Fibonacci under 4 millions!

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

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

Answer 2

The loop condition is wrong, it should be something like this:

while True:
    Fibonacci1 = Fibonacci1 + Fibonacci2
    if Fibonacci1 % 2 == 0:
        if a + Fibonacci1 > 4000000:
            break
        a = a + Fibonacci1
    Fibonacci2 = Fibonacci1 + Fibonacci2
    if Fibonacci2 % 2 == 0:
        if a + Fibonacci2 > 4000000:
            break
        a = a + Fibonacci2

Answer 3

Currently, you sum up all the first 2 million even Fibonacci numbers.

But that is not the task. You have to sum all even Fibonacci numbers that are below 4 million.

Answer 4

I don't exactly understand your algorithm, but it seems that smerriman has a point, 4000000 Fibonnacci sequence numbers would surely grow above 4M. I guess that the faster approach would be to generate sequence up to 4M, then adding up the even ones.

Answer 5

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(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 6

NOTE: This has been heavily modified to address the actual question

Here's an alternate (and very fast, but untested, method). It relies on a few properties:

1. Each Fibonacci number can be calculated directly as floor( pow( phi, n ) + 0.5 ) (See Computation by Rounding in http://en.wikipedia.org/wiki/Fibonacci_number ). Conversely the index of the biggest Fibonacci number less than i is given by floor( log(i*sqrt(5)) / log(phi) )
2. The sum of the first N Fibonacci numbers is the N+2th fibonacci number minus 1 (See Second Identity on the same wikipedia page)
3. The even Fibonacci numbers are are every third number. ( Look at the sequence mod 2 and the result is trivial )
4. The sum of the even Fibonacci numbers is half the sum of the odd Fibonacci numbers upto the same point in the sequence. (This follows from 3. and the property that F(3N) = F(3N-1) + F(3N-2) so F(3N-2) + F(3N-1) + F(3N) = 2 F(N) .. then summing both sides.

So convert our maximum value of 4000000 calculate the index of the highest Fibonacci number less than it.

int n = floor(log(4000000*sqrt(5))/log(phi)) = 33. 

33 is divisible by 3 so it is an even Fibonacci number, if it wasn't we'd need to adjust n like this.

n = (n/3)*3

The sum of all Fibonacci numbers up to this point if given by

sum = floor( pow( phi, n+2 ) + 0.5 ) - 1 = 9227464

The sum of all even numbers is half of this:

sum_even = 4613732

Nice thing about this is that its an O(1) (or O(log(N)) if you include the cost of pow/log) algorithm, and works on doubles.. so we can calculate the sum for very large values.

Answer 7

Come on, the optimal way to compute Fibonacci sequence is using 2 tricks:

EDITED, sorry for earlier mistake

1:

N =|2 0 0|
   |1 0 0|
   |0 0 0|

M =|3 2 1|
   |2 1 0|
   |0 0 1|

Matrix N*M^(n/3) has sum of first n fibonacci numbers (filtered only to the even ones) is the upper right element.

2:

You can use http://en.wikipedia.org/wiki/Exponentiation_by_squaring, because matrix multiplication is a ring.

So you can solve our problem in O(log n)

Answer 8

There are other tricks that make this more efficient than simply computing the complete list of Fibonacci numbers, and then summing the even numbers in the list.

I would, IF it were me trying to solve this problem, make a list of the even Fibonacci numbers. Are there any interesting characteristics of that list? Can you convince yourself that this pattern holds true in general?

Next, I might look for a way to compute the members of that list, and only those elements that are needed. I might even look to see if there are any formulas to be found that yield the sum of a sequence of Fibonacci numbers.

Of course, all of this would take up more of your own time than simply coding up the brute force solution, but Project Euler is all about finding the pretty solution rather than the brute force solution. In the end, if you have learned something about mathematics, about computation, then you have gained.

Answer 9

You may be interested in knowing about the The On-Line Encyclopedia of Integer Sequences!

You can search information by name or by sequence.

If you search either for 0,2,8,34 or 'Even Fibonacci' you will be redirect to sequence A014445

There you you find lots of information including formulas,
from that to code a generator that will yield the even fibonacci numbers directly is easy.

def evenfib():
    """ Generates the even fibonacci numbers """
    a, b = 2, 0
    while True:
        a, b = b, a+4*b
        yield a  

Answer 10

## nice simple generator Mark Byers
def fib():
    a = b = 1
    while True:
        yield a
        a, b = b, a + b

## does same as takewhile 5
for fibonacci in zip(range(1,1+5),fib()):
    print "fib(%i) = %i" %  fibonacci

## we can slice to take every second
print "even sequence upto 100th"
total=0
for fibonacci in zip(range(1,1+100),fib())[::2]:
    print "fib(%i) = %i" %  fibonacci
    total+=fibonacci[1] ## to double check
print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[::2] ),'that is ',total

print "odd sequence upto 100th"

total=0
for fibonacci in zip(range(1,1+100),fib())[1::2]:
    print "fib(%i) = %i" %  fibonacci
    total+=fibonacci[1] ## to double check

print "Has sum: ", sum( b for a,b in zip(range(1,1+100),fib())[1::2] ),'that is ',total