Sum of even fibonacci numbers below 4 million - Python

Question

I'm attempting the second Project Euler question in python and want to understand why my code doesn't work.

This code finds the sum of even Fibonacci numbers below 4 million

counter = 2
total = 0
while counter <= 4000000:
    if counter % 2 == 0:
        total+= counter    
    counter+= (counter -1)
print total

This code will output: 2

If I print the counter it outputs: 4194305

I'm assuming it's an issue with the if statement being executed as the while loop is functioning correctly and the counter is also incrementing correctly.

Solution 1

The problem is in the line counter+= (counter -1). You add it to itself (minus 1) while you should be doing this:

a, b = 1, 1
total = 0
while a <= 4000000:
    if a % 2 == 0:
        total += a
    a, b = b, a+b  # the real formula for Fibonacci sequence
print total

Solution 2

The series your code calculates for counter is as follows:

2 # solid start
3 # good
5 # this is going great
9 # wait, what?
17 # this is going really badly

You can't just add counter - 1 each time, you need to add the previous number in the series.

So why is your total so small? Because an odd number minus one is always even, and an odd number plus an even number is always an odd number; 2 is the only even number you ever generate, hence that is your total.

Generating the Fibonacci numbers is typically done with two variables a and b, where we start

a = b = 1

and each iteration looks like:

a, b = b, a + b

Solution 3

If you watch closely, you'll see the following sequence:

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

The formula for mapping the Fibonacci sequence is:

And you only want the sum of the even numbers such as:

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

So you can map a new formula such as:

And you will obtain the following sequence:

2 8 34 144 ...

Code example (Go):

package main

import "fmt"

func fibonacci() func() int {
    first, second := 0, 2
    return func() int {
        ret := first
        first, second = second, first+(4*second)
        return ret
    }
}

func main() {
    sum := 0
    f := fibonacci()
    for i := 0; sum < 4000000; i++ {
        sum += f()
    }
    fmt.Println(sum)
}

In that case you will not need the if conditionals.

Hope that helped you! Cheers!

Solution 4

Well I have tried this way:

fib_num = [0 ,1]
for i in range(2, 4*10**6):
    fib_num.append(fib_num[i-1] + fib_num[i-2])

def even_fib(fib_num):
    result = 0
    result = result + sum([even for even in range(0, fib_num) if even % 2 == 0])
print result

Whats wrong with that? It is taking too long to respond for script and giving 'killed' error

Solution 5

Here is my Python solution using the XOR gate. I have initialized the first two values and then in each iteration, I am storing the state of the previous two numbers. The theory is that sum of two numbers will be even only when both the numbers are either odd or even.

a = 1
b = 2

a_state = 1 #odd = 1 
b_state = 0 #even = 0

sum = b
output = []
while (a+b) < 1000:
    c = a+b
    a = b
    b = c
    
    if (a_state ^ b_state) == 0:
        sum += c
        a_state = b_state
        b_state = 0
    else:
        a_state = b_state
        b_state = 1
print(sum)

View more solutions