Problem 1

This post tackles Problem 1 in the Project Euler Series.

As you would expect, Problem 1 won't tax our mathematical skills too far, but it does let us get stuck into the new features of C#3.0.

We're asked to find the sum of all multiples of 3 or 5 below one thousand.

I'd be tempted to dive straight in, and code up a for loop. But that's the old way of doing things. We want to be Functional. How about telling the compiler what we want, and letting it figure out how to get it?

I guess we want to start with all the numbers from 1 to 999, drop all those that aren't divisible by 3 or 5, and then add up the rest.

This is where the excitement begins. A lot of the power of the new Language INtegrated Query (LINQ) features in C#3.0 come from tools to work with sequences. We use sequences all the time: whenever we use foreach on an IEnumerable type, we're iterating through a sequence.

LINQ and its associated APIs allow us to process sequences of things, without there being a for, or an i or a j in sight.

Some of the APIs produce sequences for us. Enumerable.Range(int start, int count) for example will produce a sequence of consecutive integers beginning with start.

Other APIs take a sequence as an input, tweak it in some way, and return a new sequence. Such is the Enumerable.Where method. This takes a sequence, drops things that don't meet a certain condition, then returns a sequence containing everything else.

Here's how you might use this:

Enumerable.Range(1, 999).Where(x => x % 5 == 0 || x % 3 == 0)

This is doing the first part of what we need: taking all the integers less than 1000, and giving us a sequence containing only the ones divisible by 3 and 5.

There are two curious things about that piece of code. One is the way we are calling the Where method. Surely the Range method returns an IEnumerable? Since when did IEnumerable have a Where method? That's the magic of Extension methods, which we'll dig into another time. For now, its enough to know that the Enumerable class adds many useful methods, include Where, which you can call on any object that implements the IEnumerable generic interface. You just need to add a reference to the System.Linq namespace to your code, and the extension methods magically appear.

The other interesting thing is how we're specifying the condition to the Where method. What's up with the "=>" symbol? That tells the compiler that we are creating a Lambda expression. A lambda expresssion is just a little inline block of code that we can pass to another method. This expression just takes one argument x, and returns true or false depending on whether x is divisible by 5 or 3. Isn't the syntax elegant? No need for the return keyword, and no need to tell C# that x is an int or that the expression returns a bool. It works all that out for itself.

Now that it has the lambda expression, the Where method can take every item in its input sequence (the one that it's getting from Enumerable.Range), call the expression to see whether the item meets the condition, and if it does, pass it though to the output sequence.

So it looks like we're almost ready to give Euler his answer. Except that he asked for the sum of all these numbers. That's easy. Enumerable provides another extension method, Sum(), that will get that for us. We just tag it on the end of what we've got already:

static int SumMultiplesOfThreeAndFive()
{
    return Enumerable.Range(1, 999)
            .Where(x => x % 5 == 0 || x % 3 == 0)
            .Sum();
}

Sum just works its way through a sequence, adding up everything it encounters and returns the result.

And there you have it. A Functional solution, in one line of code (ignoring a few newline characters!) to Project Euler, Problem 1.

[Updated to correct a few typos on 24/3/2008]

[Updated to correct a few typos on 25/3/2008]

[Updated to correct solution in line with change to problem on 5/5/2008]