0x0006 - 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.

The area under the graph approximates the sum of the natural numbers, so: With En as the error on Sn: 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) : Working out the integral, we get: Replacing the integral: Simplifying the sum, adding it up: So substituting our value for En we get:

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:

Saying the sum to n is one term less than the sum to (n+1)

We expand the sums:

As expected, the cubic terms cancel, and we rearrange the formula to have the sum of the squares on the left: Expanding the cube and summing the sums: Adding like terms: Dividing throughout by 3 gives us the formula for the sum of the squares:

Proof 2: (using calculus)

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

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 error is the area of each square less the area under the graph:

Integrating:

Expanding terms:

Collecting like terms:

And summing:

The error is:

Substituting for En in:

which is:

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