Project Euler # 25 The 1000 digit Fibonacci index The Fibonacci sequence is defined by the recurrence relation:
  
  Fn = Fn−1 + Fn−2, where F1
  = 1 and F2 = 1.
  
  Hence the first 12 terms will be:
  
  F1 = 1
  F2 = 1
  F3 = 2
  F4 = 3
  F5 = 5
  F6 = 8
  F7 = 13
  F8 = 21
  F9 = 34
  F10 = 55
  F11 = 89
  F12 = 144
  
  The 12th term, F12, is the first term to contain three digits.
  
  What is the index of the first term in the Fibonacci sequence to
  contain 1000 digits?


from time import time


def fib(n):
    """returns index of the first fibonacci of length n digits."""
    fibs = [0, 1]
    while len(str(fibs[-1])) &lt; n:
        fibs.append(fibs[-1] + fibs[-2])
    return len(fibs) - 1


if __name__ == '__main__':
    time1 = time()
    print(fib(1000))
    print(f'Time: {time() - time1} seconds.')
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.

Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.

from math import log10, floor, ceil

def fibonacci_digits(n):
    if n &lt; 2:
        return 1
    ϕ = (1 + 5**0.5) / 2
    return floor(n * log10(ϕ) - log10(5) / 2) + 1


It's possible to calculate the inverse of this function. This way, you can find the first Fibonacci with k digits directly, without any loop:

def euler25(k):
    if k &lt; 2:
        return 1
    ϕ = (1 + 5**0.5) / 2
    return ceil((k + log10(5) / 2 - 1) / log10(ϕ))


It seems to return the correct answer for any k in less than 1 μs :

&gt;&gt;&gt; euler25(1000)
4782
&gt;&gt;&gt; euler25(10_000)
47847
&gt;&gt;&gt; euler25(100_000)
478495
&gt;&gt;&gt; euler25(100_000_000_000_000_000)
478497196678166592


The digits are the same as in:

&gt;&gt;&gt; 1 / log10(ϕ)
4.784971966781666