Sums and Squares – Or: How I Solved Project Euler Problem 6

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

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

1² + 2² + … + 10² = 385

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

(1 + 2 + … + 10)² = 55² = 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.

The Algorithm

There’s only one way to solve this problem.

This one is real simple – dependant on your understanding of Mathematics – assuming you can understand Square Numbers.

It’s a two step approach:

1. Sum (add up) all of the squares of the numbers between 1 and 100
2. Sum all of the numbers between 1 and 100, then square the answer
3. Then find the difference between them (subtract one from the other)

There’s a slight problem with this method, though. Skipping ahead – and, hopefully teaching you all a little about speed-of-light Maths – we get:

There is a well known story about Karl Friedrich Gauss when he was in elementary school. His teacher got mad at the class and told them to add the numbers 1 to 100 and give him the answer by the end of the class. About 30 seconds later Gauss gave him the answer.
The other kids were adding the numbers like this:
1 + 2 + 3 + . . . . + 99 + 100 = ?
But Gauss rearranged the numbers to add them like this:
(1 + 100) + (2 + 99) + (3 + 98) + . . . . + (50 + 51) = ?
If you notice every pair of numbers adds up to 101. There are 50 pairs of numbers, so the answer is 50*101 = 5050.  Of course Gauss came up with the answer about 20 times faster than the other kids.

That version of the story comes, courtesy of Dr. Math. The actual story has been around for… well, since the days of Karl Friedrich Gauss

Anyway, skipping to the end, we find that the sum of all the numbers from 1 to 100 comes out at 5050. A quick calculation tells us that 5050 squared (5050 * 5050) is 25,502,500. Quite a big number, wouldn’t you say?

That’s fine, but logic tells me that the other number I’m working out (the sum of the squares) will be huge, compared to this one. So, and int just wont do it.

Dependant on your system, an int can store a value between +2,147,483,647 and – 2,147,483,646 (32 bit)

So because of this, potentially, massive answer, I decided to code this by using an unsigned long long (sometimes called a long int) type.

Again, dependant on your system, an unsigned long long can store a value between 0 and +4,294,967,295 (32bit)

Of course, I’m running 62 bit, so the maximum values that these two variable types can hold are doubled. But that’s not the point.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

A simple problem with a simple solution.

Here’s a link to the cpp file: LINK

Until next time,

J