Sum of Squares/Square of Sum Difference 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?
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.