November | 2018 | Josiah Wood

Project Euler Problem 2 instructs:

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.

They’ve already given you the definition of the Fibonacci sequence (except it is usually written as starting with 0,1 or 1,1). So the first thing to figure out is how do we find the sequence of even-valued terms.

Luckily, there is a pretty easy pattern here. Let’s start by writing the Fibonacci sequence as a formula:

$F_n=F_{n-1} + F_{n-2}$

where $F_1=F_2=1$

So starting by substituting $n=3$ we get $F_3=F_2+F_1$ . Since both $F_1$ and $F_2$ are odd valued, we’ll replace them with $F_{odd}$ . So now we have:

$F_3=F_{odd} + F_{odd}$

Two odd numbers always add to an even number, so let’s replace $F_3$ with $F_{even}$ . Resulting in:

$F_{even}=F_{odd} + F_{odd}$

So this is the start of our pattern. Now, let’s find the next equation in the pattern.

$F_4=F_3 + F_2$

Substitute $F_3$ and $F_2$ :

$F_4=F_{even} + F_{odd}$

An even and and odd number will always add to an odd number. So we have:

$F_{odd}=F_{even} + F_{odd}$

Repeat for $F_5$ and we have:

$F_{odd}=F_{odd} + F_{even}$

Once more for $F_6$ results in:

$F_{even}=F_{odd} + F_{odd}$

Which is where we started with $F_3$ . Since each Fibonacci number only depends on the previous 2 numbers, this sequence of even and odd numbers will repeat forever.

$\begin{aligned}&F_1&=&1&=&odd&\\&F_2&=&1&=&odd&\\&F_3&=&2&=&even&\\&F_4&=&3&=&odd&\\&F_5&=&5&=&odd&\\&F_6&=&8&=&even&\\&F_7&=&13&=&odd&\\&F_8&=&21&=&odd&\\&F_9&=&34&=&even&\end{aligned}$

Every third term is an even number starting with $F_3$ .

Solution A: The Straightforward Approach

The most straight-forward way to implement this in C# would be to calculate each Fibonacci number and add up every third number until we reach our limit:

public static long SolveA()
{
	long n1 = 1;
	long n2 = 2;
	long total = 0;

	while (n2 <= 4000000)
	{
		total += n2;

		long n3 = n1 + n2;
		long n4 = n2 + n3;
		long n5 = n3 + n4;

		n1 = n4;
		n2 = n5;
	}

	return total;
}

Solution B: Skipping Odd Values

Now we’re going to discuss the first optimizaiton. Since we only need to add up every third Fibonacci number, we don’t actually need the other two in the sequence.

Once again, let’s start with our Fibonacci sequence formula:

$F_n=F_{n-1} + F_{n-2}$

Instead of being based on the previous two numbers, which we don’t care about, let’s see if we can rewrite it in terms of the numbers we do care about. That would be the other even numbers, which occur in every third place. So we’d like to express $F_n$ in terms of $F_{n-3}$ and $F_{n-6}$ .

Let’s start by substituting $F_{n-1}$

$F_n=F_{n-2}+F_{n-3} + F_{n-2}$

Simplify:

$F_n=2*F_{n-2}+F_{n-3}$

$F_{n-3}$ is useful, but we still need to break down $F_{n-2}$ :

$F_n=2*(F_{n-3}+F_{n-4})+F_{n-3}$

Simplify:

$F_n=3*F_{n-3}+2*F_{n-4}$

This part gets a bit tricky. We’re going to substitute only one $F_{n-4}$ and leave the other one to use later:

$F_n=3*F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}$

Now we substitute $F_{n-3}$ back in place of $F_{n-4}+F_{n-5}$ to get:

$F_n=3*F_{n-3}+F_{n-3}+F_{n-6}$

Simplify:

$F_n=4*F_{n-3}+F_{n-6}$

There you have it. We now have our Fibonacci sequence, except that it only spits out the even terms.

Here is the C# code:

public static long SolveB()
{
	long n1 = 2;
	long n2 = 8;
	long n3 = 34;
	long total = 10;

	while (n3 <= 4000000)
	{
		total += n3;
		n1 = n2;
		n2 = n3;
		n3 = (n2 << 2) + n1;
	}

	return total;
}

Note: the n2 << 2 is just a more efficient way to multiply by 4.

Solution C: No Running Total Needed

Ok, so there's actually a way to do this without even keeping a running total. We still have to calculate the Fibonacci sequence, but we don't have to explicitly add up the even terms. We'll do this with a trick similar to the one in Project Euler Problem 1.

What we're trying to solve is the total that we'll call $S_n$ :

$S_n=\displaystyle\sum_{k=1}^{n/3}F_{3*k}$

Let's start by taking the end of Solution B:

$F_n=4*F_{n-3}+F_{n-6}$

This will be much easier to work with if we add 6 to the indices and get:

$F_{n+6}=4*F_{n+3}+F_n$

And then solve for $F_n$ :

$F_n=F_{n+6}-4*F_{n+3}$

Now let's expand the values of $F_n$ that we want to sum for our solution:

$\begin{aligned}&F_n&=&F_{n+6}&-&4*&F_{n+3}\\&F_{n-3}&=&&&&F_{n+3}&-&4*&F_n&\\&F_{n-6}&=&&&&&&&F_{n}&-&4*&F_{n-3}&\\\dots\\&F_6&=&&&&&&&&&&&F_{12}&-&4*&F_9&\\&F_3&=&&&&&&&&&&&&&&F_9&-&4*&F_6&\\&F_0&=&&&&&&&&&&&&&&&&&F_6&-&4*&F_3&\end{aligned}$

Note: I know that $F_0$ is equal to zero, but having it here it will make things easier later.

First, you can see that the left side of these equations add up to the total we are looking for. They're the list of all the even Fibonacci numbers. And we can also see a pattern on the right side. The terms in the middle partially cancel each other out leaving negative three of each term. So it ends up looking like this:

$S_n=F_{n+6}-3*F_{n+3}-3*F_n-3*F_{n-3}-...-3*F_{12}-3*F_9-3*F_6-4*F_3$

We can simplify this with a summation expression as:

$S_n=F_{n+6}-3*F_{n+3}-3*\displaystyle\sum_{k=1}^{n/3}F_{3*k}-F_3$

Substitute the summation for $S_n$ :

$S_n=F_{n+6}-3*F_{n+3}-3*S_n-F_3$

And solve for $S_n$ :

$S_n=\dfrac{F_{n+6}-3*F_{n+3}-F_3}4$

We now have the sum of our Fibonacci sequence in terms of the sequence itself.

In code form:

public static long SolveC()
{
	long n1 = 2;
	long n2 = 8;
	long n3 = 34;

	while (n3 <= 4000000)
	{
		n1 = n2;
		n2 = n3;
		n3 = (n2 << 2) + n1;
	}

	n1 = (n3 << 2) + n2;

	long total = (n1 - 3 * n3 - 2) >> 2;

	return total;
}

Solutions D & E: Logarithmic Time Algorithms

The solutions we've developed so far have all had a linear time complexity with respect to the maximum sequence value (4000000 in our case). However, it is possible to do better than that. I'm not going to go into a lot of detail, because this is probably beyond the skill level expected just for problem 2 on Project Euler.

Matrix Multiplication

It is actually possible to find the nth Fibonacci number with the following matrix formula:

$\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}$

And there are tricks to do the matrix exponent in logarithmic time, which I won't get into yet. But that's not the whole problem. Our problem statement doesn't actually want us to get the nth Fibonacci number. It wants us to sum up to the number whose value does not exceed a limit. So you'd have to use this matrix exponentiation to do a binary search to find which value of n does not exceed the limit where n + 3 does. You could then use this in our Solution C.

Inspiration for this solution came from this link.

Binet's Formula

Another improvement on the previous solution can find the nth Fibonacci number in constant time. It's called Binet's formula. In fact, any constant-recursive sequence can be solved this way. However, the binary search from the matrix solution would still be needed to find the index in the Fibonacci sequence that doesn't exceed the limit.

Here is the formula:

$f_n=\dfrac{\bigg(\dfrac{1+\sqrt5}2\bigg)^n-\bigg(\dfrac{1-\sqrt5}2\bigg)^n}{\sqrt5}$

This could also be used in Solution C to find the desired sum.

GitHub

You can find the code on GitHub (complete with unit tests) at https://github.com/josiahwood/ProjectEuler/tree/master/Problem2.

Josiah Wood

Monthly Archives: November 2018

Project Euler Problem 2: Even Fibonacci numbers

Solution A: The Straightforward Approach

Solution B: Skipping Odd Values

Solution C: No Running Total Needed

Solutions D & E: Logarithmic Time Algorithms

Matrix Multiplication

Binet's Formula

GitHub