2. Even Fibonacci numbers

문제에 대한 설명은 이곳에서 확인할 수 있다. 

먼저 직관적으로 떠오르는 방식으로 구현하고 이를 ver 1.0이라고 하자.

# ver 1.0

a_n2 = 1
a_n1 = 2
answer = a_n1 # since 2 is even

while True:
	
	a_n = a_n1 + a_n2
	
	if a_n > 4000000: break

	if a_n % 2 == 0 : answer += a_n
	
	a_n1, a_n2 = a_n, a_n1

print answer

문제를 풀고 사람들의 풀이를 보니 더 나은 방법이 있다는 것을 알게 되었다. 이를 소개한다. 

먼저 수열의 시작을 1, 1로 바꾸자.^[각주:1] 이렇게 바꾸면 매 3번째 수가 짝수가 되어 계산을 줄일 수 있다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

\(n\)번째 피보나치 수열을 \(f(n)\)이라고 한다면 피보나치 수열의 성질에 의하여 다음이 성립한다.

\(f(n)=f(n-1)+f(n-2)\)
     \(=f(n-2)+f(n-3)+f(n-3)+f(n-4) \)
     \(=f(n-3)+f(n-4)+f(n-3)+f(n-3)+f(n-5)+f(n-6) \)
     \(=4f(n-3)+f(n-6)\)

위의 식을 이용한 방법을 ver 2.0이라고 하자.

# ver 2.0

a = 2
b = 8
answer = a + b

c = 4*b +a

while c < 4000000:

	answer += c
	
	a, b = b, c
	
	c = 4*b +a

print answer

답은 4613732이다. 사람들의 생각이 놀랍다.

1. 이렇게 바꾸어도 문제의 답은 바뀌지 않는다. 왜냐하면 수의 크기에만 관심이 있기 때문이다. [본문으로]