I am here with Project Euler question #6. Mister #6, what do you have for us today?

Question 6:

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.

Well that’s a good one.

Prime: Brute forcing this one is a rather easy thing to accomplish. Simply looping through 1-100 (our limit) and doing the required math gets us our answer in less than 309 nanoseconds. Bumping out limit up to 100,000 gets the answer in 4 milliseconds. The code:

double Run()
{
	double limit = 100;
	double sq_sum = 0, sum_sq = 0;

	for(int i = 1; i <= limit; i++)
	{
		sq_sum += i;
		sum_sq += i * i;
	}

	return sq_sum * sq_sum - sum_sq;
}

Results

Limit        Time
100        <618 nanoseconds
1000000    4 milliseconds
1x10^15    unknown

Optimization 1: The above code has no comparisons and only a single loop, so there doesn’t seem to be a whole mess of optimization potential. Besides minor, insignificant variable optimizations, the only one I can think of is substituting a formula for the iterative loop. The square of the sum from 1 through limit is represented as (1+2+3+4+5+…limit)^2. Where have we seen that (1+2+3+…) before? Oh yes, we worked with that for Project Euler problem #1 (seen here). Substituting p for limit, this can be represented as ( p * (p+1) /2). To get the square of that sum, we just raise it by 2 (or multiply it by itself). That solves the square of sums, and now for the sum of squares. There is a whole mathematical explanation for the formula for the sum of squares, but I will just cut to the good stuff and say that the formula is p * (p+1) * (2p + 1) / 6. The code:

double Run()
{
	double limit = 100;
	double sq_sum = 0, sum_sq = 0;

	sq_sum = limit * (limit + 1) / 2;
	sum_sq = limit * (limit + 1) * (2 * limit + 1) / 6;

	return sq_sum * sq_sum - sum_sq;
}

Results

Limit        Time
100        <309 nanoseconds
1000000    <309 nanoseconds
1x10^15    <309 nanoseconds

This code runs in less than 309 nanoseconds no matter what the limit is. I put in the biggest number I could hold in a variable (1 * 10^308) and still finished no time. Therefore, I can safely say that Optimization 1 is as good as I’m going to get.