Python: Odd behavior with modulo operator

Question

The solution is probably rather simple, but I just can't figure it out. Here is the code, it's a simple fibonacci number generator. The goal is to sum up all even fibonacci numbers below 4,000,000.

My approach is to first generate all fibonacci numbers below 4,000,000, and then either: a) generate a new list ("even") with the even ones (this works fine) b) removing the odd ones from the list "all"

However, in the latter case, the output is, for reasons I don't understand, this: [2, 5, 8, 21, 34, 89, 144, 377, 610, 1597, 2584, 6765, 10946, 28657, 46368, 121393, 196418, 514229, 832040, 2178309, 3524578]

Any help is much appreciated. Thanks!

all = []
even = []

def fibonacci():
    a, b = 1, 2
    while a < 4000000:
        all.append(a)
        a, b = b, a + b
    print all

##Putting all the even fibonacci numbers in a different list and summing them up works fine
#    for i in all:
#        if i % 2 == 0:
#            even.append(i)
#    print even                   
#    print sum(even)


# But for some strange reason I can't figure out how to remove the odd numbers from the list
    for i in all:
        if i % 2 != 0:
            all.remove(i)

    print all
    print sum(all)

fibonacci()

Answer 1

This is a "gotcha" situation: you're removing items from a list while iterating the list, thus changing the list, causing your iteration to behave unexpectedly. Try this:

...
# But for some strange reason I can't figure out how to remove the odd numbers from the list
    for i in all[:]:
        if i % 2 != 0:
            all.remove(i)
...

This is what's called "slice" notation, and causes you to iterate a throwaway copy of the list so that your iteration is not affected by the all.remove() calls.

Answer 2

You cannot remove items from a list you iterate over. Python uses iterators, which only know the current index relative to the start of the list. When you remove items from the front of the list, the position of all elements change and you skip the next element.

You can avoid the problem in plenty ways, for example with generators:

def fibonacci():
    a, b = 1, 2
    while a < 4000000:
        yield a
        a, b = b, a + b

def even(seq):
    for item in seq:
        if item % 2 == 0:
            yield item

print sum(even(fibonacci()))