Python program to find fibonacci series. More Pythonic way.

Question

There is another thread to discuss Fibo series in Python. This is to tweak code into more pythonic. How to write the Fibonacci Sequence in Python

I am in love with this program I wrote to solve Project Euler Q2. I am newly coding in Python and rejoice each time I do it The Pythonic way! Can you suggest a better Pythonic way to do this?

Project Euler Q2. Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

fib=[]
def fibo(a=-1,b=1,upto=4000000):
    if a+b>=upto:
        return
    else:
        a,b=b,a+b
        fib.append(b)
        fibo(a,b)

fibo()
even=[i for i in fib if not i%2]
print sum(even)

Answer 1

For one thing, I would suggest summing up the terms as you calculate them rather than storing them in an array and summing the array afterwards, since you don't need to do anything with the individual terms other than adding them up. (That's just good computational sense in any language)

Answer 2

I would make the following changes:

• Use iteration instead of recursion
• Just keep a running total instead of keeping a list of all Fibonacci numbers and then finding the sum of the even ones a posterior

Other than that, it's reasonably Pythonic.

def even_fib_sum(limit):
    a,b,sum = 0,1,0
    while a <= limit:
        if a%2 == 0:
            sum += a
        a,b = b,a+b
    return sum

print(even_fib_sum(4000000))

Answer 3

Using generators is a Pythonic way to generate long sequences while preserving memory:

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

import itertools
upto_4000000 = itertools.takewhile(lambda x: x <= 4000000, fibonacci())
print(sum(x for x in upto_4000000 if x % 2 == 0))

Answer 4

First I'd do fibo() as a generator:

def fibo(a=-1,b=1,upto=4000000):
    while a+b<upto:
        a,b = b,a+b
        yield b

Then I'd also select for evenness as a generator rather than a list comprehension.

print sum(i for i in fibo() if not i%2)

Answer 5

I'd use the fibonacci generator as in @constantin' answer but generator expressions could be replaced by a plain for loop:

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

sum_ = 0
for f in fibonacci():
    if f > 4000000:
       break
    if f % 2 == 0:
       sum_ += f

print sum_

Answer 6

Here's an alternate direct 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.

Point 4 can be seen from this:

Sum of first 3N fibonacci numbers
   =(F(1) + F(2))+ F(3) +(F(4) + F(5))+ F(6) + ... +(F(3N-2) + F(3N-1))+ F(3N) 
   =     F(3)    + F(3) +     F(6)    + F(6) + ... +       F(3N)       + F(3N)
   = 2( F(3) + F(6) + ... + F(3N) )
   = 2 ( Sum of odd fibonacci numbers up to F(3N) )

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 = sum/2; // ( = 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.

NOTE: I edited and moved this answer from a closed duplicate of this question. http://stackoverflow.com/questions/3270863