Difference of squares - Part 2

In the first part, we introduced the problem, and proposed a solution, but found it inefficient at high numbers. Now we will try for a more efficient solution.

Solution #2

After digging around online a bit, it becomes obvious pretty quick that we can reduce our solution to a simple equation.

sumOfSquares n = n * (n+1) * (2*n+1) `div` 6
squareOfSum n = (n * (n+1) `div` 2) ^ 2

This simplifies it immensely, and we run out of ways to represent n before the calculation lags now.

But, what did we do here?

Proof

So we have found the formula of (n * (n+1) * (2n+1)) / 6 is equal to our sumOfSquares formula. Our testing has worked out, but we want to be sure that they are the same. So of course, let's prove it, and how else, but by induction.

Base case:

N = 1

(N * (N+1) * (2N + 1)) / 6 ==>
(1 * (1+1) * (2*1 +1)) / 6 ==>
6 / 6 = 1

That checks out. Now on to the next step.

Let's assume that for N = K the following statement is true:

1^2 + 2^2 + 3^2 ... K^2 = (K * (K+1) * (2K+1)) / 6

If that is true, then N = K+1 becomes:

1^2 + 2^2 + 3^2 ... (K+1)^2 = ((K+1) * ((K+1)+1) * (2(K+1)+1)) / 6 = ((K+1)*(K+2)*(2K+3))/6

This can be rewritten as:

1^2 + 2^2 + 3^2 ... K^2 + (K+1)^2 = (K * (K+1) * (2K+1)) / 6 + (K+1)^2

The right-hand side reduces down to:

((K+1)(2K^2 + 7K + 6)) / 6 ==> ((K+1)(K+2)(2K+3)) / 6

Since the left-hand side is equal to the right-hand side, we are done!

Background

It turns out that the above is a specific case of the more general idea of Bernoulli's Numbers, which is used in numerous other places including Fermat's Theorem and Euler-Maclaurin summation.

Wrapping Up

This post has already gone on for far too long (like anyone got this far). The analysis of the other formula used will have to wait for a future post. As will further exploration of Bernoulli and his numbers. 

Difference of squares - Part 1

This post was inspired by an exercise on Exercism and Project Euler. Be warned, I will be showing solutions that should work for both of those sites, so... if you don't want spoilers, leave now (and come back later when you have finished).

The Problem

The difference of squares problem is simply stated as determining the difference between the sum of squares and square of sums for a sequence of numbers from 1 to N.

An example:

The sum of squares for the first five natural numbers is:

(1^2 + 2^2 + 3^2 + 4^2 + 5^2) = 55

The square of sums for the first five natural numbers is:

(1+2+3+4+5)^2 = 225

With the difference between the two sequences being:

225 - 55 = 170

Solution #1

So the problem seems pretty easy, and in Haskell, it becomes almost trivial.

Let's take the first step as the sum of squares.

sumOfSquares :: Integral a => a -> a
sumOfSquares n = sum $ fmap (^2) [1..n]

We first generate a list of numbers from 1 to the input N. Then square each number in the sequence and sum the entire list. Simple

On to the square of sums.

squareOfSum :: Integral a => a -> a
squareOfSum n = (^2) $ sum [1..n]

Similarly here, we generate a list, but now sum it up, and the square the result.

The difference between the two hopefully is obvious:

difference :: Integral a => a -> a
difference n = squareOfSum n - sumOfSquares n

This solution is extremely trivial to implement, not only in Haskell but other languages as well. But, it is not exactly efficient. First, we are doing n+1 squares. Second, we are generating the same list multiple times. Even so, this performs pretty quickly on my machine up through ~ 1,000,000. After that, the operations start to slow down. 

But we can do better surely, and do so in the next post.