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.

Python Solution

There are several ways that come to mind as to how one could write this. My solution is not the shortest, but should run relatively quickly.

import time
 
def square_of_sum(n):
    sum = ((n+1)*n)/2
    squared = sum**2
    return squared
 
def sum_of_squares(n):
    sum = 0
    for i in range(n + 1):
        sum += i**2
    return sum
 
def difference(n):
    return square_of_sum(n) - sum_of_squares(n)
 
start = time.time()
diff = difference(100)
elapsed = (time.time() - start)
 
print "result %s returned at %s seconds." % (diff,elapsed)

This produces the result:

result 25164150 returned at 6.69956207275e-05 seconds.

Cython Solution

This should run slightly more quickly than the Python code.

%cython
 
import time
 
cdef square_of_sum(unsigned int n):
    cdef unsigned long int sum = ((n+1)*n)/2
    cdef unsigned long int squared = sum**2
    return squared
 
cdef sum_of_squares(unsigned int n):
    cdef unsigned long int sum = 0
    cdef unsigned int iter = 1
    while iter <= n:
        sum += iter**2
        iter += 1
    return sum
 
cdef difference(unsigned int n):
    return square_of_sum(n) - sum_of_squares(n)
 
start = time.time()
diff = difference(100)
elapsed = (time.time() - start)
 
print "result %s returned in %s seconds." % (diff,elapsed)

The above code produces the following result.

result 25164150 returned in 1.90734863281e-05 seconds.

Thus, the Cython code is roughly 3.5 times as fast as the Python code.


Comments are closed