6: Sum square difference

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

\[ 1^2 + 2^2 + ... + 10^2 = 385 \]

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

\[ (1+2+...+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\).

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Submit your answer

Your Solution

Lunch this notebook and try to create your own solution!

Tip: look for the launch button (🚀) in the top right corner!

def problem6(N):  # N=number of numbers
    # Try your solution here
    return solution

# Testing:
unittest.main(argv=[''], verbosity=2,exit=False)

# Printing Project Euler Solution
# print(problem6(100))

My solution

Spoiler Alert!!

See my solution bellow

Using list comprehension:

def problem6(N):
    sq_sum = sum([i**2 for i in range(N+1)])
    sum_sq = sum([i for i in range(N+1)])**2
    return sum_sq - sq_sum

# Testing
unittest.main(argv=[''], verbosity=2,exit=False)

# Performance of first solution:
%timeit problem6(1000000)

434 ms ± 532 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

In the solution above I used 2 list comprehension over the same interval, so a faster solution is perform both operations in just one loop:

def problem6(N):
    sq_sum = 0
    sum_sq = 0
    for i in range(N+1):
        sq_sum += i*i
        sum_sq += i
    return sum_sq*sum_sq - sq_sum

# Testing
unittest.main(argv=[''], verbosity=2,exit=False)

# Performance of second solution
%timeit problem6(1000000)

155 ms ± 65.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Finally, instead using loops, we could use some math knowledge. For instance, the sum of natural terms series can be written as:

\[\sum_{k=1}^N k = \frac{N(N+1)}{2}\]

and, the sum of squared natural numbers is:

\[\sum_{k=1}^N k^2 = \frac{N(N+1)(2N+1)}{6}\]

def problem6(N):
    sum_sq = N*(N+1)*N*(N+1)//4
    sq_sum = N*(N+1)*(2*N+1)//6
    return sum_sq - sq_sum

# Testing
unittest.main(argv=[''], verbosity=2,exit=False)

# Performance of third solution
%timeit problem6(1000000)

783 ns ± 8.52 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

The difference between the sum of the squares of the first one hundred natural numbers and the square of the sum is:

# Printing Project Euler Solution
problem6(100)

25164150