Project Euler Problem 6 Solution

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

$$\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 $\frac{10(11)}{2} = 55$, and $55^2 = 3025\space\checkmark$.

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 $\frac{10(11)(21)}{6} = 385\space\checkmark$.

Finally, calculate the difference, $3025-385 = 2640\space\checkmark$. 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: $\frac{10(9)(11)(32)}{12} = 2640\space\checkmark$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 6

HackerRank Project Euler 6 requires you to solve 10,000 test cases with N ≤ 10,000.

Python Source Code

for _ in range(int(input())):
    N = int(input())
    print(N*(N-1)*(N+1)*(3*N+2)//12)

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.