Categories

Adding Even Numbers from the Fibonacci Sequence – Python

Problem 2 from the Project Euler website.

The Problem

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.

My Solution

First, lets get the sequence going

This is pretty much what we need

a   b   c
0 + 1 = 1

a   b   c
1 + 1 = 2

a   b   c
1 + 2 = 3

...

So we can easily do that with this

# where we set a and b, and
# x is our counter.
a,b,x=0,1,0

# We only want the first 10
# numbers to make sure it works
while x<10:
print a,
# This is the Fibonacci bit
c=a+b
a,b=b,c
# Done? cool, next number please.
x=x+1

That returns

0, 1, 2, 3, 5, 8, 13, 21, 34,

So we know it works!

Now we need to get just the even numbers.

This we can do by seeing if they are multiples of 2, with the conditional a % 2 == 0

a,b,x=0,1,0
while x<10:
# If you can divide 'a' by two
# without getting a remainder,
# then I'm interested.
if a % 2 == 0:
print a,
c=a+b
a,b=b,c
x=x+1

This returns

0 2 8 34

Excellent…it works!

Now we need to add them all up, so we make another variable called answer.

while x<10:
if a % 2 == 0:
c=a+b
a,b=b,c
x=x+1

Which returns

44

PERFECT! Almost there.

The idea is to add all the even numbers under 4,000,000

so we don’t need the x counter and instead we set the loop to check that the value of a does not exceed 4m.