CODEWITHSUNDEEP
python
Evan Emolo
Evan Emolo

Reputation: 1670

Solving Project Euler #2 in Python

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

Upvotes: 1

Views: 598

Answers (4)

Jacob.Kincaid
Jacob.Kincaid

Reputation: 92

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

Upvotes: 0

desired login
desired login

Reputation: 1190

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

Upvotes: 0

jason
jason

Reputation: 241789

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 (Fn ~ 1.618n), you're generating some numbers with a very large number of digits (log10 Fn ~ n / 5) and that will take an immense amount of time.

Fix the bug, and you'll be okay.

Upvotes: 4

jh314
jh314

Reputation: 27812

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.

Upvotes: 2

Related Questions