Project Euler 25 Problem Statement

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: {1,1,2,3,5,8,13,21,34,55,89,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?

Solution

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 φFn = Fn+1, where φ(Phi) is the Golden Ratio \varphi = \frac{1+\sqrt{5}}{2}.

Wikipedia shows us that the nth Fibonacci number is F_n = [\frac{\varphi^n}{\sqrt{5}}], n\ge0, so we define an inequality that we will use to solve for n — the first Fibonacci term that exceeds d digits. In the case of d=1000 digits it would be 10999 or 1 followed by 999 zeros; a thousand digits:

[latex s="1"] \frac{\varphi^n}{\sqrt{5}} > 10^{d-1} [/latex]

We want to solve for n to get the Fibonacci term. Remove the fraction from the left side:

[latex s="1"] \varphi^n > \sqrt{5} \cdot 10^{d-1} [/latex]

Take the log of both sides:

[latex s="1"] \log \varphi \cdot n > \frac{log(5)}{2} + \log(10) \cdot (d-1) [/latex]

The log(10) is simply 1 and we can easily solve for n:

[latex s="2"] n > \frac{\frac{\log(5)}{2} + d-1}{\log \varphi} [/latex]

Use the ceiling function to find the closest integer.

[latex s="2"] n = \lceil \frac {\frac{\log(5)}{2} + d-1} {\log \varphi}\rceil [/latex]

Let’s try this with the example used in the problem statement. We will use 0.349845 and 0.208988 for the log(5)/2 and log(phi), respectively.

(0.349845 + 3 – 1) = 2.349485, and 2.349485/0.208988 = 11.2422, and the ceil (11.2422) = 12✓.

HackerRank version

The HackerRank Project Euler 25 version of this problem requires us to run thousands of trials for values of d between 2 and 5,000 in a second. No changes to the program are required.

Python 2.7 Source

Last Word

  • Works for number of digits, d > 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.
    This works as an approximation because there are 1.609 kilometers in a mile, which is very close to the golden ratio (1.618) – the ratio between two Fibonacci numbers.