CODEWITHSUNDEEP
python
madisonchuchla
madisonchuchla

Reputation: 3

Using python to find even Fibonacci numbers

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. This is how I am doing it, but I am getting the wrong value, and I am not sure why. 

Sum=0
n=0
a=1
b=2
while a<=4e6 and b<=4e6:
    if a%2==0:
        Sum = Sum + a
    n=a+b
    a=b
    b=n
if b%2==0:
    sum=sum+b
print(Sum)

My value is 1089154 which is incorrect.

Upvotes: 0

Views: 1775

Answers (4)

chepner
chepner

Reputation: 531075

Note that the Fibonacci numbers start with 0 and 1, not 1 and 2. This won't affect your result, but it does make handling the numbers easier.

Start by writing a generator function that yields all the Fibonacci numbers (eventually).

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

You don't have to test a value if it is even, because the even numbers appear very predictably in the sequence:

0 1 1 2 3 5 8 13 21 34 ...

Starting with the first value, every third value is even.

Given the generator

f = fib()  # All the Fibonacci numbers

you can then get your answer in three easy steps:

from itertools import islice, takewhile

evens = islice(f, 0, None, 3)  # All the even Fibonacci numbers
small = takewhile(lambda x: x <= 4000000, evens)  # Just the ones under 4,000,000
result = sum(small)

You don't need the every-third-value trick, but it's a bit more efficient than

evens = filter(lambda x: x % 2 == 0, f)

Upvotes: 2

Steven Rumbalski
Steven Rumbalski

Reputation: 45542

With the minimal amount of changes to your code:

Sum=0
n=0
a=1
b=2
# while a<=4e6 and b<=4e6:
while a<=4e6:
    if a%2==0:
        Sum = Sum + a
    n=a+b
    a=b
    b=n
# if b%2==0:
#     sum=sum+b  
print(Sum)

Essentially you don't need to look at b because b is the next term. If you stop the loop when b exceeds 4e6 you skip the value of a that is less than 4e6. Your if-statement after the loop tries to compensate for this, but it should have looked at a (if you had kept the while-statement the same) and it adds to sum not Sum. You don't need that second if-statement since the while-statement is fixed.

I would have done it this way:

def fib(max=-1):
    curr, next = 0, 1
    while curr <= max:
        yield curr
        curr, next = next, curr + next

print(sum(n for n in fib(4e6) if n % 2 == 0))

Upvotes: 1

kszl
kszl

Reputation: 1213

s = 0
a, b = 0, 1
while b < 4e6:
    if b % 2:
        s += b
    a, b = b, a + b

print(s)

Upvotes: 0

Toby Petty
Toby Petty

Reputation: 4660

I would do it by writing a function to get the fibonacci sequence elements up to the target number so you can more easily debug.

The fibonacci function returns a list of all elements in the fibonnaci sequence which are less to or equal to n:

def fibonacci(n):
    seq = [0, 1]
    while seq[-1] < n:
        seq.append(seq[-2] + seq[-1])
    return seq[:-1]

Then you can do a simple list comprehension to sum all the even items:

sum([i for i in fibonacci(4e6) if i%2 ==0])

Upvotes: 0

Related Questions