Project Euler: #2 in Python

Question

The problem presented is as follows:

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.

I have tried a few variations on the code you see below. I am currently getting the number 2,435,424 as the answer from the code I have written, however Project Euler is saying that number is incorrect. I have tried changing looking in to reasons my code is failing, and I'm stumped. Any advice would be appreciated. Code is as follows:

fibonacci = [2]

i = 0

number_1 = 1
number_2 = 2
number_3 = 0

while (number_3 <= 4000000):
    number_3 = number_1 + number_2
    fibonacci.append(number_3)

    if i % 2 != 0:
        number_1 = number_3
        i += 1
    elif i % 2 == 0:
        number_2 = number_3
        i += 1

total = 0

for numbers in fibonacci:
    if numbers % 2 == 0:
        total += numbers

print total

Answer 1

def EvenFibonacciNumbersSum(n):
    a = 1
    b = 2
    temp = 0
    sum =0
    while(a<=n):
        if(a%2 ==0):
            sum = sum + a
        #print(sum)
        temp = a
        a = b
        b = temp+b
    return sum

if __name__ == '__main__':
  print(EvenFibonacciNumbersSum(4000000))

Answer 2

You replace number_2 on the first iteration. That is not correct.

There is no need to evaluate an extra if in this case! an integer %2 is either 0 or 1, so use else. On top of that using if/else doesn't make much sense here, you could just do a rotation instead. Try doing it by hand and you'll see.

Project Euler is more about learning to find the solution with good code and shortcuts (4 million was originally a lot and couldn't be acquired through a bad recursion that goes through both branches). So I will not include the exact solution to any Project Euler question here but point you into the right direction instead. I highly suggest learning about python generators (see dawg's answer), since this is the easiest example to learn and understand them.

Also, it would be best to keep the running total inside your main loop so you don't have to go through them again.

Note regarding Project Euler: Python is not restricted with respect to integers (you can have infinite precision if you want) so some of the questions will not make as much sense. Also, RAM and CPU have increased exponentially; so consider doing this problem with 4 billion instead of 4 million and you will learn much more. That's where a useless elif could be expensive, and looping over something twice even worse because you have to keep track of the whole structure. Think of it this way: can you solve the problem without keeping more than the bare-necessary variables in memory? That's where generators, xrange, etc come in very handy (python 2.x).

Answer 3

Consider the many ways you can write a Fibonacci sequence in Python.

The most 'Pythonic', IMHO, is a generator:

def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b

You can modify that with the limit and the test of a % 2:

def Fib_in_even(lim):
    a, b = 0, 1
    while a < lim:
        if not a % 2:         
            yield a
        a, b = b, a + b

Then use sum to add up the modified Fibonacci series to 'the answer':

>>> sum(Fib_in_even(4000000))  
the_answer...

Answer 4

def FibSeries(first,second):
    yield first
    while True:
        first,second = second,first+second
        yield first

fib_lt_4mil = itertools.takewhile(lambda n:n<4000000,FibSeries(1,1))
even_fib_lt_4mil = [n for n in fib_lt_4mil if n%2 == 0]
print sum(even_fib_lt4mil)

at least I think

Answer 5

You're mixing doing the sum that project euler is asking for and the actual calculation of the fibonacci numbers. In the process of mixing this, you mess up both halves.

Let's do it one at a time:

fibonacci = [1, 2]
number_1 = 1
number_2 = 2
number_3 = 3

while (number_3 <= 4000000):
    number_1, number_2, number_3 = number_2, number_3, number_1 + number_2
    fibonacci.append(number_3)

Now, we have a list of fibonacci numbers. Let's sum the even ones.

total = 0
for numbers in fibonacci:
    if numbers % 2 == 0:
        total += numbers

Or more simply:

total = sum(x for x in fibonacci if x % 2 == 0)

And you'll absolutely want to apply the advice in Peter DeGlopper's answer.

Answer 6

For one thing, your loop appends one value too many to your list. Consider what happens if number_3 equals 4 million. Your loop will then compute a new value of number_3, which will exceed 4 million because one of number_1 or number_2 will have just been set equal to number_3, and add it to your list. The same holds true for any number_3 such that number_3 <= 4000000 but number_3 + min(number_1, number_2) > 4000000, I'm just using 4 million as a value that easily demonstrates the error.

I make no comment on the general algorithm - working on that is part of the point of Project Euler. But it's worth considering what you might do if the end value were not 4 million, but something too large to keep all the Fibonacci terms in memory at once.