콘텐츠로 건너뛰기
Home » 오일러 프로젝트 25

오일러 프로젝트 25

피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

F_n = F_{n - 1} + F_{n - 2} \\(F_1 = 1, F_2 = 1)

이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144 

수열의 값은 F12에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇 번째 항입니까?

http://euler.synap.co.kr/prob_detail.php?id=25

접근

어떤 수가 몇 자리인지를 확인하려면 그 수의 상용로그 값을 취하면 된다. 10의 상용로그 값은 1이며, 1의 상용로그 값은 0이다. 따라서 N의 상용로그 값의 정수부가 a 라면, N은 a + 1 자리 수라는 사실을 알 수 있다.

앞선 문제들에서 많이 해본 바와 같이, 피보나치 수열을 전개해나가면서 상용로그값이 999 이상이 되는 시점을 찾으면 된다.

%% time

from math import log10

n, a, b = 1, 1, 1
while log10(a) < 999:
  a, b, n = b, a + b, n + 1
print(n)

피보나치 수열은 말 그대로 눈덩이처럼 불어나기 때문에 1000자리가 되기 까지는 그리 오랜 시간이 걸리지 않는다. (16번 문제s_add()를 쓰면 1초 가량이 걸리는데, s_add() 의 성능도 개선할 필요가 있을 것 같다.)

비네의 식을 이용한 접근

이웃한 피보나치 수의 비율이 황금비에 아주 느리게 수렴한다는 것이 알려져 있다. 이를 바탕으로 비네의 식이라는 피보나치 수열의 일반항의 근사치를 구하는 식이 있다.

F_n = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}

이 근사치는 Fn에 근접하는 정수를 말한다. 이 값이 1000자리가 된다면 아래와 같은 식을 세울 수 있다. 위 식에서 (1 – ɸ) 는 1 미만의 수로 몇 번만 거듭제곱하면 0에 가까운 수가 되니 무시한다.

\begin{array}{lllll}
\phi^n \div \sqrt{5} & > & 10^{999} \\
\phi^n &> & \sqrt{5} \cdot 10^{999} \\
n \cdot log_{10}\phi & > & 999 + log_{10}\sqrt{5} \\
n & > & (999 + log_{10}\sqrt{5}) \div log_{10}\phi
\end{array}

황금비율 ɸ는 (1 + √5) / 2로 정의되며, 위 부등식을 만족하는 정수를 찾으면 된다.

from math import log10 as log

phi = (1 + 5 ** .5) / 2
x = ( 1000 + log(5 ** .5)) / log(phi)
print(int(x + .5))