Project Euler Problem 25: \(1000\)-Digit Fibonacci Number¶
The source code for this problem can be found here.
Problem Statement¶
The Fibonacci sequence is defined by the recurrence relation:
\[F_n = F_{n-1} + F_{n-2}, \mbox{ where } F_1 = 1 \mbox{ and } F_2 = 1.\]
Hence the first \(12\) terms will be:
\[\begin{split}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{split}\]
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?
Solution Discussion¶
Simply iterate over the Fibonacci sequence until an \(F_n\) is encountered containing \(1000\) digits.
Solution Implementation¶
from itertools import dropwhile
from lib.digital import num_digits
from lib.sequence import Fibonaccis
def solve():
""" Compute the answer to Project Euler's problem #25 """
target = 1000
fibs = Fibonaccis()
for n, F_n in dropwhile(lambda elt: num_digits(elt[1]) < target, enumerate(fibs)):
return n
expected_answer = 4782
-
solutions.problem25.
solve
()¶ Compute the answer to Project Euler’s problem #25