Project Euler, Problem 6

22 Sep 2009

Inspired by my brother over at geekality.net, I thought I should do an attempt on the various problems presented at projecteuler.net/.  Since he already solved the first five, I jumped right in at problem 6:

The sum of the squares of the first ten natural numbers is,

12 22 … 102 = 385

The square of the sum of the first ten natural numbers is,

(1 2 … 10)2 = 552 = 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 = 2640.

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

This problem has two distinct parts. First, there is the sum of a sequence of the squared natural numbers, then there is the sum of a sequence of natural numbers, squared.

Sum of a series of squared natural numbers

The problem tells to summarize the square of the first hundred natural numbers. That gives us the following sequence:

12 22 … 992 1002

The simplest solution would be a brute force loop like this one:

function sumSquaredNumbers( ): longword;
var
  i: integer;
begin
  result := 0;
  for i := 1 to 100 do
    result := result   (power(i, 2));
end;

That wouldn’t be much fun, though. There has to be a more general, optimized algorithm for this kind of work. First of all, we should make the function workable for any series length. That should be easy – just switch the hardcoded 100 with an given parameter:

function sumSquaredNumbers(serieslength: integer): longword;
var   i: integer;
begin
  for i := 1 to seriesLength do
    result := …
end;

But the code is still the same, though. Nothing was optimized in any way. We still have the loop, making our function linear.

Google to the rescue!

math.com have a nice section on Series Expansions, which includes a table of power summations. This table states that

n

∑ k2 = 1 4 9 … n2 = (1/3)n3 (1/2)n2 (1/6)n

k=1

Why this should be true, I honestly can’t tell, but a fast comparison to our brute force solution shows that it gives us the right numbers. That’s good enough for now:

function sumSquaredNumbers(seriesLength: integer): longword;
begin
  result := trunc(
                ((1/3) * power(seriesLength, 3))
                ((1/2) * power(seriesLength, 2))
                ((1/6) * seriesLength)
              );
end;

I think this is a nice solution, and a constant one as well. It doesn’t matter if the series is of length one, hundred or thousand – the computation should take the same amount of time.

Sum of a series of natural numbers, squared

This part should be a lot easier. We could start with a brute force solution to this part too, but I think we could come up with something smarter right away.

I already know of a simple optimization. If you add the first and last number in the series, you will get the same as if you add the second and next to last number:

1 2 3 4 5 6 7 8 9 10

10 9 8 7 6 5 4 3 2 1

= 11 11 11 11 11 11 11 11 11 11

As you can see, every pair of numbers makes the same sum when added together. So for any given series, you can take the first and the last number and add them together, then you can multiply the sum by the length of the series, and finally divide by two.

n

∑ k = 1 2 3 … n = (1 n) * n / 2

k=1

I know there are other solutions to this, but this one will do.

function sumSquared(seriesLength: longword): longword;
begin
  result := trunc(power(((1   seriesLength) * seriesLength / 2), 2));
end;

The solution

Now that we have solved each of the two sub parts of the problem, I guess we’re ready to solve the main thing.

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

Since we know the sum of the squares, and we now the square of the sum, it’s just a matter of substract the one from the other:

function diff(serieslength: longword): longword;
begin
  result := sumSquared(serieslength) - sumSquaredNumbers(serieslength);
end;

I have uploaded my complete solution to http://svn.vi-kan.net/euler. The code also contains a simple stopwatch to time the code. This code is so simple, though, that it’s hard to get any measures.

And that’s it. Let’s see if we can solve the next one too.