Project Euler

Perfect Square Collection

Find the smallest x + y + z with x > y > z > 0 such that all six quantities x+y, x-y, x+z, x-z, y+z, y-z are perfect squares.

Source sync Apr 19, 2026

Problem #0142

Level Level 05

Solved By 6,693

Languages C++, Python

Answer 1006193

Length 315 words

game_theorymodular_arithmeticbrute_force

Find the smallest $x + y + z$ with integers $x \gt y \gt z \gt 0$ such that $x + y$, $x - y$, $x + z$, $x - z$, $y + z$, $y - z$ are all perfect squares.

Problem 142: Perfect Square Collection

Mathematical Foundation

Theorem 1. Let $a^2 = x+y$ , $b^2 = x-y$ , $c^2 = x+z$ , $d^2 = x-z$ , $e^2 = y+z$ , $f^2 = y-z$ . Then the following Pythagorean-type identities hold:

$a^2 = c^2 + f^2$
$a^2 = d^2 + e^2$
$c^2 = b^2 + e^2$
$d^2 = b^2 + f^2$

Proof. Each identity follows from subtraction of the original definitions:

$a^2 - c^2 = (x+y) - (x+z) = y - z = f^2$ , so $a^2 = c^2 + f^2$ .
$a^2 - e^2 = (x+y) - (y+z) = x - z = d^2$ , so $a^2 = d^2 + e^2$ .
$c^2 - e^2 = (x+z) - (y+z) = x - y = b^2$ , so $c^2 = b^2 + e^2$ .
$d^2 - b^2 = (x-z) - (x-y) = y - z = f^2$ , so $d^2 = b^2 + f^2$ . $\square$

Theorem 2. The variables $x, y, z$ are recovered as:

x = \frac{a^2 + b^2}{2}, \quad y = \frac{a^2 - b^2}{2}, \quad z = \frac{c^2 - d^2}{2} = \frac{e^2 - f^2}{2}

For $x, y, z$ to be positive integers, $a \equiv b \pmod{2}$ , $c \equiv d \pmod{2}$ , and $e \equiv f \pmod{2}$ .

Proof. From the definitions: $x + y = a^2$ and $x - y = b^2$ , so $x = (a^2 + b^2)/2$ and $y = (a^2 - b^2)/2$ . For these to be integers, $a^2 \equiv b^2 \pmod{2}$ , i.e., $a \equiv b \pmod{2}$ . Positivity of $y$ requires $a > b$ , and positivity of $z$ requires $c > d$ (equivalently $e > f$ ). The other recovery formulas follow similarly. $\square$

Lemma 1. Identity (4) is redundant: it follows from identities (1)—(3).

Proof. From (1): $f^2 = a^2 - c^2$ . From (2): $d^2 = a^2 - e^2$ . From (3): $b^2 = c^2 - e^2$ . Then:

d^2 - b^2 = (a^2 - e^2) - (c^2 - e^2) = a^2 - c^2 = f^2

which is identity (4). $\square$

Lemma 2. For the ordering $x > y > z > 0$ , we need $a > c > e > 0$ , $a > d > f > 0$ , and $b > 0$ .

Proof. $x > y \iff b^2 = x - y > 0 \iff b > 0$ . $y > z \iff f^2 = y - z > 0 \iff f > 0$ . $x > z \iff d^2 > 0 \iff d > 0$ . The ordering among $a, c, e$ follows from $a^2 = c^2 + f^2 > c^2$ and $c^2 = b^2 + e^2 > e^2$ . $\square$

Editorial

Let a^2=x+y, b^2=x-y, c^2=x+z, d^2=x-z, e^2=y+z, f^2=y-z. Key relations: a^2 - f^2 = c^2 => a^2 = c^2 + f^2 c^2 - b^2 = e^2 => c^2 = b^2 + e^2 (and then d^2 = a^2 - e^2, verify b^2 + f^2 = d^2) Strategy: for each a, find all ways to write a^2 = c^2 + f^2. For each such (c, f), check if c^2 - b^2 = e^2 for some b, e with a^2 - e^2 = d^2 (perfect square) and b^2 + f^2 = d^2. Simpler: for each a, find all (c, f) with a^2 = c^2 + f^2. Then for each (c, f), iterate over e < c, check if c^2 - e^2 = b^2 (perfect square), and then check if a^2 - e^2 = d^2 (perfect square).

Pseudocode

INPUT: Find minimum x + y + z
OUTPUT: Smallest valid x + y + z

Complexity Analysis

Time: $O(A^{1+\epsilon})$ where $A$ is the value of $a$ at termination. The number of representations of $a^2$ as a sum of two squares is $O(a^\epsilon)$ (divisor-bounded). For each $a$ , we check $O(a^{2\epsilon})$ pairs of decompositions.
Space: $O(A^\epsilon)$ per value of $a$ for storing decompositions.

In practice, the search terminates at small $a$ (the answer has $a = 468$ ), making runtime negligible.

Answer

\boxed{1006193}

C++ project_euler/problem_142/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Problem 142: Perfect Square Collection
    // Find smallest x+y+z with x>y>z>0, all six sums/differences are perfect squares.
    //
    // Let a^2=x+y, b^2=x-y, c^2=x+z, d^2=x-z, e^2=y+z, f^2=y-z.
    // Relations: a^2 = c^2 + f^2, c^2 = b^2 + e^2, a^2 = d^2 + e^2 (when d<e or d>e)
    // Strategy: for each a, decompose a^2 = c^2 + f^2, then for each e < c,
    //   check if c^2 - e^2 = b^2, and a^2 - e^2 = d^2.

    long long best = LLONG_MAX;

    for (long long a = 3; a <= 1000; a++) {
        long long a2 = a * a;
        for (long long f = 1; f < a; f++) {
            long long c2 = a2 - f * f;
            if (c2 <= 0) break;
            long long c = (long long)sqrt((double)c2);
            if (c * c != c2) continue;
            if (c <= 0) continue;

            for (long long e = 1; e < c; e++) {
                long long b2 = c * c - e * e;
                if (b2 <= 0) continue;
                long long b = (long long)sqrt((double)b2);
                if (b * b != b2) continue;

                long long d2 = a2 - e * e;
                if (d2 <= 0) continue;
                long long d = (long long)sqrt((double)d2);
                if (d * d != d2) continue;

                // Verify b^2 + f^2 = d^2
                if (b2 + f * f != d2) continue;

                // Parity check
                if ((a2 + b2) % 2 != 0) continue;

                long long x = (a2 + b2) / 2;
                long long y = (a2 - b2) / 2;
                long long z = e * e - y;

                if (x > y && y > z && z > 0) {
                    long long s = x + y + z;
                    if (s < best) best = s;
                }
            }
        }
    }

    cout << best << endl;
    return 0;
}

Python project_euler/problem_142/solution.py

"""
Problem 142: Perfect Square Collection

Find the smallest x+y+z with x>y>z>0 such that
x+y, x-y, x+z, x-z, y+z, y-z are all perfect squares.

Let a^2=x+y, b^2=x-y, c^2=x+z, d^2=x-z, e^2=y+z, f^2=y-z.

Key relations:
  a^2 - f^2 = c^2  =>  a^2 = c^2 + f^2
  c^2 - b^2 = e^2  =>  c^2 = b^2 + e^2
  (and then d^2 = a^2 - e^2, verify b^2 + f^2 = d^2)

Strategy: for each a, find all ways to write a^2 = c^2 + f^2.
For each such (c, f), check if c^2 - b^2 = e^2 for some b, e
with a^2 - e^2 = d^2 (perfect square) and b^2 + f^2 = d^2.

Simpler: for each a, find all (c, f) with a^2 = c^2 + f^2.
Then for each (c, f), iterate over e < c, check if c^2 - e^2 = b^2
(perfect square), and then check if a^2 - e^2 = d^2 (perfect square).
"""

from math import isqrt

def solve():
    best = float('inf')
    best_xyz = None

    for a in range(3, 1001):
        a2 = a * a
        # Find all (c, f) with a^2 = c^2 + f^2, c > 0, f > 0
        for f in range(1, a):
            c2 = a2 - f * f
            if c2 <= 0:
                break
            c = isqrt(c2)
            if c * c != c2:
                continue
            if c <= 0:
                continue

            # Now find e such that c^2 - e^2 = b^2 (perfect square)
            # e must satisfy: e > 0, c^2 - e^2 > 0 => e < c
            # Also: a^2 - e^2 must be a perfect square d^2
            # And: b^2 + f^2 = d^2
            for e in range(1, c):
                b2 = c * c - e * e
                if b2 <= 0:
                    continue
                b = isqrt(b2)
                if b * b != b2:
                    continue

                # Check a^2 - e^2 = d^2
                d2 = a2 - e * e
                if d2 <= 0:
                    continue
                d = isqrt(d2)
                if d * d != d2:
                    continue

                # Verify b^2 + f^2 = d^2
                if b2 + f * f != d2:
                    continue

                # Compute x, y, z
                # x = (a^2 + b^2) / 2, y = (a^2 - b^2) / 2
                if (a2 + b2) % 2 != 0:
                    continue

                x = (a2 + b2) // 2
                y = (a2 - b2) // 2

                # z from e^2 = y+z => z = e^2 - y
                z = e * e - y

                if x > y > z > 0:
                    s = x + y + z
                    if s < best:
                        best = s
                        best_xyz = (x, y, z)

    print(best)

    if best_xyz:
        x, y, z = best_xyz
        print(f"x={x}, y={y}, z={z}")
        vals = {'x+y': x+y, 'x-y': x-y, 'x+z': x+z, 'x-z': x-z, 'y+z': y+z, 'y-z': y-z}
        for name, val in vals.items():
            s = isqrt(val)
            print(f"  {name} = {val} = {s}^2 (check: {s*s == val})")

if __name__ == '__main__':
    solve()