Project Euler Problem 25 Solution: N-digit Fibonacci number

Project Euler Problem 25 Statement

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

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?

Solution

Girl at beach swinging water from her hair

This problem can be efficiently solved using Binet’s formula, which provides a direct expression for the n^th Fibonacci number. The formula involves $\phi$, the golden ratio, and utilizes the property that Fibonacci numbers asymptotically form a geometric sequence as $n$ increases, i.e., $\phi F_n = F_{n+1}$.

Given Binet's formula, the n^th Fibonacci number is the closest integer to:

$F_n = [\frac{\phi^n}{\sqrt{5}}], n\ge0, \ and \ \phi = \frac{1+\sqrt{5}}{2}$ (the golden ratio).

To find the first term with at least 1,000 digits (not the value, but the index of the value in the sequence), we set up an inequality based on the logarithmic scale of Binet's formula and solve for $n$.

$\large \frac{\varphi^n}{\sqrt{5}}>10^{d-1}$

Now, using algebra, solve for n.

$$\begin{align*} \text{Remove the fraction, }\phi^n&>\sqrt{5}\cdot 10^{d-1}\\[10pt] \text{Take the log of both sides, }\log\phi\cdot n&>\frac{\log 5}{2}+\log 10\cdot (d-1)\\[10pt] \text{Solve for n, }n&>\frac{\frac{\log 5}{2}+d-1}{\log\phi}\\[10pt] \text{Find the least integer\textgreater n, }n&=\lceil \frac{\frac{\log 5}{2}+d-1}{\log\phi}\rceil\\ \end{align*}$$

Let’s use our new equation to solve the example problem above and calculate the first term to contain three digits. We calculated $\frac{\log 5}{2}$ and $\log\phi$ as 0.349845 and 0.208988, respectively. The ceiling function maps a number to the least integer greater than or equal to that integer.

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

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 25

This solution also solves HackerRank's version of Project Euler Problem 25. HackerRank increases the challenge to finding the first term in the Fibonacci sequence with $d$ digits for $2\le d\le 5000$ and accommodating up to 5,000 test cases.

Python Source Code

from math import log10, ceil, sqrt
phi = (1+sqrt(5))/2  # phi is the golden ratio, 1.61803398875
d = int(input("Digits in Fibonacci number? "))

term = ceil((log10(5)/2 + d-1) / log10(phi))
print ("First Fibonacci term to contain %d digits is F(%d)." % (d, int(term)))

Run Project Euler Problem 25 using Python on repl.it.

Last Word

Fun Fact: The Fibonacci sequence approximates mile to kilometer conversions: find miles in the sequence and use the next value for kilometers. For example, 89 miles is about 144 kilometers, as 1.609 km/mile approximates the golden ratio (1.618), linked to Fibonacci numbers.