nekedome / project-euler

solutions/problem25.py

"""
Project Euler Problem 25: :math:`1000`-Digit Fibonacci Number
=============================================================

.. module:: solutions.problem25
   :synopsis: My solution to problem #25.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem25.py>`_.

Problem Statement
#################

The Fibonacci sequence is defined by the recurrence relation:

.. math::

    F_n = F_{n-1} + F_{n-2}, \\mbox{ where } F_1 = 1 \\mbox{ and } F_2 = 1.

Hence the first :math:`12` terms will be:

.. math::

    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 :math:`12^{th}` term, :math:`F_{12}`, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain :math:`1000` digits?

Solution Discussion
###################

Simply iterate over the Fibonacci sequence until an :math:`F_n` is encountered containing :math:`1000` digits.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem25.py
   :language: python
   :lines: 54-
"""

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)):

The variable F_n seems to be unused.

        return n


expected_answer = 4782