Select Page

#### Project Euler 16 Problem Statement

The sum of the squares of the first ten natural numbers is 1² + 2² + … + 10² = 385.

The square of the sum of the first ten natural numbers is (1 + 2 + … + 10)² = 55² = 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

Solving this problem is helped by knowing two established equations:
1. The sum of the first n numbers (triangular numbers, used in Project Euler Problem 1):

$\sum\limits_{i=1}^n i = \frac{n(n+1)}{2}$

For a visual example of triangular numbers, imagine setting bowling pins:

Let’s apply this equation to our example:
The square of the sum of the first ten natural numbers is 10(11)/2 = 55, and 552 = 3025✓.

2. The sum of the first n square numbers (square pyramidal numbers):

$\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

For a visual example of square pyramidal numbers, imagine stacking jaw breakers:

Now, let’s apply this equation to our example:
The sum of the squares of the first ten natural numbers is 10(11)(21)/6 = 385✓.

Finally, calculate the difference, 3025 – 385 = 2640✓. The answer to the example above, all done without loops. These equations will be useful for solving other problems.

Now, I guess for the purists one could perform the subtraction of these two summations and derive the following equation:

$\frac{n(n-1)(n+1)(3n+2)}{12}$

And giving it a try with our example: 10(9)(11)(32)/12 = 2640✓.

#### HackerRank version

Avoiding loops to solve these types of problems in favor of equations and closed-form calculations becomes apparent with the more demanding hackerRank version. It requires you to solve up to 10,000 test cases with a higher limit of n ≤ 10,000 in a fixed amount of time, typically less than a tenth of a second.

#### Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000217: Triangular numbers: a(n) = binomial(n+1,2) = n(n+1)/2 = 0 + 1 + 2 + ... + n.
Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000330: Square pyramidal numbers: a(n) = 0^2 + 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6.