Mihir Yerande

The Fibonacci sequence is defined by the recurrence relation:

\(\hspace{1em}F_n = F_{n−1} + F_{n−2}\text{, where }F_1 = 1\text{ and }F_2 = 1\).

Hence the first 12 terms will be:

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

The 12^th 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?

The Fibonacci numbers are interesting for many reasons, and much discussion can be had about them.
I've discussed them a bit here: Fibonacci Numbers
However, for the sake of solving this problem, we will avoid that discussion and skip ahead to find a practical solution.

Note that we define the Fibs as follows:

• \(F_0 = 0\)
• \(F_1 = 1\)
• \(F_n = F_{n-1} + F_{n-2}\), where \(n \in \mathbb{N}\) and \(n \geq 2\)

• Lowercase phi: \(\hspace{1em}\displaystyle\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\cdots\)
• Lowercase psi: \(\hspace{1em}\displaystyle\psi = \frac{1-\sqrt{5}}{2} \approx -0.618\cdots\)

At first glance, we could easily write some code to iterate upwards and enumerate the Fibs in sequence.
The following code would accomplish what we need:


The time-complexity of this code depends on number of iterations, i.e. the index of the Fib in question.
Since we know the Fibs are roughly exponential, this would be roughly \(O(log(10^d)) \rightarrow O(d)\).

Can we do better? → YES

Let's instead look at the direct formula used for Fib computation:

\(\hspace{1em}\displaystyle F_n = round\left(\frac{\phi^n}{\sqrt{5}}\right)\)

We can use this formula to formula calculate the desired value of index \(n\), as follows:

\( \begin{align*} \hspace{1em}F_n & \geq 10^{d-1} & \text{Desired Fib} \\ \hspace{1em}round\left(\frac{\phi^n}{\sqrt{5}}\right) & \geq 10^{d-1} & \text{Approximate formula} \\ \hspace{1em}\frac{\phi^n}{\sqrt{5}} & \geq 10^{d-1} - 0.5 & \text{Accounting for rounding} \\ \hspace{1em}\phi^n & \geq (10^{d-1} - 0.5) \cdot \sqrt{5} \\ \hspace{1em}log\left(\phi^n\right) & \geq log\left((10^{d-1} - 0.5)) \cdot \sqrt{5}\right) \\ \hspace{1em}n \cdot log(\phi) & \geq log\left(10^{d-1}-0.5\right) + \frac{1}{2}\cdot log(5) \\ \hspace{1em}n & \geq \frac{log\left(10^{d-1}-0.5\right) + \frac{1}{2}\cdot log(5)}{log(\phi)} \\ \hspace{1em}n_{min} & = ceil\left(\frac{log\left(10^{d-1}-0.5\right) + \frac{1}{2}\cdot log(5)}{log(\phi)}\right) & \text{Least possible }n \\ \hspace{1em}n_{min} & = ceil\left(\frac{log\left(10^{d-1}\right) + \frac{1}{2}\cdot log(5)}{log(\phi)}\right) & \text{Simplifying approximation} \\ \hspace{1em}n_{min} & = ceil\left(\frac{log_{10}\left(10^{d-1}\right) + \frac{1}{2}\cdot log_{10}(5)}{log_{10}(\phi)}\right) & \text{Explicitly use log base-}10 \\ \hspace{1em}n_{min} & = ceil\left(\frac{(d-1) + \frac{1}{2}\cdot log_{10}(5)}{log_{10}(\phi)}\right) \\ \end{align*} \)

Since we've reduced this to a finite set of arithmetic operations, the time-complexity is essentially \(O(1)\).

We can plug into the final formula to obtain the following:

\( \begin{align*} \hspace{1em}n_{min} &= ceil\left(\frac{(d-1) + \frac{1}{2}\cdot log_{10}(5)}{log_{10}(\phi)}\right) \\ \hspace{1em} &= ceil\left(\frac{(1000-1) + \frac{1}{2}\cdot log_{10}(5)}{log_{10}(\phi)}\right) \\ \hspace{1em} &= ceil(4,781.859\cdots) \\ \hspace{1em} &= 4,782 \\ \end{align*} \)

The full Python3 code for my solution implementation can be found here: GitHub Solution