Project Euler: Problem 6 (in Java)

Problem 6 in Project Euler is as follows:

The sum of the squares of the first ten natural numbers is,
1^(2) + 2^(2) + … + 10^(2) = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 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 = 2640.

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

Brute Force Approach

This was an unusual problem for Project Euler as the brute force approach was both easy to code and ran well within the time constraints. My brute force solution was as follows:

	public int euler6(int n) {
		int sumOfSquares = 0;
		int squareOfSum = 0;
		for (int i=1; i<=n; i++) {
			sumOfSquares +=  (i*i);
			squareOfSum += i;
		}
		squareOfSum *= squareOfSum;
		
		int ans = squareOfSum-sumOfSquares;
		return ans;
	}

This approach (with a Big-O analysis of O(n)) took just 5 milliseconds on my laptop, well within the time limit of 1 minute.

None the less, I started analyzing the numbers, looking for patterns that might provide a better solution but I have to be honest, I couldn't find much. So, I started Googling...

Key 1

I came across the work of Gauss. I have to admit I have never heard of his work before, but clearly he was much smarter than me!

At the age of only 10, he figured out that the sum of all numbers up to n can be calculated at n(n+1)/2
e.g. 1+2+3+4+5+6+7+8+9+10 = 10(5)/2=25
There are a couple of good pages about this here and here.

Key 2

Next, I found this very cool formula for the sum of squares:
For a number n, 1^2 + 2^2 + 3^2 +.... n^2 =
n(n + 1)(2n + 1)/6

e.g. the sum of squares
=1+4+9+16+25+36+49+64+91+100=385
Or
=10(10+1)(20+1)/6
=10(11)(21)/6
=110(21)/6
=2310/6
=385

Magic!
I found the best explanation of this here.

Final Solution

So, given those 2 formulae, we can rewrite the Project Euler #6 solution as:

	public int euler6(int n) {
		int sumOfSquares = n* (n + 1) * (2*n + 1) /6;
		int sum = n*(n+1)/2;
		int squareOfSum = sum*sum;
		int ans = squareOfSum-sumOfSquares;
		return ans;
	}

Which runs in constant time or O(1).
I would never have figured out these formulae myself, but they are pretty cool to know!

Tags: euler