CODEWITHSUNDEEP
python
Will Munn
Will Munn

Reputation: 7947

Project Euler 2 python3

I've got, what I think is a valid solution to problem 2 of Project Euler (finding all even numbers in the Fibonacci sequence up to 4,000,000). This works for lower numbers, but crashes when I run it with 4,000,000. I understand that this is computationally difficult, but shouldn't it just take a long time to compute rather than crash? Or is there an issue in my code?

import functools

def fib(limit):
    sequence = []
    for i in range(limit):
    if(i < 3):
        sequence.append(i)
    else:
        sequence.append(sequence[i-1] + sequence[i-2])
    return sequence

def add_even(x, y):
    if(y % 2 == 0):
        return x + y
    return x + 0

print(functools.reduce(add_even,fib(4000000)))

Upvotes: 0

Views: 161

Answers (1)

interjay
interjay

Reputation: 110108

The problem is about getting the Fibonacci numbers that are smaller than 4000000. Your code tries to find the first 4000000 Fibonacci values instead. Since Fibonacci numbers grow exponentially, this will reach numbers too large to fit in memory.

You need to change your function to stop when the last calculated value is more than 4000000.

Another possible improvement is to add the numbers as you are calculating them instead of storing them in a list, but this won't be necessary if you stop at the appropriate time.

Upvotes: 3

Related Questions