Project Euler Problem 25 Solution

Project Euler & HackerRank Problem 25 Solution

N-digit Fibonacci number
by {BetaProjects} | APRIL 10, 2009 | Project Euler & HackerRank

Project Euler Problem 25 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

Girl at beach swinging water from her hair

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 Formula for the Golden Ratio.

Wikipedia shows us that the nth Fibonacci number is the closest integer to Formula for the nth Fibonacci number so we define an inequality that we will use to solve for n—the first Fibonacci term that contain d digits. In the case of d = 1000 digits it would be 10999 or 1 followed by 999 zeros:

Solving Binet’s formula for n

Now, we want to solve for n to and find the first term in the Fibonacci sequence with d digits.

Solving Binet’s formula for n

Let’s use our new equation for d = 3 as shown in the problem statement. We calculated sqrt(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

The HackerRank version of Project Euler 25 requires us to run up to 5,000 trials and find the first term in the Fibonacci sequence to contain d digits where, 2 ≤ d ≤ 5000.

Python Source Code

Last Word