Project Euler - Problem 2

Problem overview

Problem 2 asks for the sum of the even Fibonacci numbers that don't exceed 4,000,000. Start with 1 and 2, then get each new number by adding the previous two:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

For example, with a limit of 8, the answer is 2 + 8 = 10. We include 8 because the limit is inclusive.

The obvious loop

We can generate each number, check if it's even, and add it to the total. Nothing fancy.

def solution(limit):
    a, b = 1, 2
    total = 0

    while a <= limit:
        if a % 2 == 0:
            total += a
        a, b = b, a + b

    return total

This gives 4,613,732 for a limit of 4,000,000. The Fibonacci numbers grow quickly, so we don't actually need many iterations.

Skip the odd ones

The parity goes odd, even, odd, odd, even, odd... Every third term is even. So can we jump straight between them?

For Fibonacci terms, F(n + 6) = 4F(n + 3) + F(n). That means the next even term is four times the current one plus the previous one. Starting with 0 and 2 gives us 2, 8, 34, 144 and so on.

def solution(limit):
    previous, current = 0, 2
    total = 0

    while current <= limit:
        total += current
        previous, current = current, 4 * current + previous

    return total

Same answer, fewer iterations. Both versions take O(log limit) iterations as the sequence grows exponentially; the second just skips the odd terms. For this limit, either will do.