Project Euler
Problem #6 - Sum Square Difference
Original Problem Statement
The sum of the squares of the first ten natural numbers is,
\(\hspace{1em}1^2 + 2^2 + \cdots + 10^2 = 385\)
The square of the sum of the first ten natural numbers is,
\(\hspace{1em}(1 + 2 + \cdots + 10)^2 = 3025\)
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is
\(\hspace{1em}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.
Iterative Approach
We're looking to calculate the difference between the sum of squares and the square of the sum.
To determine each of these, we could write code to simply iterate upwards for \(1\) to \(n\).
The code for this would be as follows:
The time-complexity of this code would be linear at \(O(n)\).
Can we do better? → YES
Summation Approach
Let's instead look directly at the difference that we want to calculate:
\(\hspace{1em}D = S_1 - S_2 = \displaystyle\left(\sum_{i=1}^n i\right)^2 - \sum_{i=1}^n i^2\)
It turns out that there are closed-form expressions for each of these terms!
Gauss's Little Formula
Let's first consider \(S_1\).
The sum of the numbers \(1\) through \(n\) has a well-known closed-form expression, occasionally known as Gauss's Little Formula:
The formula is the following:
\(\hspace{1em}\displaystyle\sum_{i=1}^n i = \frac{n \cdot (n+1)}{2}\)
Using this, we can produce a closed-form expression for the square-of-sum, i.e. \(S_1\), as follows:
\(
\begin{align*}
\hspace{1em}S_1 &= \displaystyle\left(\sum_{i=1}^n i\right)^2 \\
\hspace{1em} &= \displaystyle\left(\frac{n \cdot (n+1)}{2}\right)^2 \\
\hspace{1em} &= \displaystyle\frac{n^2 \cdot (n+1)^2}{4} \\
\end{align*}
\)
Hold onto this for a bit!
Pyramidal Numbers
Let's now consider \(S_2\).
Again there is a known formula for the sum of the squares of \(1\) through \(n\).
The formula has various names and appears in different contexts, such as the Square Pyramidal Numbers.
The closed-form expression is as follows:
\(\hspace{1em}\displaystyle\sum_{i=1}^n i^2 = \frac{n \cdot (n+1) \cdot (2n+1)}{6}\)
This is \(S_2\), precisely.
Complete Formula
With the previous two revelations, we can now find a singular expression for the difference \(D\), as follows:\( \begin{align*} \hspace{1em}D &= S_1 - S_2 & \text{Desired answer} \\ \hspace{1em} &= \displaystyle\frac{n^2 \cdot (n+1)^2}{4} - \frac{n \cdot (n+1) \cdot (2n+1)}{6} & \text{Substitute with previous formulæ} \\ \hspace{1em} &= \displaystyle\frac{3 \cdot n^2 \cdot (n+1)^2}{12} - \frac{2 \cdot n \cdot (n+1) \cdot (2n+1)}{12} \\ \hspace{1em} &= \displaystyle\frac{3 \cdot n^2 \cdot (n+1)^2 - 2 \cdot n \cdot (n+1) \cdot (2n+1)}{12} \\ \hspace{1em} &= \displaystyle n \cdot (n+1) \cdot \frac{3 \cdot n \cdot (n+1) - 2 \cdot (2n+1)}{12} \\ \hspace{1em} &= \displaystyle n \cdot (n+1) \cdot \frac{(3n^2 + 3n) - (4n + 2)}{12} \\ \hspace{1em} &= \displaystyle n \cdot (n+1) \cdot \frac{3n^2 - n - 2}{12} \\ \hspace{1em} &= \displaystyle n \cdot (n+1) \cdot \frac{3n^2 - 3n + 2n - 2}{12} \\ \hspace{1em} &= \displaystyle n \cdot (n+1) \cdot \frac{(3n+2) \cdot (n-1)}{12} \\ \hspace{1em} &= \displaystyle\frac{n \cdot (n-1) \cdot (n+1) \cdot (3n+2)}{12} \\ \end{align*} \)
Now that we have a single formula, we no longer need to iterate!
The code for this would be as follows:
The time-complexity of this solution would be essentially \(O(1)\), as we've eliminated any need for iteration.
Answer
We can easily calculate the answer by hand, as follows:
\(
\begin{align*}
\hspace{1em}D &= \displaystyle\frac{n \cdot (n-1) \cdot (n+1) \cdot (3n+2)}{12} \\
\hspace{1em} &= \displaystyle\frac{100 \cdot (100-1) \cdot (100+1) \cdot (3\cdot 100+2)}{12} \\
\hspace{1em} &= \displaystyle\frac{100 \cdot 99 \cdot 101 \cdot 302}{12} \\
\hspace{1em} &= 25 \cdot 33 \cdot 101 \cdot 302 \\
\hspace{1em} &= 25 \cdot 33 \cdot 101 \cdot 302 \\
\hspace{1em} &= 26,164,150 \\
\end{align*}
\)
My Solution on GitHub
The full Python3 code for my solution implementation can be found here: GitHub Solution
