## Project Euler Problem 25 & HackerRank Version 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:

F_{n} = F_{n-1} + F_{n-2}, where F_{1} = 1 and F_{2} = 1.

Hence, the first 12 terms will be: {1,1,2,3,5,8,13,21,34,55,89,144}

The 12th term, F_{12}, 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 n^{th} Fibonacci term and using logs to determine its magnitude. This formula takes advantage of Fibonacci terms converging to φF_{n} = F_{n+1}, where φ (Phi) is the Golden Ratio
.

The n^{th} Fibonacci number is the closest integer to so we can define an inequality that we will use to solve for *n*—the first Fibonacci term that contain *d>1* digits. In the case of *d* = 1000 digits it would be 10^{999} or 1 followed by 999 zeros:

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

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

HackerRank Project Euler 25 requires us to run up to 5,000 test cases and find the first term in the Fibonacci sequence to contains *d* digits where, 2 ≤ *d* ≤ 5000.

### 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)))

### Last Word

Fun Fact: 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.