More efficient solution for Project Euler #2 (sum of Fibonacci numbers under 4 million)

Question

I would like to get some feedback on my code. I am starting to program after doing a few online Python courses.

Would you be able to help me by following my track of thinking and then pinpointing where I could be more efficient? (I have seen other answers but they seem to be more complicated than they need to be, albeit shorter; but perhaps that is the point).

Question:

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.

fibValue = 0
valuesList = []

a = 0
b = 1

#create list

while fibValue <= 4000000:
    fibValue = a + b
    if fibValue % 2 == 0:
        valuesList.append(fibValue)
    a = b
    b = fibValue

print (valuesList) #just so that I can see what my list looks like after fully compiled

print() #added for command line neatness

print() #added for command line neatness

newTot = 0

for i in valuesList:
    newTot += i
print (newTot)

Answer 1

A hint that I always offer people with this specific question. Take a look at the first few numbers of the sequence - I have set the even ones in bold:

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

Can you see a pattern in the spacing? Can you explain (ideally, prove) it?

Given that, can you think of a way to generate even Fibonacci numbers directly, instead of filtering through for them? (Hint: start with (1,2), and try to generate (5,8) in one step, then (21, 34) etc. Do some algebra and figure out how to apply multiple iterations of the generation rule at once.)

Anyway, in terms of doing the actual calculation with the numbers, there are more elegant approaches. Instead of asking Python to build a list directly, we can write a generator:

def even_fibonacci_up_to(n):
    a, b = 1, 2
    while b <= n:
        yield b # since 2 qualifies, after all.
        # Now calculate the next value.
        # math from the first step goes here when you figure it out!

Notice the use of the yield keyword. This lets us treat our expression even_fibonacci_up_to(4000000) as a special sort of sequence whose elements are generated on-demand. Unlike with ordinary functions which can only return once. :) (Using return inside a generator terminates the whole process of yielding values when it is reached.)

And instead of looping through this sequence to add up the numbers, we can use the built-in sum function:

sum(even_fibonacci_up_to(4000000))

Answer 2

Your method isn't bad though it could be cleaned up and I have a faster and more straight forward suggestion, say using a simple class.

• Karl Knechtel's method appears to create a near infinite loop.
• Madison May's recursion method reaches a "RuntimeError: maximum recursion depth exceeded" beyond an input of 40. But the 3rd solution they suggest appears to execute without error but the output appears inaccurate... I believe you are only getting the largest number, idk. Mine is similar.

I think this is your best, most accurate, and simplest (also fastest given a correct solution):

def fib(n):   # return Fibonacci series up to n
    result, a, b = list(), 0, 1 # set variables
    result.append(0) # Initial Fibonacci Zero
    while b < n:
        if b % 2 == 0:
            result.append(b)
        a, b = b, a+b
    return result

def fibSum(n):
    return sum(map(int, fib(n)))

print(fibSum(4000000))

Hope this helps. Good luck!

P.S. Also, I would recommend using '\n' for new line when printing for code cleanness, there's no need for several print statements but we all start somewhere and I've only been programming Python for about a year myself but I also have other languages in my background and I read a lot. A few key notes: map allows you to easily sum up a list of ints/truple and you can use sum instead of incrementing through a list and adding it up, it should be faster in 'almost' all cases (strings are a different story). Again, good luck!

P.P.S. I kept your mod 2, modulus is your friend. Modifying built in perimeters is not your friend, if you have to do that, odds are you're doing something wrong. Just food for thought.

Benchmarks:

Your Code:
Output: 4613732
Total Run Time: 0.000175 seconds in Python
Total Run Time: 0.000069 seconds in Pypy

My Suggestion:
Output: 4613732
Total Run Time: 0.000131 seconds in Python
Total Run Time: 0.000053 seconds in Pypy

Edit: Alternatively, you could just use this:

def fib2(n):
    result, a, b = 0, 0, 1
    while b < n:
        if b % 2 == 0:
            result += b
        a, b = b, a+b
    return result

print(fib2(4000000))

I personally prefer for whatever reason to have the Fibonacci actually functional on it's own as apposed to building a single purpose class. Obviously it should be slightly faster but I haven't tested it.

Answer 3

The Fibonacci sequence is a problem that's very well suited for a recursive solution. If you haven't yet learned about recursion, I would highly recommend it, as it provide a whole new way of looking at problems.

To find the nth Fibonacci number, you could use something like the following.

def fibonacci(n):
    if n < 2: return n
    return fibonacci(n-1)+fibonacci(n-2)

fibonacci(10) # returns 55

The reason that this answer is so clean is because it's framed in the same way that the fibonacci sequence is framed. To find one fibonacci number, you simply need to know the previous two.

That being said, recursion does introduce some interesting issues. To find the 100th fibonacci number it takes a surprising amount of time. Often problems like these require caching for recursion to be efficient.

What if we approached the problem from the opposite direction? Instead of starting from the top and working our way down, we could start from the bottom and work our way up. State is then stored in the arguments of the function.

def fibonacci(a, b, n):
    if n < 3: return a + b
    return fibonacci(b, a+b, n-1)

fibonacci(0, 1, 10) # returns 55

I hope you've enjoyed this little taste of recursion. Let me know if anything is unclear, and I'll be glad to help clear things up. However, if efficiency is your goal, Python's recursion might not be the best.

If recursion isn't your thing, or if you're intending to calculate very large fibonacci numbers, you might want an iterative solution (in fact, your own solution is pretty good). An iterative solution works especially well if you're looking for the largest fibonacci number less than n.

def fibonacci(n):
    # finds the largest fibonacci number less than n
    a, b = 0, 1
    while(a+b) < n:
        a, b = b, a+b
    return b

Answer 4

Optimizations

Eliminate the list

The first and most important optimization is to not use a list:

• There's no need to remember each even Fibonacci number; the sum is what we ultimately care about, and we can just add each even Fibonacci number onto the sum as we go along, then forget about that even Fibonacci number
• It takes time to create, store numbers into, retrieve numbers out of, and increase the size of (when you need to go beyond the current list capacity) the list
• It takes time to delete the list later on

Eliminate the check for evenness

Much less important is that you don't need to check for evenness because even Fibonacci numbers come exactly every three Fibonacci numbers. You can just blindly add every third Fibonacci number onto the sum with no check for evenness. This is because:

• Odd + even = odd, so the next Fibonacci after an even is odd
• Even + odd = odd, so the next Fibonacci after that is also odd
• Odd + odd = even, so the next Fibonacci number after the two odds is even again
• The cycle then repeats

Algorithm

• Start with the first even Fibonacci number
• While the current even Fibonacci doesn't exceed your limit:
  • Add it to your sum
  • Skip ahead to the third Fibonacci number after that, which will be the next even Fibonacci number
• Return the sum

def solve(limit):
    sum = 0
    a = 2
    b = 3
    while a <= limit:
        sum += a
        c = a + b
        d = b + c
        e = c + d
        a = d
        b = e
    return sum

Simplified algorithm

Since a and b are just filled in with d and e, we can carefully simplify away those extra variables:

def solve(limit):
    sum = 0
    a = 2
    b = 3
    while a <= limit:
        sum += a
        c = a + b
        a = b + c
        b = c + a
    return sum