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