Project Euler 006

Problem:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 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:

1. Brute-force approach:


def sum_of_sq(n) :
    res1 = 0
    for i in range(1, n+1) :
        res1 += i*i
    return res1

def sq_of_sum(n) :
    res2 = 0
    for i in range(1, n+1) :
        res2 += i
    res2 = res2**2
    return res2

a = 100
print sq_of_sum(a) - sum_of_sq(a)

2. Efficient approach:


n = 100
sum1 = (n * (n + 1) / 2)**2
sum2 = n * (n + 1) * (2 * n + 1) / 6
print sum1 - sum2

Analysis:

In the brute-force method, two functions are defined. The first one sum_of_sq(n) returns the sum of squares of the first n Natural numbers. This is calculated by adding squares of first n natural numbers. The sum is stored in the variable res1. The second function, sq_of_sum(n) first calculates the sum of first n natural numbers, squares the sum and returns it as result. The variable holding this value is res2. In the program, the variable a is assigned a value 100, as we need to find the difference between the square of the sum and the sum of squares of first 100 natural numbers. The required answer is printed by calculating the difference in values returned by the two functions.

In the efficient approach, we get the result by applying the formulas for summation of natural numbers and summation of square of natural numbers and finding their difference.

Sn = n(n+1)/2 Sn2 = n(n+1)(2n+1)/6

Running times:

Using Python 2.7 under the Ubuntu 10.10 terminal, the following running times were clocked:

1. Brute-force approach: 46.968 microseconds.

2. Efficient approach: 21.934 microseconds, which is about 46.7% of the time taken by the brute-force approach.

Proofs:

I) Proofs of the formula for sum of natural numbers:

Proof 1:

the numbers put into an rectangle

This is an example for n = 5. We see that we have a big rectangle with the its sides 5 and 5+1. The rectangle has 2(1 + 2 + 3 + 4 + 5) squares inside. So 2(1 + 2+ 3 + 4 + 5) = 5(5+1) and 1 + 2 + 3 + 4 + 5 = \frac{5(5+1)}{2}

The same way, for any n, we construct a rectangle with its sides n and n+1 that has 2(1+2+…+n) squares inside.

Proof 2: (using summation)

1+2+…+(n-1)+n=S_n

(1+2+….+(n-1)+n) + (1+2+….+(n-1)+n) = 2S_n

(1+2+….+(n-1)+n) + (n+(n-1)+….+2+1) = 2S_n

if we look at the sum above we notice that we have n columns of numbers and that on each column we have two numbers with the sum n+1, so:

n(n+1) = 2S_n

S_n=\frac{n(n+1)}{2}

Proof 3: (using mathematical induction)

Let’s write S_n=1+2+…+n like this: ,

S_n=\sum_{i=1}^{n}i

. It’s shorter.

We will use induction to prove that:

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

For n = 1 it is true that

1 = \frac{1(1+1)}{2}

2)We know that

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

is true and we want to prove it for n+1. We have to prove that:

S_{n+1}=\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}

if we add n+1 to each side of the next identity:

S_n=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}

we have:

S_{n+1}=S_n+(n+1)=\sum_{i=1}^{n}i+n+1=\frac{n(n+1)}{2}+n+1

equivalent with:

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

and this leads to:

S_{n+1}=\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}

Proof 4: (using calculus)

In the graph below, we have the first few natural numbers shown as rectangles on the graph y=x. Rectangles representing the first four natural numbers under the line y equals x.

The area under the graph approximates the sum of the natural numbers, so: S sub n is approximately the integral of x from zero to n, which equals n squared over two. With En as the error on Sn: S sub n equals n squared over two plus the error E sub n. Each of our rectangles in the graph have an area k∙1, so our error is k minus the area under the graph between (x=k-1 and x=k) : E sub n expressed as a sum of rectangle areas minus integrals from k minus one to k. Working out the integral, we get: The integral of x from k minus one to k equals k minus one half. Replacing the integral: E sub n equals the sum of k minus the sum of k plus one half. Simplifying the sum, adding it up: E sub n equals the sum of one half from k equals one to n, or n over two. So substituting our value for En we get: S sub n equals n squared over two plus n over two.

II) Proofs of the formula for sum of squares of natural numbers:

Besides mathematical induction, we have the following two proofs:

Proof 1: (using summation)

We can write:

The sum of k cubed rewritten by shifting the summation index. Saying the sum to n is one term less than the sum to (n+1)

We expand the sums: The shifted cubic sum expanded into sums of k cubed, k squared, k, and one.

As expected, the cubic terms cancel, and we rearrange the formula to have the sum of the squares on the left: Three times the sum of k squared expressed using a cubic term and lower-order sums. Expanding the cube and summing the sums: Adding like terms: Dividing throughout by 3 gives us the formula for the sum of the squares:

The sum of k squared from zero to n equals n times n plus one times two n plus one, divided by six.

Proof 2: (using calculus)

The following graph is of y=x2, and the rectangles represent the sum of the squares.

Rectangles representing the first three squared natural numbers above the curve y equals x squared.

y=x2 represents part of the sum of the squares, and the rest is the area between each rectangle and the function.

Looking at the graph, it seems the difference, or error En, varies; at first it seems bigger than the term, and it gradually gets less.

The sum of the squares, where En is the error: The sum of k squared equals the integral of x squared from zero to n plus error E sub n.

The error is the area of each square less the area under the graph: E sub n expressed as a sum of square areas minus integrals of x squared.

Integrating: E sub n after evaluating each integral of x squared.

Expanding terms: E sub n after expanding the difference of cubes.

Collecting like terms: E sub n equals the sum of k minus one third.

And summing: E sub n equals n times n plus one over two minus n over three.

The error is: E sub n equals n squared over two plus n over six.

Substituting for En in: The sum of k squared equals n cubed over three plus n squared over two plus n over six.

which is:

The sum of k squared from zero to n equals n times n plus one times two n plus one, divided by six.

The general formula for finding sum of powers of natural numbers can be found here.