Problem Description

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:

The 12th term, F₁₂, is the first term to contain three digits.

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

Analysis

Solving this problem simply comes down to knowing Binet’s formula for finding the nth Fibonacci term and using logs to determine its magnitude. This formula takes advantage of Fibonacci terms converging to (n)*Phi = (n+1), where Phi is the Golden Ratio (1 + √5)/2.
In order to find the index, n, of a Fibonacci number, f_n with d digits:

n in f_n = (d − 1 + log₁₀(5) /2) / log₁₀(phi)

Solution

Runs < 1 second in Python.

from math import log10, ceil, sqrt
phi = (1+sqrt(5))/2 
digits = 1000
 
f_term = ceil((digits-1 + log10(5)/2) / log10(phi))
print "Answer to PE25 = ", int(f_term)

Comments

• Binet’s Fibonacci Formula
  
• Works for digits > 1
• Did you know that you can use the Fibonacci sequence to convert between miles and kilometers? Just find the miles in the sequence and take the next value in the sequence for an approximate measure in kilometers. For example, 89 miles is approximately 144 kilometers.