Return to Answer

1. There are no docstrings. How are we supposed to know what this code does and how to call it?

2. There are no test cases. This kind of code is an ideal opportunity to use doctests.

3. To memoize a function, the most convenient way to do it is to use a decorator. This keeps the memoization logic separate from the code being memoized, and also makes the memoization re-usable for other functions. In particular, there is a @memoized decorator in the Python Decorator Library, so there is no need to reinvent the wheel. Using this decorator, you could write:

    @memoized
    def F(n):
        """Return the 'n'th Fibonacci number.
   
            >>> [F(i) for i in range(10)]
            [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   
        """
        if n <= 2:
            return (0, 1, 1)[n]
        else:
            return F(n - 1) + F(n - 2)
   

4. Once you split the memoization into its own function or class, there will no longer be any persistent state in your program (the only use of self at present is self.cached_result). So there is no need to use a class here.

1. You start your summation loop with sequence = 2. But this means that someone who wants to check that your code is correct would have to go through a complicated analysis: "why start at 2? ... er ... Oh, I see, F(0) = 0 which doesn't contribute anything to the sum, and F(1) = 1 which is odd. But F(2) = 1 too so why not start at 3?"

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

       >>> # See <http://oeis.org/A099919>
       >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
       [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

    """
    total = 0
    # a = F(2) and b = F(3), so b is first nonzero even Fibonacci number.
    a, b = 1, 2
    while b <= limit:
        total += b
        # Every third Fibonacci number is even, so skip directly from
        # F(3n) to F(3n+3), the next even value. If we have a = F(3n-1)
        # and b = F(3n) then F(3n+1) = a+b, F(3n+2) = a+2b, and
        # F(3n+3) = 2a+3b.
        a, b = a + 2*b, 2*a + 3*b
    return total

1. There are no docstrings. How are we supposed to know what this code does and how to call it?

2. There are no test cases. This kind of code is an ideal opportunity to use doctests.

3. To memoize a function, the most convenient way to do it is to use a decorator. This keeps the memoization logic separate from the code being memoized, and also makes the memoization re-usable for other functions. Using functools.lru_cache you could write:

    from functools import lru_cache
   
    @lru_cache(maxsize=None)
    def F(n):
        """Return the 'n'th Fibonacci number.
   
        >>> [F(i) for i in range(10)]
        [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   
        """
        if n <= 2:
            return (0, 1, 1)[n]
        else:
            return F(n - 1) + F(n - 2)
   

4. Once you split the memoization into its own function or class, there will no longer be any persistent state in your program (the only use of self at present is self.cached_result). So there is no need to use a class here.

1. You start your summation loop with sequence = 2. But this means that someone who wants to check that your code is correct would have to go through a complicated analysis: "why start at \$2\$? ... er ... Oh, I see, \$F(0)=0\$ which doesn't contribute anything to the sum, and \$F(1)=1\$ which is odd. But \$F(2)=1\$ too so why not start at \$3\$?"

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

   >>> # See <http://oeis.org/A099919>
   >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
   [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

    """
    total = 0
    # a = F(2) and b = F(3), so b is first nonzero even Fibonacci number.
    a, b = 1, 2
    while b <= limit:
        total += b
        a, b = a + 2*b, 2*a + 3*b
    return total

This works because every third Fibonacci number is even, so we skip directly from \$F(3n)\$ to \$F(3n+3)\$, the next even value. If we have $$\eqalign{a &= F(3n-1) \\ b &= F(3n)}$$ then $$\eqalign{F(3n+1) &= a+b \\ F(3n+2) &= a+2b \\ F(3n+3) &= 2a+3b}$$

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

       >>> # See <http://oeis.org/A099919>
       >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
       [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

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

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

       >>> # See <http://oeis.org/A099919>
       >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
       [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

    """
    total = 0
    # a = F(2) and b = F(3), so b is first nonzero even Fibonacci number.
    a, b = 1, 2
    while b <= limit:
        total += b 
        # Every third Fibonacci number is even, so skip directly from
        # F(3n) to F(3n+3), the next even value. If we have a = F(3n-1)
        # and b = F(3n) then F(3n+1) = a+b, F(3n+2) = a+2b, and
        # F(3n+3) = 2a+3b.
        a, b = a + 2*b, 2*a + 3*b
    return total

1. There are no docstrings. How are we supposed to know what this code does and how to call it?

2. There are no test cases. This kind of code is an ideal opportunity to use doctests.

3. Using the same piece of code for multiple purposes makes your code harder to read, harder to test, and less maintainable. Here you are using a single class for three things: (i) computing Fibonacci numbers; (ii) memoizing a recursive computation, and (iii) summing the results.

It would be better to split these three parts of the functionality into different functions or classes.

To memoize a function, the most convenient way to do it is to use a decorator. In particular, there is a @memoized decorator in the Python Decorator Library, so there is no need to reinvent the wheel. Using this decorator, you could write:

    @memoized
    def F(n):
        """Return the 'n'th Fibonacci number.

            >>> [F(i) for i in range(10)]
            [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

        """
        if n <= 2:
            return (0, 1, 1)[n]
        else:
            return F(n - 1) + F(n - 2)

1. Once you split the memoization into its own function or class, there will no longer be any persistent state in your program (the only use of self at present is self.cached_result). So there is no need to use a class here.

2. A mathematical approach

A nice feature of Project Euler is that the problems benefit from a bit of mathematical thinking. In some of the early problems you can bludgeon through them by looping over all the values (as you do here), but later on this becomes impossible: it would take far too long, so you have to use some mathematics to reduce the amount of computation.

Let's practice that here. Start by having a look at the Fibonacci numbers and seeing which ones are even:

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

You can see that every third Fibonacci number is even (exercise: prove this). Now, each Fibonacci number is the sum of the previous two Fibonacci numbers, so the sum of all the even Fibonacci numbers up to F_3n is exactly half of sum of all the Fibonacci numbers up to F_3n. (For example, taking n = 2, we find that 0 + 2 + 8 = 10, and 0 + 1 + 1 + 2 + 3 + 5 + 8 = 20.)

Can we find a quick way to sum the Fibonacci numbers? Let's look at the partial sums and see if there's a pattern:

0 1 2 4 7 12 20 33 54 88 143

It should be clear from this that the sum of the Fibonacci numbers up to F_k is F_k+2 − 1 (exercise: prove this by induction).

So if you can find the largest even Fibonacci number below four million (call it F_3N) then the sum of all the Fibonacci numbers below four million will be F_3N+2 − 1. How can we quickly find N? Well, a quick peek at Wikipedia's Fibonacci numbers article reveals that

3N = floor(log_φ(F_3N·√5 + ½))

(where φ = (1 + √5) / 2). Here, F_3N ≤ 4,000,000, and log and floor are monotonic, so

3N ≤ floor(log_φ(4,000,000 · √5 + ½))

Hence

N ≤ floor(log_φ(4,000,000 · √5 + ½)) / 3

and since we want the largest such N, the value we want is

N = floor(floor(log_φ(4,000,000·√5 + ½)) / 3)

Which you can quickly compute in Python:

>>> from math import floor, log, sqrt
>>> phi = (1 + sqrt(5)) / 2
>>> int(floor(log(4000000 * sqrt(5) + 0.5, phi) / 3))
11

and so the answer we want is F₃₅ − 1, and again peeking at Wikipedia we find that

F_n = round(φⁿ / √5)

So putting this all together:

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

       >>> # See <http://oeis.org/A000071>
       >>> [sum_even_fibonacci(10**i) for i in range(8)]
       [0, 20, 88, 1596, 6764, 121392, 2178308, 9227464]

    """
    # See <http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding>
    from math import floor, log, sqrt
    sqrt5 = sqrt(5)
    phi = (1 + sqrt5) / 2
    N = int(floor(log(limit * sqrt5 + 0.5, phi) / 3))
    return int(round(pow(phi, 3 * N + 2) / sqrt5)) - 1

Note that this code uses floating-point numbers, so it won't work for arbitrarily large values of limit. But if you needed to, you could re-code it using the decimal module.

1. There are no docstrings. How are we supposed to know what this code does and how to call it?

2. There are no test cases. This kind of code is an ideal opportunity to use doctests.

3. To memoize a function, the most convenient way to do it is to use a decorator. This keeps the memoization logic separate from the code being memoized, and also makes the memoization re-usable for other functions. In particular, there is a @memoized decorator in the Python Decorator Library, so there is no need to reinvent the wheel. Using this decorator, you could write:

    @memoized
    def F(n):
        """Return the 'n'th Fibonacci number.
   
            >>> [F(i) for i in range(10)]
            [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   
        """
        if n <= 2:
            return (0, 1, 1)[n]
        else:
            return F(n - 1) + F(n - 2)
   

4. Once you split the memoization into its own function or class, there will no longer be any persistent state in your program (the only use of self at present is self.cached_result). So there is no need to use a class here.

2. A simpler approach

This is the kind of problem that can be solved very simply. No need for classes, memoization, or multiple functions; all that's needed is a simple loop:

def sum_even_fibonacci(limit):
    """Return the sum of the even Fibonacci numbers up to 'limit'.

       >>> # See <http://oeis.org/A099919>
       >>> [sum_even_fibonacci(4 ** i) for i in range(1, 11)]
       [2, 10, 44, 188, 798, 3382, 14328, 60696, 257114, 1089154]

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