Project Euler Problem 6

This post tackles Problem 6 in the Project Euler series.

How many budding young mathematicaians have been regaled with the story of Karl Friedrich Gauss and his lightning fast calculations? The story goes that, in a maths lesson at his primary school, his teacher wanted to keep the class busy for an hour, so he told them to work out the sum of all the numbers from 1 through to 100. The others in the class laboured away for the rest of the lesson, but only minutes after being given the problem Gauss, amongst the youngest in his class, had scribbled the answer on his slate and handed it in. The teacher didn't bother to look at his result, assuming that it couldn't possibly be right. When he finally did check at the end of the lesson, Gauss's slate was the only one holding the correct answer. (And here are 109 other versions of this story!)

Gauss' secret? There's a formula for finding the sum of this sequence which made it easy for him to do it in his head: 1 + 2 + ... + n = n(n+1)/2. You can arrive at the formula by noting that when you write down the sum, it's possible to rearrange the terms into pairs of numbers each summing to the same value. So for example, 1 + 2 + 3 + ... + 100 can be written (1 + 100) + (2 + 99) + (3 + 98) + ... + (49 + 52) + (50 + 51). Each pair sums to 101, and their are 50 pairs.

Using other techniques we can find a formula for the sum of squares of the numbers 1 to 100. It is 1^2 + 2^2 + ... + n^2 = n(n + 1)(2n + 1)/6. You can see the derivation of that formula here.

These are the formulae I would use if I wanted to solve Problem 6 mathematically. But my computer spends a large part of its day with the processor sitting at only 2% CPU usage, and I'm afraid it might be getting flabby, like its operator. So I'm going to make it do its calculations the long way.

Here's the code:

    public static class Problem6
    {
        public static void Main()
        {
            int sumOfNumbers = 1.To(100).Sum();
            int squareOfSum = sumOfNumbers * sumOfNumbers;

            int sumOfSquares = 1.To(100).Select(x => x * x).Sum();

            int difference = squareOfSum - sumOfSquares;

            difference.DisplayAndPause();
        }
    }

    public static class Problem6Extensions
    {
        public static IEnumerable<int> To(this int first, int last)
        {
            for (int i = first; i <= last; i++)
            {
                yield return i;
            }
        }

        public static void DisplayAndPause(this int number)
        {
            Console.WriteLine(number);
            Console.ReadLine();
        }
    }

I think this is all self-explanatory, except perhaps the call to the Select method in the line I've highlighted. Put simply, the Select method operates on a sequence and performs a transformation on every element it sees. In this case we're transforming each of the input numbers into their corresponding square number. This sequence of squares is then passed through to the Sum method which gives us the total we need.

So there we are. Nice and simple this time, before the pace picks up in the next episode.