The Fibinici sequence is renowned for its golden ratio that is found throughout our world. It starts with the first two terms as 1 and is formed with each subsequent term being the sum of the two previous terms (1, 1, 2, 3, 5, 8, 13,…). Suppose one wanted to know the sum of every even term less than 4 million. While the solution is straight forward, a little cleverness can be used to improve efficiency.

Since the first two terms of the sequence are given, we can start the sequence as a list and build the rest of the terms less than 4 million

f = [1, 1]

while f[-1] + f[-2] < 4000000:
    f.append(f[-2] + f[-1])  # add the next term, the sum of the previous two terms

At this point our list, f, holds all the Fibinici terms less than 4 million. Finding the sum of the even terms is easy enough. A comprehension can be used to get the even terms and the built in sum operator can sum the list

print(sum([term for term in f if term % 2 == 0]))

We have answered the question, but do we really need to append each term and hold onto the entire sequence? After all, we are just summing the even terms.

Let’s try to do this on the fly by only holding two values, starting with our initial list. When we compute the next term, we will update the held values so that the second value is the current term and the first value is our previous term. The two terms in our list always tell us how to compute the next term in the Fibinici sequence. You can think of the two held values as your view of the whole sequence, through a window only two terms wide. Every update to our held values, shifts our view, once, down the sequence.

Notice, since we aren’t holding the entire sequence, we can’t use the sum operator. Instead, the sum is held in sum2

f = [1, 1]
sum2 = 0

while f[0] + f[1] < 4000000:
    f[0], f[1] = f[1], f[0] + f[1]  # update the held values
    if f[1] % 2 == 0:
        sum2 += f[1]

print(sum2)

Notice the subtlety in python’s ability to return multiple values. Since f[0] and f[1] are both computed before being assigned, there is no need for a place holder variable.

Admittetly, the computational difference in this example is negliable, but as the size of the list grows, avoiding the append operator becomes more important.