# Problem 6

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.

Both the required subroutines are straight forward to implement.  The square of the sum grows much quicker than the sum of the squares.

# Solution

`#!/usr/bin/pythondef sumsquare(val):  #Returns the sum of the squares.    ss = 1    for each in range(2,val+1): ss = ss + each**2    return ss    def squaresum(val):  #Returns the squares of the sums.    ss = 1    for each in range(2,val+1): ss = ss + each    return ss**2if __name__ == '__main__' :    import sys    val = int(sys.argv) # Bad Code, assumes input is an integer    print (sumsquare(val))    print (squaresum(val))     print (squaresum(val)-sumsquare(val))`

The answer is 25502500-338350=25164150.

# Approach

I first define two functions which compute the desired sums.  The algorithms are clear and concise in python.  I did notice that the for loop, which presumably gets allocated all at once, uses an enormous amount of memory.

# Benchmarks

Python3 really did poorly here and Jython crashed.  Pypy was the most efficient as before.  Java crashed with an out of memory error so I decided to look at memory usage.  Python 3 was actually the most memory efficient followed by Pypy and Python 2.  Jython memory usage was reported despite the crash.  I have read that pypy is implemented on stackless python, and expected to see stack usage with the other versions.  However, none of the python versions used any stack memory.

`CPU UsageProblem #6 Benchmarkstime python factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 0m37.971suser 0m36.458ssys 0m1.360stime python -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 0m38.709suser 0m37.198ssys 0m1.408stime python3 factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 1m16.192suser 1m16.133ssys 0m0.008stime python3 -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 1m16.864suser 1m16.805ssys 0m0.008stime pypy factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 0m10.756suser 0m10.729ssys 0m0.016stime pypy -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000real 0m10.672suser 0m10.649ssys 0m0.012stime jython factdiff.py 100000000java.lang.OutOfMemoryError: java.lang.OutOfMemoryError: Java heap spacereal 0m38.766suser 1m48.291ssys 0m1.680sMemory Usage/usr/bin/time -f "%M" python factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"12750032"/usr/bin/time -f "%M" python -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"12754544"/usr/bin/time -f "%M" python3 factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"30688"/usr/bin/time -f "%M" python3 -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"39264"/usr/bin/time -f "%M" pypy factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"76832"/usr/bin/time -f "%M" pypy -O factdiff.py 1000000003333333383333333500000002500000050000000250000000000000025000000166666664166666650000000"76864"/usr/bin/time -f "%M" jython factdiff.py 100000000Command exited with non-zero status 25517467504`

# Conclusion

The way I implemented this problem led to large memory usage.  I have 16 GB of memory so I didn't run out, but I noticed a jump of several GB when I ran the benchmarks.  Python 2 used almost 13 GB as reported by the time function.  Python3 was the most memory efficient of the versions, but also the slowest to run.

The answer was 25164150.