Project Euler problem 6

Source code available on GitHub.

Here’s the problem:

     The sum of the squares of the first ten natural numbers is, \[1^2 + 2^2 + \cdots + 10^2 = 385\] The square of the sum of the first ten natural numbers is, \[(1 + 2 + \cdots + 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.

Well, the question looks long but I think this is actually the simplest problem we’ve had yet. The sum of all integers from 1 to n is

    \[\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.\]

It’s not hard to see why. In fact, there’s a brilliant story about how the young Gauss found this trick when an annoyed teacher gave him this problem to keep him occupied, expecting it to take him a long time to manually sum all the numbers.

Let this sum be S, so that

    \[S = 1 + 2 + 3 + \cdots + (n-1) + n.\]

We write the sum backwards as

    \[S = n + (n-1) + (n-2) + \cdots + 2 + 1\]

and add the two equations term-by-term, getting

(1)   \begin{align*} 2S &= (n+1) + (2+n-1) + (3+n-2) + \cdots + (n-1+2) + (n+1) \\ &= (n+1) + (n+1) + (n+1) + \cdots + (n+1) + (n+1). \end{align*}

It’s easy to see that this is n lots of n+1 and so 2S = n(n+1). Divide by two, and we have S = \frac{n(n+1)}{2} just as we were hoping for.

A quick implementation of this as a function is:

def sumofintegers(n):
    return n*(n+1)/2

A very similar result for the sum of squares takes a just a little more effort to show, but I won’t prove it here:

    \[\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}.\]

A similar Python function would be:

def sumofsquares(n):
    return n*(n+1)*(2*n+1)/6

So, all we need to do is take the difference of the sum of squares and the square of the regular sum, up to n. We’re done!

def sumofsquares(n):
    return n*(n+1)*(2*n+1)/6

def sumofintegers(n):
    return n*(n+1)/2

def specialdifference(n): # Finds the difference between the sum of squares and the square sum up to n
    return abs(sumofsquares(n) - (sumofintegers(n))**2)

print(specialdifference(100))

Leave a Reply

Your email address will not be published. Required fields are marked *