Back to Project Euler

Previous Problem Next Problem

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.

Solution

As discussed in my writeup for problem 1, the sum of the first \(n\) natural numbers is the \(n\)-th triangular number:

\[1 + 2 + \cdots + n = \frac{n(n+1)}2\]

The sum of the squares of the first \(n\) natural numbers is the \(n\)-th square pyramidal number:

\[1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}6\]

We can prove this by induction. Noting that the base case holds because \(1^2 = \frac{1(1+1)(2+1)}6\), take the hypothesis that \(1^2 + 2^2 + \cdots + (n-1)^2 = \frac{(n-1)n(2n-1)}6\). Then:

\[\begin{aligned} 1^2 + 2^2 + \cdots + n^2 &= (1^2 + 2^2 + \cdots + (n-1)^2) + n^2 \\ &= \frac{(n-1)n(2n-1)}6 + n^2 \\ &= \frac{2n^3 - 3n^2 + n}6 + \frac{6n^2}6 \\ &= \frac{2n^3 + 3n^2 + n}6 \\ &= \frac{n(n+1)(2n+1)}6 \end{aligned}\]

Hence the answer is

\[ \left(\frac{n(n+1)}2\right)^2 - \frac{n(n+1)(2n+1)}6\]

for \(n = 100\).

Python Code

def p6(n=100):
	a = n * (n + 1) // 2
	b = n * (n + 1) * (2 * n + 1) // 6
	return a ** 2 - b

Previous Problem Next Problem

Back to Project Euler