Project Euler Problem 2

Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with $1$ and $2$, the first $10$ terms will be:

$$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

We want to sum all the even Fibonacci numbers up to some limit. We could generate all the Fibonacci numbers up to that limit and just sum the even ones, but there's a cooler method!

We'll use a slightly different convention from Project Euler. The recurrence relation for the $n^\text{th}$ Fibonacci number is $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$ so the first 13 terms are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots

Notice that $F_3 = 2$, $F_6 = 8$, $F_9 = 34$, and $F_{12} = 144$. So every third number is even, and all the others are odd. This is because $F_0 = 0$ is even and $F_1 = 1$ is odd, so $F_2 = F_1 + F_0$ will be odd because $\text{even} + \text{odd} = \text{odd}$ by parity. Then $F_3 = F_2 + F_1$ will be even because $\text{odd} + \text{odd} = \text{even}$. This continues and so every third Fibonacci will be even, and all others are odd.

Now that we know every third Fibonacci number is even, can we find a recurrence relation for just the even Fibonacci numbers? So we want to compute $F_n$ using $F_{n-3}$, $F_{n-6}$, $F_{n-9}$, etc.

We can start by writing out

\begin{align} F_{n+3} &= F_{n+2} + F_{n+1} \\ &= (F_{n+1} + F_n) + F_{n+1} \\ &= 2F_{n+1} + F_n \end{align}

and using this we can obtain a recurrence relation for $F_{n+6}$

\begin{align} F_{n+6} &= 2F_{n+4} + F_{n+3} \\ &= 2(2F_{n+2} + F_{n+1}) + (2F_{n+1} + F_n) \\ &= 4(F_{n+2} + F_{n+1}) + F_n \\ &= 4F_{n+3} + F_n \\ \end{align}

So knowing that $F_3 = 2$ and $F_6 = 8$ we can use the recurrence relation

F_n = 4F_{n-3} + F_{n-6}

to generate all the even Fibonacci numbers directly, skipping over all the odd ones!

We can implement this in Julia:

function sum_even_fibonacci(limit)
    limit < 2 && return 0
    limit < 8 && return 2

    a, b = 2, 8
    result = a + b

    while (c = 4b + a) ≤ limit
        result += c
        a, b = b, c
    end

    return result
end

Benchmarking sum_even_fibonacci(4 * 10^6) we get 3.375 ns which is pretty fast. Since the Fibonacci numbers grow exponentially, we can increase the limit to a much larger number and still compute the sum quickly. For example, benchmarking sum_even_fibonacci(4 * 10^15) only takes 6.259 ns.

This solution takes $\mathcal{O}(\log L)$ time because Fibonacci numbers grow exponentially, so only about $\log L$ terms are needed to reach the limit $L$.