Problem 6 - Sum of squares and square of sum

The sum of the squares of the first ten natural numbers is
12 + 22 + ... + 102 = 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 one hundred natural numbers and the square of the sum.

It is a rare programming problem that is so easy to provide a solution for, but difficult to take the extra step to optimize fully.

runsum = 0
runsquaresum = 0
for x in range(1,101):
    runsum += x
    runsquaresum += x**2
answer = runsum**2 - runsquaresum
# 6.103515625e-05 Run time in seconds

In fact, this solution is so straightforward to implement that it is possible to reduce it to a single line of code:

answer = sum(range(1,101)) ** 2 - sum([x ** 2 for x in range(1,101)])
# 2.90870666504e-05 Run time in seconds

Both of these implementations run on the same big-O magnitude of n, or linear, time. Thus, as our target number grows, our processing time grows in direct proportion. To clarify, if we make our target number 1000 instead of 100, we increase our processing time by a factor of 10. Take our target to 10000 and we again multiply our computation time by 10.

This is one approach to the problem that is a direct generation of the solution. However, suppose we use a different, slightly more search-y approach. Allow me to introduce you to Pascal's triangle:

Here, we have a mathematical construct with some very interesting properties, the most relevant of which to our problem is its containment of several summation series.

With these series, it becomes similarly complex to our previous solution to "look up" our answer in this structure. But, how do we find them?

The first part of our answer is in identifying what we need and finding a corresponding pattern in the pyramid. Since one half of our answer is the square of the sum of a number of consecutive integers, we need look no farther than the third row of the pyramid. The first row being the series of one along the pyramid, the second the summation of the ones in the previous row to that point. For ease of illustration, here's the same structure arranged in a horizontal-vertical orientation.

From here, the summation of previous rows by succeeding ones is slightly more plain. The reason we need to look at the third row, however, is that by looking here we can immediately find the sum of the second row to any given iteration, which is what we need to eventually square to produce the first part (the square of the sum) of our solution, and we need only look one row down from the second row to the corresponding entry to find the sum of the series to that point. For example:

1 + 2 + 3 + 4 + 5 = 15, 15^2 = 225

The second half of our solution is slightly more difficult to find, but can nonetheless be observed in the triangle. If we want to find the sum of squares to a certain point, we need to look at rows 2 and 4.

For example, to find the sum of squares to 5 (1^2 + 2^2 + 3^2 + 4^2 + 5^2), we look at row two to see how far we count over (5), then drop two rows to row 4 (landing at 35). Here, we simply take the number we landed on and add the previous entry on the same row (20), producing 55.

(1^2 + 2^2 + 3^2 + 4^2 + 5^2) = 1 + 4 + 9 + 16 + 25 = 55

This rule repeats throughout the pyramid, and will hold for when our target is 100 or 10000000, so we can say that:

(1 + 2 + 3 + 4 + 5)^2 - (1^2 + 2^2 + 3^2 + 4^2 + 5^2) = 225 - 55 = 170

With this method, our computation time takes a similar O(n) time magnitude, but with an additional time of magnitude n tacked on to generate the list we need to search, thus making the time magnitude remain O(n), but with a greater coefficient attached.

rows = []
rows.append([1 for x in range(100)])
x = 0
while x < 4:
    rows.append([sum(rows[-1][:a + 1]) for a in range(100)])
    x += 1
answer = (rows[2][-1] ** 2) - sum(rows[3][-2:])

While this solution works, when scaling our target up by a factor of 10, our solution time scales by a factor of 100, and this is attributable to the sum calculations that we have to do over and over to generate the sum lists. Thankfully, we can optimize this a bit. We don't need to generate the first row of all ones, since we don't reference it in the future. We can eliminate generation of the fourth row (third sum), since all we need from that row can be generated by summation of certain parts of the third row. Thus, we can optimize our code to once again have a O(n) time scale:

sum_one = [x for x in range(1,101)]
last = 0
sum_two = []
for x in range(100):
 sum_two.append(sum_one[x] + last)
 last = sum_two[-1]
square_of_sum = sum_two[-1] ** 2
sum_of_squares = (sum(sum_two[:-1]) * 2) + sum_two[-1]
answer = square_of_sum - sum_of_squares

After all this, can we improve our solution any more? Yes we can.

There is, thankfully, a deterministic, O(1) (constant time) formula for the sum of a series of integers, which we can use in our algorithm.

1 + 2 + ... + (n-1) + n = (n+1) + (n+1) + ... + (n+1) + (n+1) = (n+1) * n/2 = (n(n+1))/2
1 + 2 + ... + 99 + 100 = 101 + 101 + ... + 101 + 101 = 101 * 50 = 5050

Once we use this formula to find the sum of our series to number n, we square the result to get the first half of our answer. Is there a similar formula for the sum of squares? Yep.

(n(n+1)(2n+1))/6

This, in combination with the first, allows us to calculate the difference incredibly quickly with the complete formula:

((n(n+1))/2)^2 - (n(n+1)(2n+1))/6

Or:

square_of_sum = ((n * (n + 1)) / 2) ** 2
sum_of_squares = (((2 * n) + 1) * (n + 1) * n) / 6
answer = square_of_sum - sum_of_squares

Or, slightly more compact and fast:

answer = (((n * (n + 1)) / 2) ** 2) - (n * (n + 1) * ((2 * n) + 1)) / 6

When n equals 10000000, my original brute force implementation takes over 4 seconds, while this last one takes

# 7.86781311035e-06 seconds