Project Euler Problem 25 - ONLY DO WHAT ONLY YOU CAN DO

フィボナッチ数列で1000桁になる最初の項は何番目か?

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2025

フィボナッチ数列は以下の漸化式で定義される:

$F_n = F_{n-1} + F_{n-2}$ , ただし $F_1 = 1, F_2 = 1$ .
最初の12項は以下である.

$F_1 = 1$
$F_2 = 1$
$F_3 = 2$
$F_4 = 3$
$F_5 = 5$
$F_6 = 8$
$F_7 = 13$
$F_8 = 21$
$F_9 = 34$
$F_{10} = 55$
$F_{11} = 89$
$F_{12} = 144$
12番目の項, $F_{12}$ が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

1000-digit Fibonacci number

http://projecteuler.net/problem=25

The Fibonacci sequence is defined by the recurrence relation:

$F_n = F_{n-1} + F_{n-2}$ , where $F_1 = 1$ and $F_2 = 1$ .
Hence the first 12 terms will be:

$F_1 = 1$
$F_2 = 1$
$F_3 = 2$
$F_4 = 3$
$F_5 = 5$
$F_6 = 8$
$F_7 = 13$
$F_8 = 21$
$F_9 = 34$
$F_{10} = 55$
$F_{11} = 89$
$F_{12} = 144$
The 12th term, $F_{12}$ , is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

考え方

フィボナッチ数列の一般項は次の式で表される
$F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {{\phi^n - (-\phi)^{-n}} \over \sqrt{5}}$
ただし、 $\phi \equiv \frac{1+\sqrt{5}}{2} \simeq 1.618 033 988 749 895$ は黄金比。
この式の第2項は n = 0 のときの $1 / \sqrt 5 \simeq 0.447$ が最大で、それを超えることはない。従って、第2項を略した次の式は F_n の値を 0.447 以下（n > 4 のとき1%以下）の誤差で与える近似式である。
$F_n \approx {\phi^n \over \sqrt{5}}$
この誤差は 0.5 より小さいので、F_n の正確な整数値は以下の式で得られる。
$F_n = \left\lfloor {\phi^n \over \sqrt{5}} + \frac{1}{2} \right\rfloor$
ただし、 $\lfloor x\rfloor$ は床関数。
wikipedia フィボナッチ数