(8 votes, average: 5.00 out of 5)

## Project Euler 25: Find the first term in the Fibonacci sequence to contain 1000 digits

#### Project Euler 25 Problem Description

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

 F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 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?

#### 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 φFn = Fn+1, where φ(Phi) is the Golden Ratio $\varphi = \frac{1+\sqrt{5}}{2}$.
This equation will calculate the first index, n, of a Fibonacci number, Fn, with d digits:

$n = \lceil \frac {d-1+\frac{log 5}{2}} {log \varphi}\rceil$

The HackerRank version of this problem requires a program to run thousands of trials for values of d between 2 and 5,000 in a few seconds.

#### Project Euler 25 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 25 Solution Python 2.7 source.

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|4782|

#### Afterthoughts

• Binet’s Fibonacci Formula
• $F_n = \frac {(1+\sqrt{5})^n-(1-\sqrt{5})^n} {2^n\sqrt{5}}$

• Works for number of digits, L > 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.
Project Euler 25 Solution last updated