Detailed mathematical approach

Problem Summary

For the first \(n\) positive integers, compare two quantities:

$A_n=\left(\sum_{k=1}^{n} k\right)^2,\qquad B_n=\sum_{k=1}^{n} k^2.$

The problem asks for

$D_n=A_n-B_n.$

In the Project Euler instance, \(n=100\). The statement also gives the smaller checkpoint \(n=10\), where the answer is \(2640\).

Mathematical Approach

The implementations reduce the problem to two classical closed forms. The relevant mathematical objects are the ordinary sum

$S_n=\sum_{k=1}^{n} k,$

the sum of squares

$Q_n=\sum_{k=1}^{n} k^2,$

and the difference \(D_n=S_n^2-Q_n\).

Expanding the square reveals the real quantity

The phrase “square of the sum minus sum of the squares” hides a clean combinatorial identity. Expanding the square gives

$\left(\sum_{k=1}^{n} k\right)^2=\sum_{k=1}^{n} k^2+2\sum_{1\le i<j\le n} ij.$

Therefore

$D_n=2\sum_{1\le i<j\le n} ij.$

So the answer measures all cross-terms between distinct numbers. The invariant here is simple: every unordered pair \(\{i,j\}\) with \(i<j\) appears exactly twice in the square expansion, once as \(ij\) and once as \(ji\).

Closed form for the triangular sum

To compute \(S_n\), pair the first and last terms, the second and second-last terms, and so on:

$1+n=n+1,\qquad 2+(n-1)=n+1,\qquad 3+(n-2)=n+1.$

Each pair contributes \(n+1\). This leads to the classical triangular-number formula

$S_n=\frac{n(n+1)}{2}.$

This identity is the first ingredient used by the implementations.

Closed form for the square sum

For \(Q_n\), a compact derivation uses the telescoping identity

$(k+1)^3-k^3=3k^2+3k+1.$

Summing from \(k=1\) to \(n\) collapses the left-hand side:

$(n+1)^3-1=3\sum_{k=1}^{n} k^2+3\sum_{k=1}^{n} k+n.$

In terms of \(Q_n\) and \(S_n\), this is

$(n+1)^3-1=3Q_n+3S_n+n.$

Substitute \(S_n=\frac{n(n+1)}{2}\):

$3Q_n=(n+1)^3-1-\frac{3n(n+1)}{2}-n=\frac{n(n+1)(2n+1)}{2}.$

Hence

$Q_n=\frac{n(n+1)(2n+1)}{6}.$

Collapsing the difference to one polynomial

Now substitute the two closed forms into \(D_n=S_n^2-Q_n\):

$D_n=\left(\frac{n(n+1)}{2}\right)^2-\frac{n(n+1)(2n+1)}{6}.$

Factoring common terms gives a single polynomial expression:

$D_n=\frac{n(n+1)(3n^2-n-2)}{12}=\frac{n(n-1)(n+1)(3n+2)}{12}.$

The implementations use the first subtraction form directly, but this factorization shows even more clearly that the entire problem has been collapsed to a closed expression in \(n\).

Worked example: the checkpoint and the target case

For \(n=10\),

$S_{10}=55,\qquad Q_{10}=385,\qquad D_{10}=55^2-385=2640.$

This is the built-in checkpoint used to verify the formula. For the actual Euler input \(n=100\),

$S_{100}=5050,\qquad Q_{100}=338350,\qquad D_{100}=5050^2-338350=25164150.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical recipe: compute the triangular sum, compute the square-sum formula, square the first quantity, subtract the second, and print the result. No loop over \(1,2,\dots,n\) is required.

Shared evaluation pattern

The implementation first forms

$\frac{n(n+1)}{2}$

and

$\frac{n(n+1)(2n+1)}{6}.$

After that, the answer is just one subtraction. Each language version also checks the known case \(n=10\mapsto2640\) before reporting the default Project Euler case \(n=100\).

Arithmetic considerations

The compiled implementations use 64-bit integer arithmetic, while the Python version uses integer arithmetic naturally. For this problem size the intermediate values are comfortably within range, and the divisions by \(2\) and \(6\) are exact because the closed forms are integer-valued for every positive integer \(n\).

Complexity Analysis

A direct summation approach would already be modest at \(O(n)\) time, but the closed-form derivation removes iteration entirely. The running time is therefore \(O(1)\).

The memory usage is also \(O(1)\), since the computation stores only a fixed number of integer quantities. There is no table, recursion, or auxiliary array.

Footnotes and References

1. Problem page: Project Euler Problem 6
2. Triangular numbers: Wikipedia - Triangular number
3. Square pyramidal numbers: Wikipedia - Square pyramidal number
4. Arithmetic progressions: Wikipedia - Arithmetic progression
5. Power-sum formulas: Wikipedia - Faulhaber's formula