Posted on Jan 8, 2020 • Originally published at jinglescode.github.io

Project Euler - Problem 6 - Sum square difference

The problem

This is problem 6 from the Project Euler.

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 = 552 = 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 n natural numbers and the square of the sum.

Thinking process

square of the sum

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

(1 + 2 + ... + 10)^2 = 552 = 3025

Find the patterns.

sum_of_first_n(4) = 1+2+3+4 = 10 sum_of_first_n(6) = 1+2+3+4+5+6 = 21 sum_of_first_n(8) = 1+2+3+4+5+6+7+8 = 36 sum_of_first_n(10) = 1+2+3+4+5+6+7+8+9+10 = 55

I know I have to make use of the n.

sum_of_first_n(4) = (4+1)*2 = 10 sum_of_first_n(6) = (6+1)*3 = 21 sum_of_first_n(8) = (8+1)*4 = 36 sum_of_first_n(10) = (10+1)*5 = 55

I am seeing a pattern here, and that is:

sum_of_first_n(n) = (n+1)*(n/2)

And return as square of sum with this function:

function square_sum_of_first_n(n){ return Math.pow( (n+1)*(n/2), 2); }

sum of the squares

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

1^2 + 2^2 + ... + 10^2 = 385

Find the patterns.

sum_of_square(2) = 5 = 1^2 + 2^2 = 2^2 + 1 sum_of_square(3) = 14 = 1^2 + 2^2 + 3^2 = 3^2 + 5 sum_of_square(4) = 30 = 1^2 + 2^2 + 3^2 + 4^2 = 4^2 + 14 sum_of_square(5) = 55 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 5^2 + 30

By looking at the additions, you can tell that we need another multiplier, having other additions is simply not enough.

After much trials, I realised it about multiplying n with n+1 with n+(n+1):

sum_of_square(2) = 5 = (2*3 * (2+3))/6 sum_of_square(3) = 14 = (3*4 * (3+4))/6 sum_of_square(4) = 30 = (4*5 * (4+5))/6 sum_of_square(5) = 55 = (5*6 * (5+6))/6

And we get this function:

function sum_of_square(n){ return ( ( (n * (n+1)) * (n + (n+1)) )/6) }

Combine everything

// list of numbers we wanna test var test_values = [10, 20, 100]; // this function execute the code and records the time to execute function run_function(func, test_values) { for(var i in test_values){ console.log('Test value:', test_values[i]); var t0 = performance.now(); console.log('Output:', func(test_values[i])); var t1 = performance.now(); console.log("Took " + (t1 - t0) + " ms"); console.log(); } } function sumSquareDifference(n) { return square_sum_of_first_n(n) - sum_of_square(n); } function sum_of_square(n){ return ( ( (n * (n+1)) * (n + (n+1)) )/6) } function square_sum_of_first_n(n){ return Math.pow( (n+1)*(n/2), 2); } run_function(sumSquareDifference, test_values);

Output:

Test value: 10 Output: 2640 Took 0.10000000474974513 ms Test value: 20 Output: 41230 Took 0.03500000457279384 ms Test value: 100 Output: 25164150 Took 0.03500000457279384 ms

This is my Project Euler Challenge journey; anyone wants to do this together? It will be fun, and we can learn a thing or two by solving this problem in different ways.

DEV Community