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 φ, the golden ratio, and leverages the property that Fibonacci numbers approach a geometric sequence as n increases, i.e., φF_n = F_n+1.

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

Where is 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.

Now, using algebra, solve for n.

Let’s use our new equation to solve the example problem above and calculate the first term to contain three digits. We calculated and 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 ≤ d ≤ 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.