Project Euler Problem #6:

Problem #6 of Project Euler is yet another example of how having a decent background in math can save you a lot of hassle when solving coding problems. The question reads:

Project Euler Problem 6: Sum Square Difference
The sum of the squares of the first ten natural numbers is

1^2 + 2^2 + . . . + 10^2 = 385

The square of the sum of the first ten natural number is

(1 + 2 + 3 + . . . + 10)^2 = 55^2 = 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.

Clearly each of these values can be obtained by simple iteration. Add up i^2 as i ranges from 1 to 10, add up i in the same range, square the second result, and you’re done. However, we can actually solve this question entirely with some simple formulas.

Solution #1: Formulaic Approach

The first part of the question involves finding the sum of the squares of the first n natural numbers. It is well known that this sum is equal to n(n+1)(2n+1)/6. We can prove this claim easily with induction. When n = 1, the claim is true as 1^2 = 1*2*3/6 = 1. Now assume the claim is true for n = x. Then 1^2+2^2+ . . . + x^2 = x(x+1)(2x+1)/6. Adding (x+1)^2 to both sides, we get 1^2 + 2^2 + . . . + x^2 + (x+1)^2 = (2x^3+3x^2+x + 6x^2 + 12x + 6)/6 = (2x^3+9x^2+13x+6)/6 = (x+1)(x+2)(2x+3)/6. Thus, the inductive step is done, and therefore the claim is true. Therefore, we can find the sum of the squares with a formula.

The second part of the question involves finding the square of the sum of the first n natural numbers. It suffices to find a formula for the sum of the first n natural numbers. This sum is called the nth triangular number, as it represents the number of dots in an equilateral triangle made up of n rows of dots. It is well known that the nth triangular number is n(n+1)/2. Once again, we can prove this claim with induction. The base case is true as 1 = 1*2/2 = 1. Now assume the claim is true for n = x. Thus, 1 + 2 + . . . + x = x(x+1)/2. Adding x+1 to both sides, we get 1 + 2 + . . . + x + (x+1) = (x^2+x+2x+2)/2 = (x^2+3x+2)/2 = (x+1)(x+2)/2. Thus, the inductive step is done, and the claim is true. Squaring this result, we get the formula (n^2*(n+1)^2)/4. As it turns out, you can show through induction that this formula provides the sum of the cubes of the first n natural numbers. Therefore, this value will be greater than or equal to the value from the first part.

Putting the results from each part together, we get a very short program. Here is an implementation of this method in Python 2.7:

'''
Author: Walker Kroubalkian
Formulaic Approach to Project Euler Problem #6
'''

import time

def projectEulerProblemSix(n):
    return n*n*(n+1)*(n+1)/4 - n*(n+1)*(2*n+1)/6

start = time.time()
print projectEulerProblemSix(100)
print ("--- %s seconds ---" % (time.time() - start))

'''
Prints

25164150
--- 8.82148742676e-06 seconds ---

for input of n = 100
'''

As expected, the formulaic approach absolutely crushes this problem. The formulas that were discussed above are quite common, and I probably won’t write out the proof for them in future posts.

Thank you for reading!