Problem

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Solution

The naive approach to this algorithm would be to just implement the recursive Fibonacci function and do what the problem says. We'd end up with something like this:

int fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }
int sum = 0;
for (int n = 0; fib(n) < 4000000; ++n)
  if (fib(n) % 2 == 0)
    sum += fib(n);

Luckily, 4 million is small enough so that this algorithm runs fairly quickly (about half a second on my machine). If the upper bound was much bigger, we would run into very serious performance issues. The reason is because the implementation of the Fibonacci function shown there runs in exponential time i.e. the time that it takes to calculate fib(n) is proportional to . In concrete terms, we're talking milliseconds to calculate fib(10), and millions of years to calculate fib(100) (that's not an exaggeration -- it's actually around 5 million years for my computer).

Since we do actually get an answer before the end of the universe, we could just move onto the next problem, but we wouldn't have learned much. It's worthwhile putting in some extra effort now to make our Fibonacci function run faster.

There are many ways to generate Fibonnaci quickly, so I'll only mention a few here.

Iterative

The iterative method simply starts at fib(1) and works its way up to fib(n), remembering the previous two values at each stage:

int fib(int n)
{
  if (n < 2)
    return n;
  int fp = 0, f = 1;
  foreach (i; 1..n)
  {
    swap(fp, f);
    f += fp;
  }
  return fp;
}

As we only have one simple loop with no recursion, this approach obviously runs in time linear in .

Memoization

Memoization is a common technique for improving the complexity of recursive functions. The concept is simple: once you have calculated a value, store it somewhere and use that value instead of calculating it again. The beauty of memoization is that it allows you to keep your elegant recursive definition.

int fib(int n)
{
	static int[] cache = [0, 1];
	if (n >= cache.length)
	  cache ~= fib(n-1) + fib(n-2);
	return cache[n];
}

Note that I have been a little cheeky with the memoization part here by simply appending the newly calculated value onto the end of the array, assuming that it will be in the right position. If you think about it though, it always will be in the right position, because fib(n-1) would have been calculated before the append, which means that the array will be elements long when the append actually happens, which is what we want.

The performance here is linear in for the first time you calculate a value then constant for subsequent invocations.

Closed-Form Formula

Interestingly, there exists a closed form formula for calculating the nth Fibonacci number. It is:

Let's put it into action:

int fib(int n)
{
	double phi = (1.0 + sqrt(5.0)) / 2.0;
	double f = (pow(phi, n) - pow(1.0 - phi, n)) / sqrt(5.0);
	return cast(int)(f + 0.5);
}

Assuming pow(double, int) is implemented using the exponentiation by squaring algorithm, this will run in logarithmic time.

Problem

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.

Solution

This problem is trivial to solve. We can test whether an integer is a multiple of an integer by testing if . In most popular programming languages (including D), this is achieved by using the modulo operator (%).

bool divides(int m, int n) { return n % m == 0; }

Using this, the straight-forward, imperative solution is to simply iterate through the numbers 1 to 999, summing those that divide by either 3 or 5.

int sum = 0;
foreach (n; 1..1000)
  if (divides(3, n) || divides(5, n))
    sum += n;

While there's nothing wrong with this solution, it's arguably not as concise as it could be. Fortunately, the Phobos library provides utilities for making this easier and more literal through its std.algorithm and std.range modules.

auto numbers = iota(1, 1000);
auto multiples = filter!("a%3==0 || a%5==0")(numbers);
int sum = reduce!("a+b")(0, multiples);

We could also write this all on one line if we wanted:

int sum = reduce!("a+b")(0, filter!("a%3==0 || a%5==0")(iota(1, 1000)));

So what's happening here?

First, the iota(a, b) function simply returns the numbers in the range . Next, the filter function takes those numbers as an argument and returns a range of those numbers that satisfy the given predicate. Here, the predicate is "a%3==0 || a%5==0" i.e. the number is divisible by 3 or 5. Now, we have all the numbers under 1000 that are divisible by 3 or 5, all we have to do is sum them; this is what reduce!("a+b") does. The reduce function starts with the first argument (0) and iteratively moves through the elements of the second argument, applying the function ("a+b") to its current value and that element.

Is this the best we can do? No. It turns out that this problem is best solved using maths. Clearly, if you count from 1 to 1000, every third number is going to a multiple of 3, and every fifth number is going to be a multiple of 5. This means that there are numbers divisible by 3, and numbers divisible by 5.

But what is the sum of all those numbers? It should be easy to see that the sum of is just 3 times the sum of and it is known that the sum of is .

So do we just add those two quantities together? Not quite. If we add them together then we will be adding the numbers that are divisible by both 3 and 5 twice. Using the inclusion-exclusion principle we just need to subtract those numbers from the total to get the correct amount. How many numbers are divisible by both 3 and 5? If you look at those numbers, it's quite easy to see the pattern: they are divisible by 15. Note that while it may seem that the 15 comes about because , it is actually because (See: Least common multiple).

Our solution now becomes simply:

int sum(int m)
{
  int n = 999 / m;
  return m * n * (n + 1) / 2;
}

int answer = sum(3) + sum(5) - sum(15);