Finding the First 1000-Digit Fibonacci Number: A Python Solution to Project Euler Problem 25

Project Euler Problem 25 asks us to find the index of the first Fibonacci number containing 1000 digits. While many would reach for complex mathematical formulas or libraries, sometimes a straightforward iterative approach is all you need.

The Problem

The Fibonacci sequence is defined as:

• F(1) = 1

• F(2) = 1

• F(n) = F(n-1) + F(n-2) for n > 2

The sequence grows rapidly: 1, 1, 2, 3, 5, 8, 13, 21, 34... and we need to find which term first reaches 1000 digits.

The Solution

Here's a clean Python implementation that solves this problem:

counter = 2
fibonacci_value_x = 1
fibonacci_value_y = 1
fibonacci_value = 0

while len(str(fibonacci_value)) < 1000:
    counter += 1
    fibonacci_value = fibonacci_value_x + fibonacci_value_y
    fibonacci_value_x = fibonacci_value_y
    fibonacci_value_y = fibonacci_value
    print(fibonacci_value)

print(counter)

How It Works

The algorithm uses a simple sliding window approach:

1. Initialize the sequence with the first two Fibonacci numbers (both equal to 1)

2. Track three values: the two most recent Fibonacci numbers (fibonacci_value_x and fibonacci_value_y) and the current sum

3. Iterate until we reach 1000 digits by checking the string length of the current number

4. Slide the window forward by updating our tracking variables for the next iteration

The beauty of this approach is its simplicity. By converting the number to a string with str(), we can easily count digits without logarithms or complex mathematical operations.

Why This Works

Python handles arbitrarily large integers natively, which means we don't need special libraries for big number arithmetic. The Fibonacci sequence grows exponentially, so we reach 1000 digits relatively quickly—the answer is 4782.

The space complexity is O(1) since we only store three values at any time, and the time complexity is O(n) where n is the index of the target Fibonacci number.

The Result

Running this code reveals that F(4782) is the first Fibonacci number with 1000 digits. The program efficiently computes this in milliseconds, demonstrating that sometimes the most direct approach is the best approach.