The sum of the squares of the first ten natural numbers is,
12 + 22 + … + 102 = 385The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)2 = 552 = 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.
There is an easy way to solve this problem and then there is an easier way. The easy way would be set up a loop, run through each number from 1 to 100, and keep a total of the numbers and their squares in two variables, and then compute the result at the end. It would be of the form in the solution below.
|
1 2 3 4 5 6 |
sum = 0 sum_of_squares = 0 for i in range(1, 101): sum += i sum_of_squares += i**2 print(sum**2 - sum_of_squares) |
The code listing above will work and, even better, will give us the right answer. But it runs in O(n) time. On a reasonably fast PC, the code above would take almost 10 seconds to compute the result for N = 10,000,000 and over a minute for N = 100,000,000.
The good news is we can do better, and again, math to rescue.
* We know that the sum of 1..n is given as n * (n+1)/2.
* We also know that the sum of 12..n2 is given as n * (n+1) * (2n+1)/6.
Knowing this, we can compute the result is just three steps, as follows.
|
1 2 3 4 5 |
n = 100 sum = n * (n + 1) // 2 sum_of_squares = n * (n + 1) * (2 * n + 1) // 6 print(sum ** 2 - sum_of_squares) |