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:
\begin{align} 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{align}The \(12\)th term, \(F_{12}\), is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain \(1000\) digits?
Python's unbounded ints again make this trivial — but we can make it even easier! Binet's formula implies that \(F_n\) very quickly converges to \(\frac 1{\sqrt 5} \varphi^n\), where \(\varphi = \frac{1 + \sqrt 5}2\). We thus need to find the smallest \(n\) such that \(\frac 1{\sqrt 5} \varphi^n \geq 10^{999}\). Taking logs of both sides yields \(n \log \varphi - \log \sqrt 5 \geq 999 \log 10\), so the answer is \(\left\lceil \frac{999 \log 10 + \log \sqrt 5}{\log \varphi} \right\rceil\).
from math import log, ceil, sqrt
p25 = lambda d=1000: ceil(((d-1)*log(10) + log(sqrt(5))) / log((1+sqrt(5))/2))