The second problem is another classic, this time in the form of the Fibonacci sequence.
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, the first thing we need is a Fibonacci generator. Thanks to Python’s generators this should be quite elegant. And thanks to the fact that generators are lazy, we can effectively make an infinite one and not have to worry about exceeding any bounds.
This is a good time to introduce my idea of making a personal standard library
of stuff that might be useful. A Fibonacci generator might not be the number
one most useful thing, but it’s the start of potentially many exciting functions
I can call upon when required. This one is in the euler package in the
math module.
def fib():
x = 0
y = 1
yield y
while True:
x, y = y, x + y
yield y
To test it let’s take all the Fibonacci values up to 60.
>>> list(takewhile(lambda x: x < 60, fib()))
[1, 2, 3, 5, 8, 13, 21, 34, 55]
So far, so good. And in fact we can use this exact technique to get all the values under four million.
from itertools import takewhile
from euler.math import fib
def sum_fib_evens(limit):
return sum(x for x in takewhile(lambda y: y < limit, fib()) if not x % 2)
def test_0002_fibonacci_sequence():
assert sum_fib_evens(4000000) == 4613732
The answer is 4613732 and it takes 1ms to work that out.