Detailed mathematical approach

Problem Summary

We seek the smallest value of \(x+y+z\) with \(x \gt y \gt z \gt 0\) such that all six pairwise sums and differences

$x+y,\quad x-y,\quad x+z,\quad x-z,\quad y+z,\quad y-z$

are perfect squares. A direct search over triples \((x,y,z)\) is far too loose, because each candidate would still need six square tests and there is no obvious numerical range for the three variables separately.

The implementations therefore search in a more structured space: instead of guessing \(x\), \(y\), and \(z\) directly, they guess a small set of square quantities from which every other required square is forced. That is the key mathematical simplification.

Mathematical Approach

The six square conditions are strongly linked. Once the relations between them are written down explicitly, the problem collapses to a search over three squares rather than three unrestricted integers.

Naming the Six Square Quantities

Let

$A=x+y,\qquad B=x-y,\qquad C=x+z,\qquad D=x-z,\qquad E=y+z,\qquad F=y-z.$

Every one of \(A,B,C,D,E,F\) must be a perfect square. Because \(x \gt y \gt z \gt 0\), they satisfy the order relations

$A \gt C \gt D \gt 0,\qquad E \gt F \gt 0,\qquad B \gt 0.$

These six quantities are not independent. From the definitions, simple subtraction and addition give

$F=A-C,\qquad E=A-D,\qquad B=C-E=C+D-A.$

So once \(A\), \(C\), and \(D\) are known, the other three quantities are forced. The whole problem is therefore equivalent to finding three squares \(A \gt C \gt D \gt 0\) such that

$A-C,\qquad A-D,\qquad C+D-A$

are also positive perfect squares.

Recovering \(x\), \(y\), and \(z\)

After choosing a valid triple \((A,C,D)\), the original integers are reconstructed by solving the linear system

$x+z=C,\qquad x-z=D,\qquad x+y=A.$

This gives

$x=\frac{C+D}{2},\qquad z=\frac{C-D}{2},\qquad y=A-\frac{C+D}{2}=\frac{E+F}{2}.$

The target sum is then

$x+y+z=A+\frac{C-D}{2}.$

So the square \(A=x+y\) plays a central role: it is the largest required square and it also appears directly in the final objective.

Switching from Squares to Square Roots

The implementations do not loop over arbitrary perfect squares stored in tables. They iterate over square roots. Write

$A=a^2,\qquad C=c^2,\qquad D=d^2,\qquad a \gt c \gt d \gt 0.$

Then the three derived quantities become

$F=a^2-c^2,\qquad E=a^2-d^2,\qquad B=c^2+d^2-a^2.$

The search condition is now very compact: choose roots \(a\), \(c\), \(d\) such that all three expressions above are positive perfect squares. Once that happens, the formulas for \(x\), \(y\), and \(z\) are immediate.

Parity as a Built-In Pruning Rule

The formulas

$x=\frac{c^2+d^2}{2},\qquad z=\frac{c^2-d^2}{2}$

show that \(c^2\) and \(d^2\) must have the same parity. A square has the same parity as its root, so \(c\) and \(d\) must both be odd or both be even. The implementations exploit this directly: once \(c\) is fixed, the inner loop only tests values of \(d\) with matching parity. That removes half of the innermost candidates before any square check is even attempted.

The positivity condition

$B=c^2+d^2-a^2 \gt 0$

is another strong filter. It says the largest square \(a^2\) cannot be too far above the other two, because otherwise \(x-y\) would become non-positive.

Worked Example: The Minimal Solution

The first successful root triple found by the search is

$a=925,\qquad c=765,\qquad d=533.$

So the three base squares are

$A=925^2=855625,\qquad C=765^2=585225,\qquad D=533^2=284089.$

The three forced quantities are then

$F=A-C=270400=520^2,$

$E=A-D=571536=756^2,$

$B=C+D-A=13689=117^2.$

Now reconstruct the original triple:

$x=\frac{C+D}{2}=\frac{585225+284089}{2}=434657,$

$y=\frac{E+F}{2}=\frac{571536+270400}{2}=420968,$

$z=\frac{C-D}{2}=\frac{585225-284089}{2}=150568.$

All six required values are perfect squares:

$x+y=855625=925^2,\qquad x-y=13689=117^2,$

$x+z=585225=765^2,\qquad x-z=284089=533^2,$

$y+z=571536=756^2,\qquad y-z=270400=520^2.$

Therefore

$x+y+z=434657+420968+150568=1006193.$

How the Code Works

The C++, Python, and Java implementations all follow the same algebraic search. The outer loop chooses a root \(a\), which fixes the largest square \(A=x+y=a^2\). The middle loop chooses a smaller root \(c\), which fixes \(C=x+z=c^2\), and immediately checks whether

$F=a^2-c^2=y-z$

is a perfect square. Most candidates fail here, so this is an efficient early rejection step.

For each surviving pair \((a,c)\), the inner loop chooses \(d\) with the same parity as \(c\), guaranteeing that the half-sum formulas for \(x\) and \(z\) stay integral. It then forms

$E=a^2-d^2,\qquad B=c^2+d^2-a^2$

and requires both to be positive perfect squares. If they are, the implementation reconstructs \(x\), \(y\), and \(z\) and performs one final direct verification of all six expressions \(x\pm y\), \(x\pm z\), and \(y\pm z\).

That final verification is mathematically redundant once every identity above is correct, but it is a useful safety check. It also makes the three language versions easy to compare: they all implement exactly the same sequence of derived-square tests followed by a direct confirmation.

Complexity Analysis

If the square-root search limit is \(L\), the raw nested loops are cubic, so the worst-case running time is \(O(L^3)\). The parity restriction removes half of the innermost iterations, and the square tests on \(a^2-c^2\), \(a^2-d^2\), and \(c^2+d^2-a^2\) prune the overwhelming majority of candidates before the expensive final six-square confirmation.

The memory usage is \(O(1)\): the algorithm keeps only a fixed number of integers and square-test temporaries. In practice it is fast because it never searches blindly over all \((x,y,z)\); instead it walks through the much smaller state space of compatible square differences.

Footnotes and References

1. Problem page: Project Euler 142 - Perfect Square Collection
2. Perfect square: Wikipedia - Square number
3. Difference of two squares: Wikipedia - Difference of two squares
4. Diophantine equation: Wikipedia - Diophantine equation
5. Parity: Wikipedia - Parity