Prob 0006 ‐ Sum Square Difference - maccergit/Euler GitHub Wiki

01

The naive direct approach is super easy in Python. It's pretty fast, and scales linear - so it's good up to a point (somewhere in the range of 1 million to 100 million).

02

We can use closed forms for both sums - the discussion paper on the problem site includes the derivation of the closed forms. For the square of the sum, we get :

\displaystyle \left(\sum_{i=1}^{limit} i\right)^2 = \left(\frac{limit(limit + 1)}{2}\right)^2

and for the sum of the squares, we get :

\displaystyle \sum_{i=1}^{limit} i^2 = \frac{limit(limit + 1)(2limit + 1)}{6}

This gives us the result in about 325 nanoseconds - at this resolution, we see a lot of noise, even when averaging a million runs for each data point. Investigating further shows an increase of a couple hundred nanoseconds when limit approaches $10^{15}$, which I attribute to the overhead of exact processing of very large numbers.

03

Expanding the square term and subtracting the sum of squares term can then be simplified to a single simplified closed form for the complete value :

\displaystyle \left(\sum_{i=1}^{limit} i\right)^2 - \sum_{i=1}^{limit} i^2 = \frac{limit(limit + 1)(3limit + 2)(limit - 1)}{12}

This runs slightly faster than the unsimplified version :