피보나치 수열은 아래와 같은 점화식으로 정의됩니다.
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))