Sum of Squares/Square of Sum Difference

Question

I am doing Project Euler problem #6. This is the question it asks:

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

$1ドル^2 + 2^2 + \ldots + 10^2 = 385$$

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

$$(1 + 2 + \ldots + 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.

My implementation in Python is as follows:

def sum_of_squares(n):
 return sum([i**2 for i in range(1, n+1)])
def square_of_sum(n):
 return sum(range(1, n+1)) ** 2
print square_of_sum(100) - sum_of_squares(100)

It works but I was wondering if my implementation is good and fast enough?

Answer 1

Implementation is good indeed, but I have some reservations calling it fast. Its complexity is O(n). As usual (including, but not limited to, Project Euler), an ultimate optimizer is math. Recall that

$$ 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$

and

$$ 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$$

so the result

$$ \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n+1)(3n+2)}{12}$$

can be achieved in O(1) time.

• domen: Btw. this might be a spoiler for a different Euler problem. I've often seen same problems with increased difficulty on the site.

Answer 2

Your implementation looks fine. This calculation is so trivial for a computer to do that it's not worth spending much time optimizing the implementation.

That said, the fact that you called print without parentheses indicates that you are using Python 2. In Python 2, xrange() would be slightly preferable to range().

Alternatively, keep using range(), and call print() with parentheses to make your program compatible with Python 3.

• Yuushi: Or use a from __future__ import print_function.

Answer 3

One minor tweak I would suggest to your current implementation:

def sum_of_squares(n):
 return sum([i**2 for i in range(1, n+1)])

You don't need to built the list; sum will take the bare generator expression as an argument:

def sum_of_squares(n):
 return sum(i**2 for i in range(1, n+1)) # or xrange in 2.x

This will be quicker and also uses less memory (see e.g. here).