Project Euler: Problem 6

Posted on May 24th 2021 in Algorithms by Pim Debaere.

Project Euler: Problem 6

Time for a new problem from Project Euler. Admittedly, a fairly easy problem to solve – you don't even need to be able to program for it, as long as you can work with software such as Excel. Of course I do not only want to find the right solution, but also a way with which we can also solve the same problem if the limits are slightly higher. Feel free to read on for the solution and for a quick and simple algorithm.

Sum square difference

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.
Problem 6

As mentioned, you can simply calculate this in Excel, but let's stick to a bit of programming. The easiest way is to write a loop that calculates the square for every natural number up to and including one hundred and adds the number to the sum and then does the actual calculation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function sumSquareDifference(n) { 
  var sum = 0; 
  var sum_square = 0; 
 
  for (var i = 1; i <= n; i++) { 
    sum += i; 
    sum_square += Math.pow(i, 2); 
  } 
 
  return Math.pow(sum, 2) - sum_square; 
} 
 
console.time('run'); 
var answer = sumSquareDifference(100); 
console.timeEnd('run'); 
console.log('Answer: ' + answer); 
 
// output: 
// run: 0.040283203125 ms 
// Answer: 25164150

Fig. 1 – Project Euler: Problem 6 - an elaboration of the problem.

The above code works and will quickly give you the result. However, if we do not set the limit to 100, but to 100,000, then we see that this piece of code needs more than 5 ms, so it suddenly takes 125 times longer! So this can be done better.

Simple math

Because this is a triangular number (the sum of consecutive natural numbers) we can also write the sum as follows:
sum(n) = n(n + 1) / 2

We can also make the same simplification for the sum of the squares. Feel free to calculate that for every natural number the following is correct if we want the sum of the squares:
sum_squares(n) = n(n + 1)(2n + 1) / 6

If we put these two formulas together, we can calculate the result as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function sumSquareDifference(n) { 
    var sum = n * (n + 1) / 2; 
    var sum_square = n * (n + 1) * (2 * n + 1) / 6; 
 
    return Math.pow(sum, 2) - sum_square; 
} 
 
console.time('run'); 
var answer = sumSquareDifference(100); 
console.timeEnd('run'); 
console.log('Answer: ' + answer); 
 
// output 
// run: 0.025146484375 ms 
// Answer: 25164150

Fig. 2 – Project Euler: Problem 6 - optimized calculation.

Not only is the calculation for this question (with limit 100) now about twice as fast, if we do the same calculation now with limit 100,000 we see that we now also have the result in 0.3 ms!