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.
A simplified approach
print (sum(range(101))**2 − sum(i*i for i in range(101)))
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):
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 552 = 3025 ✓.
2. The sum of the first n square numbers (square pyramidal numbers):
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 ✓. Getting to know 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:
And giving it a try with our example: 10(9)(11)(32) / 12 = 2640 ✓.
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.
- 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 'Σ'.