Detailed mathematical approach

Problem Summary

The Fibonacci sequence is defined by \(F_1=1\), \(F_2=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n \ge 3\). The problem asks for the first index \(n\) such that \(F_n\) has 1000 decimal digits.

A direct search would keep generating larger and larger Fibonacci numbers until the digit count reaches 1000. The implementations take a lighter route: they still advance the Fibonacci recurrence, but they rescale the stored pair whenever a new power of ten is crossed. This keeps only mantissa-sized values in memory while still tracking exactly when the digit count increases.

Mathematical Approach

Two complementary viewpoints are useful here. Analytically, Binet's formula and logarithms explain why the answer is 4782. Computationally, the implemented code uses the same growth law in iterative form by normalizing consecutive Fibonacci terms.

The Sequence and Its Growth

Because each term is the sum of the previous two, the Fibonacci numbers grow exponentially. The exact closed form is

\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]

Here \(\varphi\) is the golden ratio and \(|\psi| \lt 1\). That second fact matters: the term \(\psi^n\) shrinks rapidly, so the size of \(F_n\) is controlled by \(\varphi^n/\sqrt5\). This is why the problem can be solved from growth alone without constructing a 1000-digit integer.

Turning a Digit Count into an Inequality

For any positive integer \(N\), the number of decimal digits is

\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]

So the first Fibonacci number with at least \(D\) digits is the first one satisfying

\[ F_n \ge 10^{D-1}. \]

Because the Fibonacci sequence is strictly increasing for \(n \ge 2\), this threshold is crossed only once. That means the problem really is "find the smallest index where the inequality becomes true."

Solving for the Minimal Index

For \(n \ge 2\), the standard Fibonacci digit formula is

\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]

Therefore we want the smallest integer \(n\) such that

\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]

That is equivalent to

\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]

hence

\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]

Since \(n\) must be an integer, the first valid index is

\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]

The special case \(D=1\) is handled separately, because \(F_1=1\) already has one digit.

Worked Example

Take \(D=3\). Then

\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]

That matches the sequence itself: \(F_{11}=89\) has only 2 digits, while \(F_{12}=144\) has 3 digits. The same reasoning scales immediately to the Project Euler target \(D=1000\):

\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]

An equivalent computational view keeps a scaled pair proportional to \((F_n,F_{n+1})\) and divides both values by \(10\) whenever the current term grows past \(10\). Because the Fibonacci recurrence is linear and homogeneous, this common rescaling does not change which index first reaches a given digit threshold. The ratio of consecutive terms still approaches \(1/\varphi\), so the normalized loop is the iterative counterpart of the same growth law.

How the Code Works

The C++, Python, and Java implementations keep two consecutive Fibonacci terms in scaled form, together with a decimal-exponent counter and the current index. They start from \(F_1=F_2=1\), advance by the usual recurrence, and inspect the newly current term after each step.

If that stored term has grown past \(10\), both stored values are divided by \(10\) and the exponent counter is incremented. Applying the same factor to both terms preserves the recurrence up to a common scale, so the next update remains proportional to the true Fibonacci sequence.

The loop stops when the exponent counter first reaches \(D\). At that moment the current index is exactly the first index whose Fibonacci number has \(D\) digits. The implementations verify this on the checkpoints \(D=2 \mapsto 7\), \(D=3 \mapsto 12\), and \(D=1000 \mapsto 4782\).

Complexity Analysis

Let \(t\) be the answer index. The normalized loop performs one constant-cost update per Fibonacci step, so the running time is \(O(t)\). Because Fibonacci digit counts grow linearly with the index, this is also \(O(D)\) for a requested digit threshold \(D\).

Memory usage is \(O(1)\): only two scaled terms, one exponent counter, and one index are stored. For the Project Euler target the total work is just 4782 iterations, so the method remains effectively instantaneous while avoiding both big integers and a direct logarithmic formula.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=25
2. Fibonacci number: Wikipedia - Fibonacci number
3. Binet's formula: Wikipedia - Closed-form expression for Fibonacci numbers
4. Golden ratio: Wikipedia - Golden ratio
5. Common logarithm: Wikipedia - Common logarithm