Project Euler Problem 2

Statement

Each new term in the Fibonacci sequence is generated by adding the previous two terms.

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Exploration

The even terms in the sequence are:

This can be computed quickly with code, some Fibonacci sequence equations would be interesting to derive.

Notice every 3rd number is even, as the previous two numbers are odd, which sums to even. A similar statement can be said about the odd numbers.

The Fibonacci sequence can be generated with the equation:

Then every third number can be defined with the equation:

Also something interesting I noticed for

is:

Playing with that leads to the similar equation

An equation to represent this problem is as follows, however this would need a computer to finish in reasonable time.

Solution

Since every third number is even, take each third element of the sequence until four million. Three step jumps can be taken as defined by the matrix above.

>>> class Pair:
...   def __init__(self, fi_m1, fi):
...     self.fi_m1 = fi_m1
...     self.fi = fi
>>> def f_3(pair):
...   return Pair(
...     pair.fi_m1 + (2 * pair.fi),
...     (2 * pair.fi_m1) + (3 * pair.fi)
...   )
>>> x = Pair(1, 2)
>>> s = 0
>>> while x.fi < 4e6:
...   s += x.fi
...   x = f_3(x)
>>> print(s) 
4613732