Return to Revisions

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, F₁₂, 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])) < 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.')