Fork me on GitHub

Find the sum of all the even-valued terms in the sequence which do not exceed

Mon 04 January 2010

four million tags: projecteuler, python type: post category: programming Published: true meta: _edit_last: '1' Comments: true Problem Statement

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Notes

In this case we shall write a method fib() for generating a fibonacci sequence. However in order to keep the sequence open ended (infinite), we shall use a generator. This allows us to use the necessary memory only on demand. However we do need to terminate the sequence generation at some point. In this case when the generated numbers exceed four million. For this we define a method until(gen,predicate) which is also a generator which wraps another generator (in this case fib()), but also accepts a predicate which acts as a stop condition for further generation when the predicate evaluates to True. UpDate: Changed to using itertools.takewhile per Navin's suggestion in comments. We supply the predicate itself as a lambda which has a condition check for value exceeding four million. Finally in order to add only the even values in the series, we use the for loop on the generator followed by an if condition to test whether the generated value is even.

Solution

from itertools import takewhile 

def fib():
    """ Fibonacci series generator """
    x = 1
    y = 1
    while True :
        x,y = y,x+y
        yield x

# Actual Solution
print sum(val for val in takewhile(lambda x : x <= 4000000,fib()) if val%2 ==0)

Comments !

social