Project Euler #2 in "Python"

Question

I am an absolute beginner here. I was giving the questions on Project Euler a try in Python. Can you please point out where does my code go wrong?

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

def fib(a):
    if ((a==0) or (a==1)):
        return 1
    else:
        return((fib(a-1))+(fib(a-2)))
    r=0
    sum=0
    while (fib(r))<4000000:
        if(((fib(r))%2)==0):
            sum+=fib(r)
            print(sum)

Answer 1

Your code isn't wrong, it's just too slow. In order to solve Project Euler problems, not only does your code have to be correct, but your algorithm must be efficient.

Your fibonacci computation is extremely expensive - that is, recursively trying to attain the next fibonacci number runs in O(2^n) time - far too long when you want to sum numbers with a limit of four million.

A more efficient implementation in Python is as follows:

x = 1
y = 1
z = 0
result = 0

while z < 4000000:
   z = (x+y)         
   if z%2 == 0:
       result = result + z

   #next iteration

   x = y
   y = z

print result

Answer 2

this definetly is not the only way- but another way of doing it.

def fib(number):
    series = [1,1]
    lastnum = (series[len(series)-1]+series[len(series)-2])
    _sum = 0
    while lastnum < number:
        if lastnum % 2 == 0:
            _sum += lastnum
        series.append(lastnum)
        lastnum = (series[len(series)-1] +series[len(series)-2])
    return series,_sum

Answer 3

You should use generator function, here's the gist:

def fib(max):

    a, b = 0, 1

    while a < max:

        yield a

        a,b = b, a+b

Now call this function from the shell, or write a function after this calling the fib function, your problem will get resolved.It took me 7 months to solve this problem

Answer 4

This is probably the the most efficient way to do it.

a, b = 1, 1
total = 0
while a <= 4000000:
    if a % 2 == 0:
        total += a
    a, b = b, a+b  
print (total)

Answer 5

Using recursion might work for smaller numbers, but since you're testing every case up to 4000000, you might want to store the values that you've already found into values. You can look for this algorithm in existing answers.

Another way to do this is to use Binet's formula. This formula will always return the nth Fibonacci number. You can read more about this on MathWorld.

Note that even numbered Fibonacci numbers occur every three elements in the sequence. You can use:

def binet(n):
     """ Gets the nth Fibonacci number using Binet's formula """
     return int((1/sqrt(5))*(pow(((1+sqrt(5))/2),n)-pow(((1-sqrt(5))/2),n)));

s = 0; # this is the sum
i = 3;
while binet(i)<=4000000:
    s += binet(i);
    i += 3; # increment by 3 gives only even-numbered values

print(s);

Answer 6

You may try this dynamic program too, worked faster for me

dict = {}
def fib(x):
    if x in dict:
        return dict[x]
    if x==1:
        f = 1
    elif x==2:
        f = 2
    else:
        f = fib(x-1) + fib(x-2)
    dict[x]=f
    return f

i = 1
su = 0
fin = 1

while fin < 4000000:
    fin = fib(i)
    if fin%2 == 0:
        su += fib(i)
    i+=1

print (su)

Answer 7

As pointed in other answers your code lacks efficiency. Sometimes,keeping it as simple as possible is the key to a good program. Here is what worked for me:

    x=0
    y=1
    nextterm=0
    ans=0
    while(nextterm<4000000):
        nextterm=x+y
        x=y
        y=nextterm
        if(nextterm%2==0):
            ans +=nextterm;
    print(ans)

Hope this helps. cheers!

Answer 8

it is optimized and works

def fib(n):
    a, b = 0, 1
    while a < n:
        print(a, end=' ')
        a, b = b, a+b
    print()
fib(10000)

Answer 9

This is the slightly more efficient algorithm based on Lutz Lehmann's comment to this answer (and also applies to the accepted answer):

def even_fibonacci_sum(cutoff=4e6):
    first_even, second_even = 2, 8
    even_sum = first_even + second_even
    while even_sum < cutoff:
        even_fib = ((4 * second_even) + first_even)
        even_sum += even_fib
        first_even, second_even = second_even, even_fib
    return even_sum

Consider the below Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Every third element in the Fibonacci sequence is even.

So the even numbers in the above sequence are 2, 8, 34, 144, 610, ...

For even number n, the below equation holds:

n = 4 * (n-1) + (n-2)

Example:

• 34 = (4 * 8) + 2, i.e., third even = (4 * second even) + first even
• 144 = (4 * 34) + 8, i.e., fourth even = (4 * third even) + second even
• 610 = (4 * 144) + 34 i.e., fifth even = (4 * fourth even) + third even

Answer 10

İt's can work with If we know in how many steps we will reach 4000000. It's around 30 steps.

a=1
b=2
list=[a,b]
for i in range (0,30):
    a,b=b,a+b
    if b%2==0:
        list.append(b)
print(sum(list)-1)

Answer 11

Adapting jackson-jones answer to find the sum of the even-valued fibonacci terms below 4 million.

# create a function to list fibonacci numbers < n value
def fib(n):
    a, b = 1, 2
    while a < n:
        yield a
        a, b = b, a+b

# Using filter(), we extract even values from our fibonacci function
# Then we sum() the even fibonacci values that filter() returns 
print(sum(filter(lambda x: x % 2 == 0, fib(4000000))))

The result is 4613732.