Python: odd behavior with modular operator
The solution is probably pretty simple, but I just can't seem to figure it out. Here's the code, it's a simple fibonacci number generator. The goal is to sum 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) create a new list ("even") with even ones (this works great) b) remove the odd ones from the "all" list
However, in the latter case, the output, for reasons I don't understand, looks like 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 greatly appreciated. Thank!
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()
source to share
This is a "wish" situation: you remove items from the list while iterating over the list, thereby changing the list, causing your iteration to behave unpredictably. Try the following:
...
# 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 is called a "slice" entry, and forces you to iterate over the selected copy of the list, so your iteration is not affected by calls to all.remove ().
source to share
You cannot remove items from the list you are iterating over. Python uses iterators that only know the current index relative to the beginning of the list. When you remove items from the front of the list, the position of all items changes and you skip the next item.
You can avoid the problem in a variety of 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()))
source to share
If we closely observe how the iteration happens in the following code
for i in all:
if i % 2 != 0:
all.remove(i)
# Add these two lines for debugging..
# Or to know how this iteration functions
print "when %d: " %i
print all
print "Remaining Evens",
print all
This is what the output will look like if the maximum number is 100.
original series [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
when 1:
[2, 3, 5, 8, 13, 21, 34, 55, 89]
when 3:
[2, 5, 8, 13, 21, 34, 55, 89]
when 13:
[2, 5, 8, 21, 34, 55, 89]
when 55:
[2, 5, 8, 21, 34, 89]
Remaining Evens [2, 5, 8, 21, 34, 89]
Here, when python starts iterating over the list, it technically only remembers the position of the number it has to iterate from.
If we see a way out,
In the first iteration, it removes 1.
In the next iteration, he remembers that he should count the second position. The list now starts with "2". Thus, the second position is "3". Thus, he removes it.
In the next iteration, he remembers that he should count from the third position. Now in the current list the 3rd position is "8". So it counts from there .. NOT from "5". So, since 8 doesn't satisfy, it goes to 13 ..
Thus, he skips all these numbers.
How to fix it:
Actually, you need to make a copy of the "all" list and iterate over it. (It must not refer to the same object ..). If this happens, the same will happen.
you can do this simply by using the slice operators:
copy_all= all[:]
#or else, you need to use deepcopy()
import copy
copy_all = copy.deepcopy(all)
# you iterate copy_all but delete in all.
However, prefer the first method. Its very simple.
source to share