#### 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):

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 55^{2} = 3025✓.

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

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 come in 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:

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.

#### Python 2.7 Source

#### 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.

## Recent Comments