Project Euler Problem 6

Jun 30th, 2022

5 min read

Sum Square Difference

Project Euler presents the following Problem #6:

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.

A very straightforward solution takes advantage of LongRange implementing the Iterable interface (via its superclass LongProgression), so that standard library functions, sum() and sumOf(), can be used to return the expected result. LongRange is used instead of IntRange to account for any overflow from either extension function.

1fun sumSquareDiffBrute(limit: Int): Long {
2    val range = 1L..limit
3    val sumOfRange = range.sum()
4    val squareOfSum = sumOfRange * sumOfRange
5    val sumOfSquares = range.sumOf { it * it }
6    return squareOfSum - sumOfSquares
7}

Note that the original problem calls for:

... the difference between the sum of the squares ... and the square of the sum.

But line 6 has the subtraction order reversed... 🤔

If you're worried about returning a negative value, wrapping the subtraction in abs() (which requires an import statement) would easily avoid that; however, this subtraction order will not produce a negative result.

Given that all elements $a_i$ in the range are non-negative, the square of the sum will always be greater than or equal to the sum of the squares:

\begin{align*} (a_1+a_2+\ldots+a_n)^2&\ge a_1^2+a_2^2+\ldots+a_n^2\\[.5em] (a_1^2+a_2^2+\ldots+a_n^2)+2((a_1a_2+\ldots+a_1a_n)+(a_2a_3+\ldots+a_2a_n)+\ldots+a_{n-1}a_n)&\ge a_1^2+a_2^2+\ldots+a_n^2\\[.5em] 2((a_1a_2+\ldots+a_1a_n)+(a_2a_3+\ldots+a_2a_n)+\ldots+a_{n-1}a_n)&\ge 0\\[.5em] (a_1a_2+\ldots+a_1a_n)+(a_2a_3+\ldots+a_2a_n)+\ldots+a_{n-1}a_n&\ge 0 \end{align*}

From 2 Extensions To 1

Let's say your original plan was to use a simple for loop and accumulate both values simultaneously. Or maybe you don't like the idea of looping over a range twice to essentially do the same thing two different ways.

fold() is an aggregate function that applies a provided operation to a collection using an initial value as the accumulated value on the first step. In this case, we can store the cumulative values for sumOfRange and sumOfSquares in a Pair that is updated with every step through the range:

1fun sumSquareDiffBrute(n: Int): Long {
2     val range = 2L..n
3     val (sumOfRange, sumOfSquares) = range.fold(1L to 1L) { acc, num -> 
4        acc.first + num to acc.second + num * num 
5     }
6     return sumOfRange * sumOfRange - sumOfSquares
7}

Line 2: The range starts from 2 instead of 1 because the initial value provided to fold() on line 3 corresponds to the values for the number 1.

Line 3: Destructuring declaration of the final result of fold() improves code readability in the final calculation on line 6.

Maybe you'll find this alternative more reasonable. It might even give you a small performance boost. On my system, this version executed on average 31% faster than the original version when I pushed the upper constraints of n. But it was still not as fast as the solution described in the next section.

Optimized Solution

If you want to scale the problem beyond the first one hundred numbers, introducing some mathematics to the solution will help improve performance by switching to an O(1) time complexity.

If you've been following along since Project Euler Problem 1 🎉 then you're familiar with the summation method that returns the sum of the first $n$ natural numbers without having to rely on a linear O(n) time complexity. This will replace range.sum().

\sum_{i=1}^n i=\frac{n(n+1)}{2}

Conveniently, the sum of a sequence of squares can also be calculated with an O(1) time complexity using the following formula:

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

Consider reading more about square pyramidal numbers or this formula's proof by induction.

1fun sumSquareDiff(n: Int): Long {
2    val sumOfRange = n.gaussSum()
3    val sumOfSquares: Double = n / 6.0 * (n + 1) * (2 * n + 1)
4    return sumOfRange * sumOfRange - sumOfSquares.toLong()
5}
6
7fun Int.gaussSum(): Long  = 1L * this * (this + 1) shr 1

Line 7: Depending on the size of the argument n, conversion of very large Double values to Long values can lead to large rounding losses, so my helper function replaces integer division by 2 with a single bitwise right shift. Remember that $n>>1=\dfrac{n}{2^1}$ .

Speed Comparison

Here are the average execution times (from a benchmark test of 1000 iterations) showing the advantage of using the optimized solution when scaled:

n	BRUTE FORCE (ms)	OPTIMIZED (ns)
100	3.16	2.4e+04
10_000	7.55	2.9e+04

Here's the full source code for this problem (and its corresponding test suite).

This solution set is also available in Python and in C++ on my GitHub.

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️➕🟦🔺

Project Euler Problem 6

Sum Square Difference

Brute Force

Optimized Solution

Speed Comparison