25問目

Fibonacci 数列は再帰的な関係式によって定義されている.
 F_n = F_{n-1} + F_{n-2},\quad F_1 = 1,\quad F_2 = 1.
従って, 最初の12個は,
 \begin{eqnarray} 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 \end{eqnarray}
となる. 12番目の  F_{12} が初めて3桁になる数字である.

では, 初めて1000桁になるのは何番目か?

http://projecteuler.net/index.php?section=problems&id=25

以前の問題 (問題2改 - cocoatomo衝動日記) でも使用したように, Fibonacci 数列は一般項が
 F_n = \frac{1}{\sqrt{5}}\(\alpha^n - \beta^n\), \quad \alpha = \frac{1 + \sqrt{5}}{2},\quad \beta =\frac{1 - \sqrt{5}}{2}
と書ける. これが  10^{999} 以上になる n を求めれば良い.

 \begin{eqnarray} F_n &\geq& 10^{999} \\ \alpha^n - \beta^n &\geq& \sqrt{5} \cdot 10^{999} \end{eqnarray}.
ここで,  \beta^n は十分小さく無視できるので,
 \alpha^n &\geq& \sqrt{5} \cdot 10^{999}.
両辺の対数を取って,
 n \geq \frac{\frac{1}{2}\log{5} + 999\log{10}}{\log \alpha}.
単なる計算なので, pari/gp の力を借りて終了.