Project Euler Solution #25: 1000-digit Fibonacci number

Problem 25

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:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, 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 \leq \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);