1000-digit Fibonacci Number

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:

\begin{align} F_1 &= 1\\ F_2 &= 1\\ F_3 &= 2\\ F_4 &= 3\\ F_5 &= 5\\ F_6 &= 8\\ F_7 &= 13\\ F_8 &= 21\\ F_9 &= 34\\ F_{10} &= 55\\ F_{11} &= 89\\ F_{12} &= 144 \end{align}

The \(12th\) term, \(F_12\), 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

This problem doesn’t need any optimizations to be solved in milliseconds. It’s perfectly fine to store 1000-digit numbers within a BigInt, so we can just keep getting new Fibonacci sequence numbers until the result hits 1000 digits.

Pen and paper solution

We could stop there and call it a day, but this problem can be solved in a different way if we dive deep into one curious property of the Fibonacci sequence. To be continued…