Project Euler: Problem 6

The sum of the squares of the first ten natural numbers is,
$1^2 + 2^2 + \ldots + 10^2 = 385$
The square of the sum of the first ten natural numbers is,
$(1 + 2 + \ldots + 10)^2 = 55^2 = 3025$
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 -- 385 = 3640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

– Project Euler Problem 6

So, apparently my brother has joined me on my Project Euler solving quest. You can see his Delphi solution on his blog. My C# solution, you can find below 🙂

Solution

This problem is quite straight forward so I turned to Linq and used some obvious brute force:

var numbers = Enumerable.Range(1, 100); var answer = numbers.Sum() *
numbers.Sum() - numbers.Aggregate(0, (sum, n) => sum + n * n);

This gives the answer, in 0 ms, around 2-3000 ticks.

Take 2

However, my brother went further and found some pretty smart optimizations. Had to have a look at those of course and see if I could make sense of those too. It all boils down to expansion of power summations.

\sum\limits_{(k = 1)}^n k^m

The Euler problem we are trying to solve here can be described mathematically like this:

\left(\sum\limits_{(k = 1)}^{100}k\right)^2 - \sum\limits_{(k = 1)}^{100} k^2

In other words, the answer can be found very easily if we have the formulas for m=1 and m=2. And that we do:

\begin{align*} \sum\limits_{k=1}^n k &= 1+2+3+\ldots+n=\frac{n^2+n}{2}=\frac{1}{2}n^2+\frac{1}{2}n \\ \sum\limits_{k=1}^n k^2 &= 1+4+9+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n \end{align*}

Turning those into two C# methods is quite easy and we can find our answer like so:

static ulong SumExpansion1(ulong n)
{
    return (n * n + n) / 2;
}

static ulong SumExpansion2(ulong n)
{
    return n * (n + 1) * (2 * n + 1) / 6;
}

var answer = SumExpansion1(100) * SumExpansion1(100) - Numbers.SumExpansion2(100);

That also takes 0 ms, but we are down to around 2-300 ticks. So, compared to the brute force solution, this only takes 10% of the time. Awesome ^_^

Take 2.5

The formula can actually be simplified a bit if we bring out our math skills. Not that my math skills really deserve being called skills, but anyways 😛

\begin{align*} \left(\sum\limits_{k=1}^{100}k\right)^2 - \sum\limits_{k=1}^{100} k^2 &= \left(\frac{n^2}{2}+\frac{n}{2}\right)^2 - \left(\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}\right) \\ &= \Bigl(\frac{n^2}{2}\Bigr)^2 + 2\Bigl(\frac{n^2}{2}\Bigr)\Bigl(\frac{n}{2}\Bigr) + \Bigl(\frac{n}{2}\Bigr)^2 - \Bigl(\frac{n^3}{3}\Bigr) - \Bigl(\frac{n^2}{2}\Bigr) - \Bigl(\frac{n}{6}\Bigr) \\ &= \frac{n^4}{4} + \frac{2n^3}{4} + \frac{n^4}{4} - \frac{n^3}{3} - \frac{n^2}{2} - \frac{n}{6} \\ &= \frac{3n^4+2n^3-3n^2-2n}{12} \end{align*}

Now, our answer can be found like this:

const ulong n = 100;
var answer =  (3*n*n*n*n + 2*n*n*n - 3*n*n - 2*n) / 12;

Which, compared to take 2, takes about half the time. Around 150 ticks. 😎

Alright... done with this one now...