Project Euler #2: Even Fibonacci Numbers

Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. Starting with 1 and 2, the first 10 terms are:

Find the sum of even-valued terms whose values do not exceed 4 million.

Observation: Which Fibonacci Numbers Are Even?

Call the Fibonacci sequence $F_1 = 1, F_2 = 2, F_3 = 3, \ldots$.

Looking at the parity pattern: odd, even, odd, odd, even, odd, odd, even, $\ldots$

Every third Fibonacci number is even. So we only need to sum $F_3, F_6, F_9, \ldots$ — every term with index divisible by 3.

A Direct Recurrence for Even Fibonacci Numbers

Let $E_n$ be the $n$-th even Fibonacci number. The even Fibonacci numbers satisfy their own recurrence:

Proof: Using the identity $F_{3k} = F_{3k-3} + 2F_{3k-2} + F_{3k-1}$ and reducing mod 2, the even terms at positions $3, 6, 9, \ldots$ satisfy the above recurrence with $E_1 = 2$ and $E_2 = 8$.

This means we never need to generate odd Fibonacci numbers at all.

Clean Implementation

def solve(limit: int = 4_000_000) -> int:
    a, b = 2, 8       # E_1, E_2
    total = a
    while b <= limit:
        total += b
        a, b = b, 4 * b + a   # recurrence: E_{n+1} = 4E_n + E_{n-1}
    return total

print(solve())  # 4613732

The loop runs only $\lfloor \log_\phi(4 \times 10^6) / 3 \rfloor \approx 11$ iterations — essentially $O(\log N)$.

Why the Factor of 4?

The recurrence $E_{n+1} = 4E_n + E_{n-1}$ has characteristic polynomial $x^2 - 4x - 1 = 0$, with roots:

where $\phi = (1+\sqrt{5})/2$ is the golden ratio. Since even Fibonacci numbers are $F_{3n}$ and $F_{3n} = \phi^{3n}/\sqrt{5} + \ldots$, the effective base of growth is $\phi^3 = 2 + \sqrt{5} \approx 4.236$, which explains the coefficient 4 in the recurrence.

Answer