Project Euler Problem 6 Solution: Sum square difference

Project Euler Problem 6 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

A simplified approach

print (sum(range(101))**2 − sum(i*i for i in range(101)))

Text with a dashed underscore will highlight the code section being talked about when moused over or tapped.

Using loops to sum our objectives, and Python’s list comprehension structure, we can make a simple subtraction and print the difference. For the small upper bound of 100 it takes no time at all. But, this lacks the efficiency to solve the more demanding parameters of the HackerRank version. A better method will have to be discovered.

Calculating our objectives without looping

Solving this problem without using loops is achieved by implementing the following two established equations:
1. The sum of the first n natural numbers (called 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 a set of bowling pins arranged in the traditional triangular pattern:

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² = 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 a stack of marbles as shown below:

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

Finally, calculate the difference, 3025 – 385 = 2640 ✓. Knowing these equations is useful for solving other programming problems.

A compound formula

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}$

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

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 6

HackerRank requires you to solve up to 10,000 test cases with a higher limit of n ≤ 10,000. This is solved quickly by avoiding loops and using the closed–form calculations described above.

Python Source Code

# -*- coding: utf-8 -*-
n = int(input('first n natural numbers, n ='))
print ("Difference: (Σn)² - Σn² =", n*(n-1)*(n+1)*(3*n+2)//12)

Run Project Euler Problem 6 using Python on repl.it.

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.
The first line of the Python script, # -*- coding: utf-8 -*-, defines the character set and allows us to use UTF–8 characters such as the 'Σ'.