Project Euler #2 - Even Fibonacci numbers

Question

Given:

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, ...

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

MAX_LIMIT = 4000000 # Four million inclusive
FIB_CACHE = {}

def fib(n):
    """ Calculates nth fibonacci term.
    Args:
        n: The nth term.
    Returns:
        The nth fibonacci term of the series.
    """
    if (2 >= n):
        return n
    if (n not in FIB_CACHE):
        FIB_CACHE[n] = fib(n-1) + fib(n-2) # linear recurrence
    return FIB_CACHE[n]
    
def sum_fib():
    sum = 0
    i = 1
    ith_fib = 0
    while (1):
        ith_fib = fib(i)
        if (ith_fib > MAX_LIMIT):
            return sum
        if (ith_fib % 2 == 0):
            sum += ith_fib
        i += 1
    return sum
    
print fib(1)
print fib(2)
print fib(10)
print sum_fib()

Note: Without caching, it was taking too long to complete since it's an exponential algorithm.

Few important points:

• I read somewhere about putting fewer changing values on the left. Is this true?
• I am always confused about when to use an if-if branch and anif-else branch. Is there any heuristic? For example, could I write cache-checking code in the else branch too?

Answer 1

Going from top to bottom:

MAX_LIMIT = 4000000 # Four million inclusive

That sounds like a function parameter, not a global constant:

def sum_fib(max_limit=4000000):
    ...

Now, you have this function:

def fib(n):
    ...

But you don't really need it. You never need the nth Fibonacci number here, out of the blue. You're always going in order. If you're going in order, you can just keep them as local variables and update both:

cur, prev = cur+prev, cur

And then:

while (1):

Typically we'd say while True:, but in this case, we have a clearly established termination condition: our max limit. So let's use it:

def sum_fib(max_limit=4000000):
    cur, prev = 1, 0
    total = 0 
    while cur < max_limit:
        if cur % 2 == 0:
            total += cur 
        cur, prev = cur+prev, cur 

    return total

We could even generalize this more by providing a predicate:

def sum_fib(max_limit=4000000, pred = lambda x: x%2 == 0): 
    cur, prev = 1, 0
    total = 0 
    while cur < max_limit:
        if pred(cur):
            total += cur 
        cur, prev = cur+prev, cur 

    return total

---

Now back to optimizations. What are the Fibonacci numbers? They are:

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

What are the even Fibonacci numbers? They are:

2, 8, 34, 144, 610

Notice that it's every 3rd Fibonacci number. What can we do with that? That's still a Fibonacci-like sequence. Except instead of a_n = a_n-1 + a_n-2, we have a_n = 4a_n-1 + a_n-2:

def sum_fib(max_limit=4000000):
    cur, prev = 2, 0
    total = 0 
    while cur < max_limit:
        total += cur 
        cur, prev = 4*cur+prev, cur 

    return total

Answer 2

I think your docstring for fib could be shortened to one line. You don't need to separate out Args and Returns as headings (unless this is to follow a specific parsing format)

""" Returns the nth fibonacci term."""

A few notes about your cache. It should just be a list, every nth number calculated will need all preceding numbers anyway, so a list fits this use perfectly. You might have wanted to avoid the fact that lists start indexing from 0, but you save space by sticking with a list and you can just pass n-1 when accessing the list. Also caps in the name suggest that it's a constant, but it's obviously not as it's a cache. If you wanted to signal that it shouldn't be used, add an underscore before it _fib_cache because that's the Python style to indicate it's a 'private' variable.

Also you could make the cache part of the function itself using a mutable default value. If you added cache=[] to your fib definition then you'll create an empty list when you create the function. This list will always be passed to the function as cache unless you manually override it by passing your own list value. This way you're not reliant on an external dictionary to store your values.

Even better though, start with cache=[1,2] since the brief said to begin with those values. Now you don't need to validate special values with 2 >= n. Though it could be good to ensure that a value less than 1 hasn't been passed.

Also, when using a list, instead of testing whether an index exists first, it's actually more Pythonic and faster to try access an index and then catch if that fails and calculate the previous fibonacci values. You can do this using try except IndexError.

def fib(n, cache=[1,2]):
    if (n < 1):
        raise ValueError("n must be greater than 1")
    try:
        return cache[n-1]
    except IndexError:
        cache.append(fib(n-2) + fib(n-1))
        return cache[-1]

Also using 2 <= n is a confusing order, generally variables are on the left and constants are on the right. Another convention is using while True instead of while (1), in addition those parentheses aren't needed.

ith_fib is a confusing name, I think it's meant to be ith like 4th, but that's not clear. Just use num or current_fib.

Answer 3

Question only requires finding the sum of all even fibonacci numbers not exceeding 4million.

Another way would be to not use a array to hold previous fib numbers at all.

Something like:

n, sum = 2, 0
previous, current = 1, 1
fib = 2
while fib < 4000000:
    fib = current + previous   #equivalent to n-1 + n-2

    #check for even fibs
    if fib%2 == 0:
        sum += fib

    previous = current      #n-2
    current = fib           #n-1

Answer 4

Using a while loop with a counter is highly unidiomatic, you should use itertools.count for conciseness.

Some code, as my answer could be considered ambiguous:

def sum_fib():
    sum = 0
    for i in itertools.count():
        ith_fib = fib(i)
        if (ith_fib > MAX_LIMIT):
            return sum
        if (ith_fib % 2 == 0):
            sum += ith_fib
    return sum