프로젝트 오일러 002

4백만 이하의 피보나치 수 중에서 짝수인 것의 합

피보나치 수열은 수열의 앞 두 수의 합으로 전개되는 수열입니다. 비네의 공식이라는 일반항을 구하는 공식이 알려져 있지만, 수열을 계속 만들면서 합산하는 것이 가장 간단합니다.

실제로 피보나치 수열은 거의 지수적으로 증가하기 때문에, 4백만 이하의 수는 그리 많지 않습니다.(힌트: 33개 밖에 없습니다) 로직을 간단하게 하기 위해서 반복문을 직접 사용하기 보다는 피보나치 수열을 생성하는 제너레이터를 사용하도록 하겠습니다. (그리고 이상하게도 제너레이터를 사용하는 코드가 파이썬에서는 루프를 도는 것보다 더 빠릅니다.)

def fibs():
	a, b = 1, 1
	while a <= 400_0000:
		yield a
		a, b = b, a + b

print(sum(x for x in fibs() if x % 2 == 0))

Julia 에서는 이런 식으로 풀어볼 수 있고, 훨씬 빠릅니다.

let (a, b, s) = (1, 1, 0)
	while a <= 400_0000
		iseven(a) && (s += a)
		a, b = b, a + b
	end
	println(s)
end

Julia에서는 Channel을 사용하여 제너레이터와 비슷하게 구현할 수 있습니다.

let fibs = Channel() do ch
	a, b = 1, 1
	while a <= 400_0000
		iseven(a) && put!(ch, a)
		a, b = b, a + b
	end
end
collect(fibs) |> sum |> println
end

피보나치 수열의 일반항을 구하는 비네의 공식은 다음과 같이 씁니다.

$$F_n=\frac{{\varphi }^n-{\hat{\varphi }}^n}{\sqrt{5}}=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]$$

이 공식은 두 가지를 말해줍니다.

1. 피보나치 수는 n이 충분히 크다면 황금비의 거듭제곱에 비례하여 증가합니다.
2. 이웃하는 두 피보나치 수열의 차이는 n이 충분히 크다면 황금비에 수렴합니다.

피보나치 수열은 앞 두 항의 합으로 이루어지므로, 홀수, 홀수, 짝수의 패턴이 반복됩니다. 즉 3의 배수번째 항을 200만 이하의 범위에서 더해나가면 빠르게 답을 구할 수 있습니다.

sf = 5 ** 0.5
phi = (1 + sf) / 2
phi_ = (1 - sf) /2

def vn(k: int) -> int:
    return int((phi ** k - phi_ ** k) / sf)

print(sum(vn(i) for i in range(0, 100, 3) if vn(i) <= 200_0000))