Solving Project Euler #2 in Python

Question

I am attempting to do Project Euler problem #2. Which is:

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.

However the terminal window hangs when I use the following code with 4000000. Smaller numbers run ok. Is there something about this code that is really inefficient, hence the lagginess?

n = int(raw_input("Enter the start number: "))

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

def even_sum(fib_seq):
    seq = []
    seq = [next(fib_seq) for number in range(n)]
    seq = [number for number in seq if number % 2 == 0]
    return sum(seq)

def start():
    fib = fib_generator()
    even_sum = even_sum(fib)
    print even_sum

start()

Solve the problem on paper first, for a few small numbers. Compare the results with those from your code. — Colonel Panic
– Colonel Panic, Commented Jul 25, 2013 at 1:02
Also, I would change both seq = [...] lines to seq = (...) (or use ifilter and takewhile from itertools). That will create generators and avoid having to ever store the entire list at once in memory, which will make it slower for large input values. — Gustav Larsson
– Gustav Larsson, Commented Jul 25, 2013 at 1:15

jason · Accepted Answer · 2013-07-25 01:06:26Z

4

You have a bug. You're generating the first 4,000,000 Fibonacci numbers, but the problem statement only asks for those Fibonacci numbers whose values are not more than 4,000,000.

Since the Fibonacci numbers grow exponentially (F_n ~ 1.618ⁿ), you're generating some numbers with a very large number of digits (log₁₀ F_n ~ n / 5) and that will take an immense amount of time.

Fix the bug, and you'll be okay.

edited Jul 25, 2013 at 1:06

answered Jul 25, 2013 at 1:01

jason

243k35 gold badges436 silver badges532 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jh314 · Accepted Answer · 2013-07-25 01:04:32Z

2

You just need to add logic to stop when the next fibonacci number exceeds 4000000.

Also, I spy a potential problem with this line:

def start():
    fib = fib_generator()
    even_sum = even_sum(fib) #<--- right here
    print even_sum

It isn't good to have a variable name the same as the function name.

answered Jul 25, 2013 at 1:04

jh314

27.9k16 gold badges66 silver badges83 bronze badges

Comments

desired login · Accepted Answer · 2013-07-25 05:33:50Z

0

Yes, there is something inefficient in your code, you load a very long list into memory twice, with your two seq = ... statements. Why not try one generator expression rather than two list comprehensions? Also, you could alter your Fibonacci generator to stop at a certain number:

def fib_generator(n):
    a, b = 0, 1
    while a < n:
        yield a
        a, b = b, a + b

def even_sum(fib_seq):
    seq = (number for number in fib_seq if not number % 2)
    return sum(seq)

def start():
    n = int(raw_input('Enter max constraint: '))
    fib_seq = fib_generator(n)
    even_sum1 = even_sum(fib_seq)
    print even_sum1

start()

answered Jul 25, 2013 at 5:33

desired login

1,1338 silver badges16 bronze badges

Comments

Jacob.Kincaid · Accepted Answer · 2013-08-07 22:55:29Z

0

This ran pretty fast for me

lst = []
num1 = 1
num2 = 2
sum = 0
jump = 0
next = 0

while next<4000000:
    next = num1 + num2
    if next<4000000:
        if jump ==0:
            num1 = next
            jump = 1
        else:
            num2 = next
            jump = 0
        if next%2 == 0:
            lst.append(next)

for item in lst:
    sum+=item

print ''
print "Sum: ",
print sum

answered Aug 7, 2013 at 22:55

Jacob.Kincaid

925 bronze badges

Collectives™ on Stack Overflow

Solving Project Euler #2 in Python

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related