[프로젝트 오일러] 문제2 - 짝수 피보나치 숫자들

문제

영문

Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

바로가기

 

한글

피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

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

4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 됩니까?

바로가기

 

해설

세 가지 방법으로 다르게 생각해볼 수 있습니다. 뒤의 방법으로 갈수록 복잡도가 줄어듭니다!

 

파이썬 (Python) + 수학적 분석

방식 1

a = 1
b = 2
sum = 0

while b < 4000000:
  if b%2 == 0:
    sum += b
  a, b = b, a+b

print(sum)

단순하게 피보나치 수를 4백만 이하까지 반복문을 통해 구하고, 그 중 2로 나누어 떨어지는 수만 더해준 값을 출력하는 코드입니다.

 

방식 2

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

 

피보나치 수열을 살펴보면 다음과 같이 3번째 항마다 짝수임을 알 수 있습니다. 따라서 계속 2로 나누어 떨어지는지 확인할 필요 없이 3번째 수들만 계속 더해주면 되겠지요!

 

a = 1
b = 1
c = a+b
sum = 0

while c < 4000000:
  sum += c
  a = b+c
  b = c+a
  c = a+b

print(sum)

위의 아이디어를 파이썬으로 옮겨보면 다음과 같습니다.

 

방식 3

2 8 34 144 ...

 

그럼 위와 같이 아예 짝수 항만 모아져 있는 수열만을 구할 수는 없을까요? 그럼 계산량이 줄어들 텐데 말이죠. 놀랍게도 구할 수 있습니다! 바로 피보나치의 점화식을 약간 수정해서 말이죠.

 

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

 

점화식에서 n-3, n-6번째 항만을 남기려고 계속 수정해주면 다음과 같이 변하게 됩니다. 이를 이용하면 피보나치 수열에서 세 칸씩 띄워서 값을 알 수 있지요.

 

a = 0
b = 2
sum = 0

while b < 4000000:
  sum += b
  a, b = b, 4*b + a

print(sum)

위 아이디어를 코드로 표현한 것입니다!

 

정답

4613732