Using Fibonacci Program to Sum Even Elements

Question

I am trying to solve the following using Python:

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.

So far, I have been able to generate the Fibonacci elements but in trying to sum the even elements, my code seems to stall. Here is the code below:

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    if n>1:
        return fib(n-1)+fib(n-2)

n=0
total=0

while fib(n)<=4000000:
    if fib(n)%2==0:
        total+=fib(n)

print(total)

Any suggestions would be welcome.

You have an infinite loop, `n` is never incremented up from zero. — miradulo, Apr 01 '15 at 15:30
also, dont recalculate recursively for each term like that. use a generator or something. — cmd, Apr 01 '15 at 15:35
possible duplicate of [Efficient calculation of Fibonacci series](http://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series) — greybeard, Apr 19 '15 at 17:36

miradulo · Accepted Answer · 2015-04-01T15:49:45.197

4

You have an infinite loop as n isn't ever incremented up from zero in your while loop. Additionally, why not sum your Fibonacci total as well as find the next Fibonacci value in the same while loop, like this:

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

Outputs:

edited Apr 01 '15 at 15:49

answered Apr 01 '15 at 15:34

miradulo

28,857
6
80
93

Sorry, I was just about to ask the same question, hence unchecking the answer. Thanks for the clarification. – David Clark Apr 01 '15 at 15:50

Steve Wilhelm · Answer 2 · 2015-04-01T16:38:27.110

since this looks like a homework assignment, I threw in some interesting Python

from math import sqrt
# Using Binet's formula
def fib(n):
    return int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))

def sum_even_terms(limit = 4000000):
    n = total = 0
    while True:
        term = fib(n)
        n += 1
        if term > limit: break 
        if term % 2 == 0:
            total += term
    return total

print sum_even_terms()

def is_nth_term_even(n):
    return (fib(n) % 2 == 0)

print is_nth_term_even(30)

Mark Dickinson · Answer 3 · 2015-04-01T17:05:26.730

Just for fun, here's a really short solution:

def fib_even_sum(limit=4*10**6):
    """Sum of the even Fibonacci numbers up to the given limit."""
    b, c = 1, 2
    while c <= limit:
        a = b + c; b = c + a; c = a + b
    return b // 2

print fib_even_sum()  # outputs 4613732

It's based on the following facts:

Every third Fibonacci number is even.
If Fib(n) is even, then the sum of the even Fibonacci numbers up to Fib(n) is equal to the sum of the odd Fibonacci numbers up to Fib(n) (because each even Fibonacci number is the sum of the two preceding odd Fibonacci numbers).
The sum of all Fibonacci numbers (even and odd) up to and including Fib(n) is Fib(n+2) - 1 (via an easy proof by induction).

So if Fib(n) is the last even number to be included in the sum, then the total you want is just (Fib(n+2) - 1) / 2.

Daniel · Answer 4 · 2015-04-01T16:06:34.420

0

You can also use a generator and add the numbers

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

f = fib()
total = 0
while total <= 4000000:
    current =  f.next()
    if current % 2 == 0:
        total += current

print total

edited Apr 01 '15 at 16:06

answered Apr 01 '15 at 15:53

Daniel

5,095
5
35
48

Using Fibonacci Program to Sum Even Elements

4 Answers4