25. 1000-digit Fibonacci number

1. 개요

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

2. 구현: ver 1.0

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

# -*- 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( \left(\frac{1+\sqrt{5}}{2} \right )^n - \left(\frac{1-\sqrt{5}}{2} \right )^n \right )$$

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

\begin{eqnarray*} F_{n+1}-\alpha F_n &=& \beta \left( F_n-\alpha F_{n-1} \right) = \beta^2 \left( F_{n-1}-\alpha F_{n-2} \right) = \cdots = \beta^{n-1} \left( F_{2}-\alpha F_{1} \right) = \beta^{n} \label{basic01}\tag{1} \end{eqnarray*}

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

\begin{eqnarray*} F_{n+1}-\beta F_n &=& \alpha \left( F_n-\beta F_{n-1} \right) = \alpha^2 \left( F_{n-1}-\beta F_{n-2} \right) = \cdots = \alpha^{n-1} \left( F_{2}-\beta F_{1} \right) = \alpha^{n} \label{basic02}\tag{2} \end{eqnarray*}

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