CODEWITHSUNDEEP
python-3.xwhile-loopfibonacci
newc00der
newc00der

Reputation: 3

Why no answer when trying to sum even Fibonacci numbers

I defined a function to calculate fibonacci numbers which works well.

Now I'm trying to add up all the even numbered fibonacci numbers <= n than are also <= 4000000 but I'm getting no output.

def fib_iterative(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

def sum_even_fibs(n):
    total = 0
    n = 0
    while fib_iterative(n) < 4000000:
        if fib_iterative(n) % 2 == 0:
            total += fib_iterative(n)
            n += 1
    return total

print(sum_even_fibs(10))
# 1,1,2,3,5,8,13,21,34,55. 
# 2 + 8 + 34 = 44

Upvotes: 0

Views: 78

Answers (3)

dangee1705
dangee1705

Reputation: 3520

Your code doesn't work because you are not doing it until n, you are doing it until 4000000.

You can combine both of your functions to create this.

def sum_even_fibs(n):
    a, b = 0, 1
    t = 0
    for i in range(n):
        a, b = b, a + b
        if a % 2 == 0:
            t += a
    return t

print(sum_even_fibs(10)) #44

as someone in the comments pointed out, every third number is even so you can compress this down to

def sum_even_fibs(n):
    a, b = 0, 1
    t = 0
    for i in range(n // 3):
        a, b = a + 2 * b, 2 * a + 3 * b
        t += a
    return t

print(sum_even_fibs(10)) #44

for the specific case where you don't want to do any numbers above 4000000, you can add this if statement

def sum_even_fibs(n):
    a, b = 0, 1
    t = 0
    for i in range(n // 3):
        a, b = a + 2 * b, 2 * a + 3 * b
        if a >= 4000000:
            print("the fibonacci numbers in this calculation exceed 4000000")
            return None
        t += a
    return t

Upvotes: 0

Patrick Haugh
Patrick Haugh

Reputation: 60974

Let's say you were just doing this up to n=5. You should be calculating five fibonacci numbers. Instead, you're calculating all of the fibonacci numbers up to the current one three times! For each n, you should call fib_iterative exactly once and reuse the result. You're also discarding the value of your n parameter.

def sum_even_fibs(n):
    total = 0
    for x in range(n):
        current = fib_iterative(x)
        if current > 4000000:
            break
        if not current % 2:
            total += current
    return total

This is still inefficient, because you're recalculating n-1 values of every time you call fib_iterative(n). Instead, a generator based solution will allow you to calculate each value only once.

from itertools import takewhile

def fib(n):
    x = 0
    y = 1
    for _ in range(n):
        yield x
        x, y = y, x+y

def sum_even_fibs(n):
    fibs = fib(n)
    evens = (x for x in fibs if not x%2)
    less_than_4000000 = takewhile(lambda x: x < 4000000, evens)
    return sum(less_than_4000000)

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 881373

With regard to the code:

if fib_iterative(n) % 2 == 0:
    total += fib_iterative(n)
    n += 1

This will only increment n if the nth Fibonacci number is even. That means that, as soon as you reach 1, it becomes an infinite loop. If you put a print(n) immediately between the while and if statements, you'll see this - it will print out 0 followed by a rather large number of 1s (presumably until you get bored and stop it forcefully).

To fix it, you need to bring the n += 1 back one indent level so that it's incremented regardless:

if fib_iterative(n) % 2 == 0:
    total += fib_iterative(n)
n += 1

Upvotes: 2

Related Questions