# Project Euler #2 - Even Fibonacci numbers

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?
• Could you clarify what you mean by "fewer changing values on the left"? Sep 16, 2015 at 8:49
• @JanneKarila, yes! I mean if (1 <= n), here 1 is on left side. Sep 16, 2015 at 13:50
• I tackled this a long time ago using the Golden Ratio - here's a link to the blog post which details the solution. The basic principle is that the nth Fibonacci number is the closest integer to (1/Sqrt(5))*(Golden_Ratio^n); generating even a long list of Fibs from that is very fast and consequently fast to sum the even fibs directly - no caching. It's in F# but easily adaptable to Python. Sep 16, 2015 at 14:14

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



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



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 an = an-1 + an-2, we have an = 4an-1 + an-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


• Just one thing, I don't why but if you see in the description above the sequence contains only single 1 in the start i.e. 1, 2, 3, 5.... This confused me a bit. Sep 16, 2015 at 13:49
• Hmm, but that's confusing. Anyways I am really surprised about jumping into the very first solution, it will be good if I can analyze other solutions as well :( Sep 16, 2015 at 14:04
• Np, I got it. I think the sequence must respect the finonacci rule, it doesn't matter the starting point. Sep 16, 2015 at 15:31
• Hmm, now I have one problem. Why we are doing everything in just one function. We are supposed to divide responsibility right? Sep 17, 2015 at 4:17
• Yes, you are right. But how would I know if I am over engineering. How do you know when to draw the line? because I find that thinking in terms of small function helps me a lot to solve some problem. Sep 17, 2015 at 17:19

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.

• Just asking, why using dictionary is not preferred? is it the hashing time that matters? Sep 16, 2015 at 14:06
• Also, ith_fib seems perfectly fine name. The first thing that comes to your mind is that its some ith term of the sequence which is good. Sep 16, 2015 at 14:07
• Dictionaries are optimised for keywords, but lists are optimised for a sequence of integers. You have the latter so it makes sense to use the type optimised for it. ith confused me because I read it as a word rather than separating i and th. Sep 16, 2015 at 14:31
• If one is using a list to store the Fibonacci numbers, it would be clearer to populate it from bottom up (with a loop instead of recursion). Sep 17, 2015 at 5:38
• @JanneKarila That's definitely true, I actually got that feedback on something I posted, I was mostly just improving upon what the OP had. You're right that I should have noted the better approach though, I'll remember to do that in future even if I'm not going into detail on it. Sep 18, 2015 at 9:07

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

• Basically you are saying to use an iterative solution. But I wanted to learn recursive algorithms :) Sep 16, 2015 at 14:08
• @CodeYogi Fibonacci isn't really a good example to learn recursion. Dynamic programming for sure.
– sam
Sep 16, 2015 at 14:28
• @CodeYogi Tower of Hanoi for recursion Sep 16, 2015 at 18:29
• @Caridorc ya that's a well known example. But! what about thinking of our own, solving new problems? can just Tower of Hanoi enable us to solve any problem including recursion? I doubt. Sep 17, 2015 at 4:12
• Also, if I see you are mixing concerns, ideally one function should calculate nth Fib term and second should sum the terms, Sep 17, 2015 at 4:16

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