Robert Eisele
Engineer, Systems Architect and DBA

# Project Euler 25: 1000-digit Fibonacci number

Problem 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 index of the first term in the Fibonacci sequence to contain 1000 digits?

## Solution

Lemma: Length $$L(n)$$ of number $$n$$:
$\begin{array}{rl} & 10^{d-1} \leq n < 10^d\\ \Leftrightarrow & (d-1) \cdot log(10) \leq log(n) < d \cdot log(10)\\ \Leftrightarrow & (d-1) \leq log(n) / log(10) < d\\ \Leftrightarrow & d <= log_{10}(n) + 1 < d + 1\\ \Leftrightarrow & d = \lfloor1 + log_{10}(n)\rfloor\\ \Leftrightarrow & L(n) = \lfloor 1 + log_{10}(n)\rfloor \end{array}$

The nth fibonacci number has a well known closed formula using the golden ratio:

$F(n) = \frac{\Phi^n - (-\Phi)^{-n}}{\sqrt{5}}$

As $$n$$ will become quite large, we can ignore the subtrahend of this formula and simplify the expression a bit, or more formally:

$\lim\limits_{n\to\infty} F(n) =\lim\limits_{n\to\infty} \frac{\Phi^n - (-\Phi)^{-n}}{\sqrt{5}} = \frac{\Phi^n}{\sqrt{5}}$

Okay, now let's bring together the two things:

$\begin{array}{rl}L(F(n)) &= \lfloor 1 + log_{10}(\Phi^n / sqrt(5))\rfloor\\&= \lfloor 1 + n \cdot log_{10}(\Phi) - 0.5 \cdot log_{10}(5)\rfloor\end{array}$

We now can use this for our 1000 digit fibonacci number and solve:

$\begin{array}{rl}& 1000 < 1 + d \cdot log_{10}(\Phi) - 0.5 \cdot log_{10}(5)\\\Leftrightarrow& 999 < d \cdot log_{10}(\Phi) - 0.5 \cdot log_{10}(5)\\\Leftrightarrow& d > (999 + 0.5 \cdot log_{10}(5)) / log_{10}(\Phi)\\\Leftrightarrow& d > (999 \cdot log(10) + 0.5 \cdot log(5)) / log(\Phi)\\\Rightarrow& d = \lceil(999 \cdot log(10) + 0.5 \cdot log(5)) / log(\Phi)\rceil\end{array}$

Compressing all constants and formulating it for a general $$n$$, the implementation can then be stated as:

function solution(n) {
return Math.ceil(4.78497 * n - 3.1127);
}
solution(1000);


Go to overview