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
nnatural 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.
Top comments (0)