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 cannon balls:

Project Euler 6

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

\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 trials 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) A000330: Square pyramidal numbers: a(n) = 0^2 + 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6.