About

Project Euler is a great way to solve some fun maths with the computer. Computers are as fundamental a tool for the modern mathematician, as the square and compass were to the Ancient Greeks. Try out some problems!

Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 8 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, ...

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

Solution

We must generate even terms and keep track of a rolling sum of these terms.

Types

If we were writing this in a strictly typed language we can look to Binet's formula and some simple algebra for guidance. Each term in our sequence will be under $4\,000\,000$ , so we can fit every intermediate term inside of 32-bits. Now let's examine

Binet's Formula

F_n = \frac{1}{\sqrt{5}}\Bigg( \bigg(\frac{1 + \sqrt{5}}{2}\bigg)^n - \bigg(\frac{1 - \sqrt{5}}{2}\bigg)^n\Bigg)

Observing that Fibonacci's terms grow exponentially, it should be fairly easy to see that the sequence will surpass $4\,000\,000$ in fewer than 1000 terms, a conservative upper bound to test if our sum will fit in 32-bits. But if the reader is not convinced we can estimate how many terms it will take by realizing that as n grows, Binet's Formula will be dominated by the term

\Bigg(\frac{1 + \sqrt{5}}{2}\Bigg)^n \approxeq 1.618^n \approxeq F_n\sqrt{5}

So we can just say $4\,000\,000$ is an imaginary Fibonacci number, and use logarithms to estimate (with good accuracy) how many terms until our sequence surpasses our upper bound. In this case

n \approxeq log_{1.618}(4\,000\,000 * \sqrt{5}) \approxeq 33

Letting me conclude that our sum will fit in 32-bits, since

33 * 4\,000\,000 = 132\,000\,000 < 4\,000\,000\,000 < (1 \ll 32)

where $\ll$ is a binary left shift up the register.

Sequential Trial Sum

The most obvious solution attacks the problem directly.

Start with some initial terms
Initialize some memory for a sum
Open Loop: Check if we've reached the upper bound
1. Add to sum if even
2. Find the next term
Profit

While simple this would work well for this problem because it's

Easy to implement, so invites few mistake
Relatively small, we will reach the upper bound quickly (see Types)

In python this would be something similar to

def sum_even_fib(ubound):
    f_0 = 1
    f_1 = 1
    f_2 = f_0 + f_1
    sum = 0
    while (f_2 < ubound):
        if (f_2 % 2 == 0):
            sum += f_2
        f_0 = f_1
        f_1 = f_2
        f_2 = f_0 + f_1
    return sum

Branchless Sum

But wait there's more!

Since we only want to sum up the even Fibonacci numbers under four million, let's figure out how we stop generating any odd terms of the sequence.

Some simple number theory will show us that

even + even = even \\[3mm] odd + odd = even \\[3mm] even + odd = odd \\[3mm]

Since the Fibonacci sequence is recursive, if there is any odd number in the sequence, the terms will oscillate between odd and even. Indeed let's say we walk along the sequence until we find term $n$ , which is even since terms $n - 1$ and $n - 2$ are odd. This implies term $n + 1$ is odd, which then leads to the conclusion that $n + 2$ is odd. And so $n + 3$ is even. This pattern will repeat indefinitely. I will leave the formal proof as an exercise for the reader.

Knowing that every third (relative) term is even, let's look for a formula that finds every third term of the sequence.

F_n = F_{n-1} + F_{n-2} = (F_{n-2} + F_{n-3}) + F_{n-2} = F_{n-3} + 2F_{n-2}

Already, there is a term with a relative distance that's a multiple of 3.

F_{n-3} + 2F_{n-2} = F_{n-3} + 2(F_{n-3} + F_{n-4}) = 3F_{n-3} + 2F_{n-4} \\[3mm] 3F_{n-3} + F_{n-4} + F_{n-4} = 3F_{n-3} + (F_{n-4} + F_{n-5}) + F_{n-6} \\[3mm] \implies F_n = 4F_{n-3} + F_{n-6}

With this new formula we can start generation at n = 8, so $F_{n-6} = 2, F_{n-3} = 8$ . Since we starting by adding two even numbers together, the subseries generated with our new formula will only ever contain even numbers. This is obvious from the beginning of the sequence listed in the problem statement.

Modifying our previous code

def sum_even_fib(ubound):
    f_0 = 2
    f_3 = 8
    f_6 = f_0 + 4*f_3
    sum = 10
    while (f_6 < ubound):
        sum += f_6 # No need to check if even
        f_0 = f_3
        f_3 = f_6
        f_6 = f_0 + 4*f_3
    return sum

It may be tempting to remove the while (seq < ubound) loop, replacing it with a count determined from Binet's formula (similar to our estimation in types). This is a bad idea due to the floating point nature of the formula. Implementing Binet's formula, or a similar generating function, without rapidly expanding round off error, is very difficult. Binet's formula is what we would call poorly conditioned. Of course the interested reader can quantify this by counting flops, or benchmarking performance on their own machine.

Some Code

Checkout my python implementation on github