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:

where

So starting by substituting we get . Since both and are odd valued, we’ll replace them with . So now we have:

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

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

Substitute and :

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

Repeat for and we have:

Once more for results in:

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

Every third term is an even number starting with .

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:

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 in terms of and .

Let’s start by substituting

Simplify:

is useful, but we still need to break down :

Simplify:

This part gets a bit tricky. We’re going to substitute only one and leave the other one to use later:

Now we substitute back in place of to get:

Simplify:

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 :

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

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

And then solve for :

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

Note: I know that 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:

We can simplify this with a summation expression as:

Substitute the summation for :

And solve for :

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:

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:

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.

Project Euler Problem 1 instructs:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This ends up being a basic math problem, so no code is needed yet.

I think the easiest way to think of this is as a variation on triangular numbers. Triangular numbers are the sums of the first natural numbers. Which is a very similar description to our problem statement. The initial formula for triangular numbers is:

Expanded, this looks like:

If we do a little trick here, then we can simplify this expression considerably. Take the above expansion, reverse it, and add it to the original expansion term by term.

If we simplify the repeated terms we get:

And then solve for :

Great! Now we really have something that we can use in our solution. Since the problem asked for the sum of natural numbers below 1000 let us subtract 1 to get 999. Then divide that by (which will represent the increment being summed, either 3 or 5 in this problem). Last, scale by so that we are adding up multiples of the increment instead of just sequential natural numbers. So if represents the upper limit provided (1000), then we get this equation:

Now substitute the final equation for :

However, we need the sum of numbers that are either multiples of 3 or 5. So we have to add both of those results and then subtract the intersection that would otherwise be counted twice.

It would have arguably been simpler to just write a quick program that loops through all natural numbers less than 1000 and total any value that is a multiple of 3 or 5. However, thinking about this problem mathematically is good practice for what is up ahead. In future problems you will not have the luxury of using an algorithm that takes linear time instead of constant time.

However, if you’d really like to see this in code, then here is my C# example:

using System;

namespace Problem1
{
	public class Program
	{
		static void Main(string[] args)
		{
			int result = Solve(1000);
			Console.WriteLine(result);
		}

		public static int Solve(int limit)
		{
			return Sum(limit, 3) + Sum(limit, 5) - Sum(limit, 15);
		}

		static int Sum(int limit, int increment)
		{
			int n = (limit - 1) / increment;
			return increment * n * (n + 1) / 2;
		}
	}
}

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