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)

exact dupe: http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python — Kenan Banks, Feb 23 '09 at 16:57
Corrected. When editing, everything showed up correct, seems it was some SO formatting error. — schnaader, Feb 23 '09 at 17:04
Or some othere people that were editing it a bit later... however, it works now :) — schnaader, Feb 23 '09 at 17:05

score 15 · Answer 1 · answered Feb 23 '09 at 17:02

15

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))

answered Feb 23 '09 at 17:02

Constantin

26,638
10
58
79

Blegh, I want to yell for the stupid use of forward-compatible code (2to3 exists for a reason), but at the same time itertools.takewhile is the right way to do it. So since the 3.x thing is a minor issue, +1 it is. – Devin Jeanpierre Jan 11 '10 at 12:28

score 14 · Accepted Answer · answered Feb 23 '09 at 17:02

14

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)

answered Feb 23 '09 at 17:02

Jorenko

2,496
1
21
25

score 4 · Answer 3 · answered Feb 23 '09 at 16:56

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)

score 2 · Answer 4 · answered Feb 23 '09 at 17:00

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))

answered Feb 23 '09 at 17:00

Adam Rosenfield

375,615
96
501
581

I prefer recursion wherever possible. ;) Isn't it Pythonic? – lprsd Feb 23 '09 at 17:09

score 1 · Answer 5 · edited May 23 '17 at 10:32

Here's an alternate direct method It relies on a few properties:

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) )
The sum of the first N Fibonacci numbers is the N+2th fibonacci number minus 1 (See Second Identity on the same wikipedia page)
The even Fibonacci numbers are are every third number. ( Look at the sequence mod 2 and the result is trivial )
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. Fibonacci under 4 millions

score 1 · Answer 6 · edited May 23 '17 at 10:32

1

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_

edited May 23 '17 at 10:32

Community

1
1

answered Feb 23 '09 at 17:19

jfs

374,366
172
933
1,594

What is the benefit to doing this? – Asad Saeeduddin Mar 18 '13 at 05:06
@Asad: It is a matter of style. Some might find it to be more explicit and simpler to understand hence more readable. – jfs Mar 18 '13 at 05:34

score 0 · Answer 7 · answered Jul 01 '13 at 03:10

0

print ("Fibonacci Series\n")

a  = input ("Enter a nth Term: ")

b = 0 

x = 0

y = 1

print x,("\n"), y

while b <=a-2:

  b = b+1

  z = x + y

  print z

  x = y

  y = z

answered Jul 01 '13 at 03:10

Jawad Rajput

1
1

That looks more like "The most unPythonic way to find a Fibonacci sequence"! – Ken Y-N Jul 01 '13 at 03:34

score 0 · Answer 8 · answered Jun 28 '14 at 13:49

0

def main():
    a = 1
    b = 2
    num = 2

    while b < 4000000:
        a, b = b, a+b
        num += b if b % 2 == 0 else 0

    print num

if __name__ == '__main__':
    main()

answered Jun 28 '14 at 13:49

Alan Dong

3,771
36
35

score 0 · Answer 9 · answered Oct 25 '11 at 21:00

In Python 3 at least if you give a generator to the sum function it will lazily evaluate it so there is no need to reinvent the wheel.

This is what @Constantin did and is correct.

Tested by comparing the memory usage of using generators:

sum(range(9999999))

compared with not doing so:

sum(list(range(9999999)))

The one with the generator does not cause memory exceptions with higher numbers either.

Python program to find fibonacci series. More Pythonic way

9 Answers9

Linked

Related