Fibonacci under 4 millions [duplicate]

Question

Possible Duplicate:
Python program to find fibonacci series. More Pythonic way.

Hey, i was trying to write a script which sums all the even terms in "Fibonacci Sequence" under 4 millions.

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
i = 4
for i in range(1,4000000):
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

it should takes less than a minute, but it took all night and it wasn't solved !

---

Edit: Sorry guys, i misunderstood the problem. I though it means that i have to sum all the even terms UP TO 4 million ! But the solution was to sum all the even terms UNTIL 4 million.

Working code (finished in less than one second):

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
while a < 4000000:
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

Answer 1

There are a couple of problems with your code:

• You are looping four million times instead of until a condition is true.
• You have repeated code in the body of your loop.

Most people when they start learning Python learn only imperative programming. This is not surprising because Python is an imperative language. But Python also supports functional programming to a certain extent and for this sort of exercise a functional programming approach is more enlightening in my opinion.

First define a generator that generates all the Fibonacci numbers:

def fib():
    a = b = 1
    while True:
        yield a
        a, b = b, a + b

To use this generator we can import a few useful functions from itertools. To print the first few numbers use islice:

from itertools import ifilter, islice, takewhile

for x in islice(fib(), 5):
    print x

1
1
2
3
5

To find only the even numbers we can use ifilter to produce a new generator:

def is_even(x):
    return x % 2 == 0

evenfibs = ifilter(is_even, fib())

for x in islice(evenfibs, 5):
    print x

2
8
34
144
610

To fetch numbers from the generator until a number exceeds four million use takewhile:

for x in takewhile(lambda x: x < 4000000, evenfibs):
    print x

To solve the problem you can use sum:

sum(list(takewhile(lambda x: x < 4000000, evenfibs)))

I hope this shows that a functional programming approach is not difficult and is a more elegant way to solve certain types of problem.

Answer 2

Are you sure it is i that you want to be less than 4 million?