(14 votes, average: 5.00 out of 5)

Project Euler 6: Find the difference between the sum of the squares and the square of the sum

Project Euler 6 Problem Description

Project Euler 6: 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.

Analysis

Solving this problem requires the knowledge of two established formulas:
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}$

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:

We apply these formulas to our range [1,n] and find the difference. These formulas 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 formula:

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

Avoiding loops to solve these types of problems in favor of formulas and closed-form calculations becomes apparent with the more demanding hackerRank Project Euler 6 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.

This program and method
solves all test cases for
Project Euler 6 on HackerRank

Project Euler 6 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 6 Solution Python 2.7 source.

Afterthoughts

Project Euler 6 Solution last updated