25. 1000-digit Fibonacci number

1. 개요

문제는 이곳에서 확인할 수 있다. $n$번째 피보나치 수열의 값을 $F_n$이라고 할 때 최초로 1000의 자리를 넘는 $F_n$의 $n$을 구하는 것이 목표이다. 단, $F_1=F_2=1$이다.

2. 구현: ver 1.0

처음에는 피보나치 수열의 일반항을 구하여 진행하려고 했으나 일반항에 무리수가 포함되어 있고 거듭제곱 연산이 발생하기 때문에 계산상 오차가 발생하였다. 피보나치 수열의 일반항은 3. 피보나치 수열의 일반항에 적고, 본 문제의 해결은 피보나치 수열의 정의를 이용한다. 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

# -*- coding: utf-8 -*- import math as m   fn_2, fn_1 = 1, 1 fn = fn_2 + fn_1 n = 3   while m.log(fn, 10) < 999:  # log_{10}10=1     fn_2 = fn_1     fn_1 = fn     fn = fn_1 + fn_2     n += 1   print(n)

답은 4782이다.

3. 피보나치 수열의 일반항

$n$번째 피보나치 수열의 값을 $F_n$이라고 할 때 일반항은 아래와 같다.

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

증명은 다음과 같다. 피보나치 수열의 점화식은 $F_{n+1}=F_n+F_{n-1}$이다.단, $n\ge 2$이며 $F_1=F_2=1$이다. 이때 $\alpha \beta =-1$, $\alpha +\beta =1$인 $\alpha$와 $\beta$를 이용하여 점화식을 $(1)$과 같이 다시 쓸 수 있다.

$$\begin{array}{}\text{(1)}& F_{n+1}-\alpha F_n& =& \beta (F_n-\alpha F_{n-1})={\beta }^2(F_{n-1}-\alpha F_{n-2})=\cdots ={\beta }^{n-1}(F_2-\alpha F_1)={\beta }^n\end{array}$$

$\alpha$와 $\beta$를 바꾸어 써도 식이 성립하므로 점화식을 $(2)$와 같이 표현할 수 있다.

$$\begin{array}{}\text{(2)}& F_{n+1}-\beta F_n& =& \alpha (F_n-\beta F_{n-1})={\alpha }^2(F_{n-1}-\beta F_{n-2})=\cdots ={\alpha }^{n-1}(F_2-\beta F_1)={\alpha }^n\end{array}$$

$(1)$과 $(2)$를 연립하여 $F_n=({\beta }^n-{\alpha }^n)/(\beta -\alpha )$를 얻는다. 한편, $\alpha \beta =-1$, $\alpha +\beta =1$의 해는 $x^2-x-1=0$의 해와 같으므로 이를 대입하면 $F_n$의 일반항을 구할 수 있다.