Problem 006: Sum Square Difference

From Project Euler:

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.

The brute-force algorithm for this is pretty simple, just run a loop and calculate the result:

(def N 101)

(defn square [x] (* x x))

(println (- (square (reduce + (range 1 N)))
            (->> (range 1 N)
                 (map square)
                 (reduce +))))

This runs pretty fast (note that the JVM takes 1.5s to start up on my machine):

$ time clj 6.clj
25164150

real 0m1.517s
user 0m3.001s
sys 0m0.133s

We can do better though. As we saw in Problem 001, we can use a formula to calculate the sum of numbers from 1 to $N$:
$$
\sum^n_{i=1} i = \frac{n(n+1)}{2}
$$
Or in Clojure:

(defn sumto [n] (quot (* n (+ n 1)) 2))

If we square this value, we get the square of the sums (the first value in our subtraction). This is O(1) rather than O(n).

Turns out there is also a formula for the sum of squares of a sequence:
$$
\sum^n_{i=1} i^2 = \frac{n(n+1)(2n+1)}{6}
$$
For more details, see here.

Writing this out in Clojure:

(defn sumto-sq [n] (quot (* n
                            (+ n 1)
                            (+ (* 2 n) 1))
                         6))

Combining them all together:

(def N 100)
(println (- (square (sumto N))
            (sumto-sq N)))

This also runs fast, and should run fast for any number that fits into a 64-bit integer¹:

$ time clj 6.clj
25164150

real 0m1.583s
user 0m3.043s
sys 0m0.140s

---

1 We may have to algebraically manipulate the formula a bit to avoid overflows but it should be doable.^↩