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) = 385The square of the sum of the first ten natural numbers is,

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

You can optimize a bit more by removing the divisions and replace them with multipling by the decimal equivalents. So the /2 becomes *0.5 and the /6 becomes *0.166667

Not sure if your times will go down in your C test but in my cases the divisions slows C# and Unity’s .JS

Inspire &

Have Fun!

-tomlong74

Excellent point. I will try that out and let you know. More than likely I won’t see I change since I am already testing faster than my timer can count. Still that is a very good piece of advice.