The Fibonacci sequence is defined by the recurrence relation:

F_*n* = F_*n*−1 + F_*n*−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?



In [1]:

    
from euler import gen_fibonacci, gen_lte



In [2]:

    
list(gen_lte(gen_fibonacci(), 100))









    Out[2]:





[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]



In [3]:

    
def gen_fib2():
    yield 1
    for i in gen_fibonacci():
        yield i



In [4]:

    
list(gen_lte(gen_fib2(), 100))









    Out[4]:





[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]



In [5]:

    
def gen_fib3():
    yield 0
    yield 1
    for i in gen_fibonacci():
        yield i



In [6]:

    
list(gen_lte(gen_fib3(), 100))









    Out[6]:





[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]



In [7]:

    
def foo(n):
    for i, fib in enumerate(gen_fib2(), 1):
        if len(str(fib)) >= n:
            return i



In [8]:

    
foo(3)









    Out[8]:





12



In [9]:

    
%timeit foo(1000)
foo(1000)









    



1 loops, best of 3: 248 ms per loop






    Out[9]:





4782

For extra bonus points, directly calculate the number without generating any Fibonacci numbers.

Hint: Read Knuth.



In [10]:

    
from math import sqrt, log, ceil



In [11]:

    
phi = (sqrt(5) + 1.) / 2.
def term_of_ndigits_fib(ndigits):
    return int(ceil((log(sqrt(5)) + (ndigits - 1) * log(10)) / log(phi)))



In [12]:

    
n = 1000
%timeit term_of_ndigits_fib(n)
term_of_ndigits_fib(n)









    



1000000 loops, best of 3: 1.8 us per loop






    Out[12]:





4782