Using Python Modulo Operator to Sort List

Question

I've been working on the Project Euler problems to try and learn python and I wrote a solution to the second problem (find the sum of even-valued terms in the Fibonacci sequence that do not exceed four million). The code gives me the correct solution, but it requires me to use modulus division twice in order to remove the odd-numbered values from the list of fibonacci numbers I generated. Here is the solution I wrote:

term_1 = 1
term_2 = 2
fibonacci_list = [1]
while term_2 < 4000000:
    fibonacci_list.append(term_2)
    term_1, term_2 = term_2, term_1 + term_2
for num in fibonacci_list:
    if num % 2 != 0
        fibonacci_list.remove(num)
for num in fibonacci_list:
    if num % 2 != 0
        fibonacci_list.remove(num)
return sum(fibonacci_list)

If I only put in one for-loop, the list fibonacci_list becomes the following:

[2, 5, 8, 21, 34, 89, 144, 377, 610, 1597, 2584, 6765, 10946, 28657, 46368, 121393, 196418, 514229, 832040, 2178309, 3524578]

Shouldn't all the odd numbered terms fail the modulus division test and be removed? Why do I need to run the for loop twice to remove all odd numbered terms?

score 3 · Accepted Answer · edited May 23 '17 at 12:04

I imagine the problem you are facing is that you are attempting to remove items from a list while iterating over the list.

See here, here and here for previous questions on this same topic.

For the sake of discussion, let's assume this is in fact the problem, and let's assume that it is forbidden to remove items from a list while iterating over it.

What could you do differently that would result in you not needing to remove items from a list while iterating over it? I'm not sure if you want to be given the answer outright or not since you are doing Project Euler, so I will refrain from giving out any obvious answers.

score 1 · Answer 2 · answered Jun 30 '11 at 20:43

Only looked at this briefly but it looks like you are mutating the collection that you are iterating through, i.e. as you remove items, the pointer to the current item/next item will be affected and certain items may be skipped on the first pass through.

score 0 · Answer 3 · answered Dec 01 '12 at 20:25

0

This remembers me the sieve of Eratosthenes. So I would like to propose this solution, which suppose converting your list to an array:

fibonacci_list = fibonacci_list [ fibonacci_list % 2 != 0  ]

answered Dec 01 '12 at 20:25

Tengis

2,721
10
36
58

score 0 · Answer 4 · edited May 23 '17 at 11:55

0

It's not hard to see that only every 3rd term of the fibonacci sequence is even. You could use that instead.

In any case, you fell into the classic trap of mutating a sequence while iterating over it. Don't do that, do this:

fibonacci_list[:] = [x for x in fibonacci_list if x%2==0]

edited May 23 '17 at 11:55

Community

1
1

answered Jun 30 '11 at 20:44

Jochen Ritzel

104,512
31
200
194

1

You can just do fibonacci_list = [x for x in fibonacci_list if x%2==0] since the list comprehension creates a new list anyway. – Peter Collingridge Jun 30 '11 at 20:53

score 0 · Answer 5 · answered Jun 30 '11 at 20:58

Compare your program to this. It might help.

fibonacci = [1,2]
num = 3
while num < 4000000:
    fibonacci.append(num)
    len_ = len(fibonacci)
    num = fibonacci[len_-2] + fibonacci[len_-1]

sum = 0
for num in fibonacci:
    if num%2 == 0: sum += num

print sum

I don't understand why are you unnecessary removing the odd numbered entries from the list. Just add the even numbered ones that's it.

Using Python Modulo Operator to Sort List

5 Answers5