Project Euler Problem 6

Sum Square Difference

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 = 55^2 = 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.

Analytic solution

Not sure if there's much to say on this problem besides that using two special cases of Faulhaber's formula for powers of 1 and 2 we can write

\sum_{k=1}^n k = \frac{n(n+1)}{2}

and

\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}

So we can compute the answer directly using

\begin{align} \operatorname{SSD}(n) &= \left( \sum_{k=1}^n k \right)^2 - \sum_{k=1}^n k^2 \\ &= \left( \frac{n(n+1)}{2} \right)^2 - \frac{n(n+1)(2n+1)}{6} \\ &= \frac{n(n+1)(n-1)(3n+2)}{12} \end{align}

With a simple implementation

function sum_square_difference(n)
    return n * (n + 1) * (n - 1) * (3n + 2) ÷ 12
end

we call sum_square_difference(100) to compute the solution which runs in 2.384 ns.

It turns out that actually there is a bit more to say. The answers $\operatorname{SSD}(n) = 0, 4, 22, 70, 170, 350, \dots$ are OEIS A052149, which describes them as the number of rectangles on an $n \times n$ board that aren't squares.

To see why, notice that a rectangle on the board is picked out by choosing two of the $n + 1$ vertical grid lines for its left and right sides, and two of the $n + 1$ horizontal grid lines for its top and bottom. So the number of rectangles is

\binom{n+1}{2}^2 = \left( \frac{n(n+1)}{2} \right)^2 = \left( \sum_{k=1}^n k \right)^2

which is the square of the sum! A $k \times k$ square fits on the board in $(n - k + 1)^2$ different positions, so going from $k = 1$ to $k = n$ there are $n^2 + (n-1)^2 + \cdots + 1^2$ squares, which is the sum of the squares. The difference counts the rectangles that aren't squares. A chessboard, for example, has $36^2 = 1296$ rectangles and $204$ squares, so $\operatorname{SSD}(8) = 1092$ of its rectangles aren't squares.

The same numbers show up when placing two queens peacefully on a chessboard. Two queens can attack each other if they're in the same row, column, or diagonal. If we put a dot in the center of each cell of an $(n+1) \times (n+1)$ board, the dots are the corners of the cells of an $n \times n$ board. Two queens in different rows and different columns then sit peacefully on opposite corners of a rectangle on the smaller board, and they're on the same diagonal (and vulnerable) exactly when that rectangle is a square. Every rectangle has two pairs of opposite corners, so there are $2 \operatorname{SSD}(n)$ ways to place two queens on an $(n+1) \times (n+1)$ board so that neither attacks the other (OEIS A036464).

These numbers also show up in combinatorics. Expanding

x(x+1)(x+2) \cdots (x+n) = x^{n+1} + \left( \sum_{k=1}^n k \right) x^n + \left( \sum_{1 \leq i < j \leq n} ij \right) x^{n-1} + \cdots

the coefficient of $x^{n-1}$ is half the answer. The coefficients of this polynomial are the (unsigned) Stirling numbers of the first kind, where the coefficient of $x^k$ counts the permutations of $n + 1$ objects that have exactly $k$ cycles. So

\operatorname{SSD}(n) = 2 \left[ {n+1 \atop n-1} \right]

and half the answers $0, 2, 11, 35, 85, 175, \dots$ are OEIS A000914.

Analytic solution

What the answers count