Project Euler Problem 25

Project Euler Problem 25

Solution

Answer: 4782

We seek the index $n$ of the first Fibonacci number with $1000$ digits.

The Fibonacci sequence satisfies:

$$F_n = F_{n-1}+F_{n-2}, \qquad F_1=1,;F_2=1$$

A number has $1000$ digits if:

$$F_n \ge 10^{999}$$

Using the approximation from Binet’s formula:

$F_n\approx \frac{\varphi^n}{\sqrt{5}}$

where $\varphi = \frac{1+\sqrt5}{2}$.

We solve:

$$\frac{\varphi^n}{\sqrt5} \ge 10^{999}$$

Taking logarithms:

$$n\log_{10}(\varphi)-\log_{10}(\sqrt5)\ge 999$$

$$n \ge \frac{999+\log_{10}(\sqrt5)} {\log_{10}(\varphi)}$$

Evaluating gives:

$$n \ge 4781.859\ldots$$

So the first valid index is:

$$n = 4782$$

Python code

a, b = 1, 1
index = 2

while len(str(b)) < 1000:
    a, b = b, a + b
    index += 1

print(index)

Tracing mentally:

• $F_{12}=144$ is indeed the first 3-digit Fibonacci number (matches the example).
• The loop increments until the first term reaches 1000 digits.
• The computed index is 4782.

Answer: 4782