Problem 75: Singular Integer Right Triangles

Mathematical Analysis

Theorem 1 (Euclid’s Parametrization of Primitive Triples)

Every primitive Pythagorean triple $(a, b, c)$ with $a^2 + b^2 = c^2$, $a, b, c > 0$, and $\gcd(a, b, c) = 1$ can be written (up to swapping $a$ and $b$) as:

where $m > n > 0$, $\gcd(m, n) = 1$, and $m \not\equiv n \pmod{2}$. Conversely, every such pair $(m, n)$ generates a primitive triple.

Proof.

$(\Leftarrow)$ Given valid $(m, n)$, direct computation verifies:

For primitivity: suppose a prime $p$ divides $\gcd(a, b)$. Then $p \mid (m^2 - n^2)$ and $p \mid 2mn$. Since $m$ and $n$ have opposite parity, $a = m^2 - n^2$ is odd, so $p \neq 2$. Then from $p \mid 2mn$ and $p$ odd, $p \mid m$ or $p \mid n$. If $p \mid m$, then from $p \mid m^2 - n^2$ we get $p \mid n^2$, hence $p \mid n$, contradicting $\gcd(m, n) = 1$. Similarly for $p \mid n$. Thus $\gcd(a, b) = 1$, and since $\gcd(a, b) = 1$ implies $\gcd(a, b, c) = 1$ (as $c^2 = a^2 + b^2$), the triple is primitive.

$(\Rightarrow)$ Let $(a, b, c)$ be a primitive triple with $b$ even (exactly one of $a, b$ must be even; if both were odd, then $c^2 = a^2 + b^2 \equiv 2 \pmod{4}$, which is impossible since squares are $\equiv 0$ or $1 \pmod{4}$). Factor:

Since $a$ is odd and $c$ is odd (as $c^2 = a^2 + b^2$ with $a$ odd and $b$ even), both $c - a$ and $c + a$ are even. Write $c - a = 2s$, $c + a = 2t$, so $b^2 = 4st$ and $(b/2)^2 = st$.

Claim: $\gcd(s, t) = 1$. Indeed, if $d \mid s$ and $d \mid t$, then $d \mid (t - s) = a$ and $d \mid (t + s) = c$, so $d \mid \gcd(a, c)$. Since $\gcd(a, c) = 1$ (because $\gcd(a, b, c) = 1$ and any common factor of $a, c$ would divide $b^2$ hence $b$), we get $d = 1$.

Since $st = (b/2)^2$ is a perfect square and $\gcd(s, t) = 1$, both $s$ and $t$ must be perfect squares: $s = n^2$, $t = m^2$. Then $a = t - s = m^2 - n^2$, $c = t + s = m^2 + n^2$, $b = 2mn$, with $m > n > 0$ (since $c > a > 0$), $\gcd(m, n) = 1$ (from $\gcd(s, t) = 1$), and $m \not\equiv n \pmod{2}$ (since $a = m^2 - n^2$ is odd). $\square$

Theorem 2 (Perimeter Formula)

The perimeter of the primitive triple generated by $(m, n)$ is $L_0 = 2m(m + n)$.

Proof.

Theorem 3 (Scaling Principle)

Every Pythagorean triple $(a, b, c)$ is uniquely expressible as $k \cdot (a_0, b_0, c_0)$ for a positive integer $k$ and a primitive triple $(a_0, b_0, c_0)$. Consequently, perimeter $L$ admits a Pythagorean triple if and only if $L = kL_0$ for some primitive perimeter $L_0$ and some $k \geq 1$.

Proof. Setting $g = \gcd(a, b, c)$, the triple $(a/g, b/g, c/g)$ is primitive and $(a, b, c) = g \cdot (a/g, b/g, c/g)$. Uniqueness: if $k(a_0, b_0, c_0) = k'(a_0', b_0', c_0')$ with both primitive, then $k = k'$ (since $\gcd(a_0, b_0, c_0) = \gcd(a_0', b_0', c_0') = 1$) and the triples coincide. $\square$

Lemma (Bound on $m$)

For primitive perimeters $L_0 = 2m(m+n) \leq L_{\max}$ with $n \geq 1$, we have $m < \sqrt{L_{\max}/2}$.

Proof. From $2m(m + n) \leq L_{\max}$ and $n \geq 1$: $2m(m+1) \leq L_{\max}$, so $m^2 < m(m+1) \leq L_{\max}/2$. For $L_{\max} = 1{,}500{,}000$, this gives $m < \sqrt{750000} \approx 866.03$, i.e., $m \leq 866$. $\square$

Definition (Singular Perimeter)

A perimeter $L$ is called singular if there is exactly one Pythagorean triple (counting different orderings of legs as the same triple) with perimeter $L$.

Theorem 4 (Counting Method)

For each perimeter $L \leq L_{\max}$, define $T(L)$ as the number of distinct Pythagorean triples with perimeter $L$. Then $T(L) = \sum_{L_0 \mid L} \mathbf{1}[L_0 \text{ is a primitive perimeter}]$. The answer is $|\{L \leq L_{\max} : T(L) = 1\}|$.

Proof. By Theorem 3, each Pythagorean triple with perimeter $L$ corresponds to a unique factorization $L = kL_0$ with $L_0$ primitive and $k \geq 1$. Distinct primitive perimeters $L_0$ dividing $L$ give distinct triples. $\square$

Editorial

Euclid’s parametrization gives a clean generation scheme for all primitive triples. Every valid pair $(m,n)$ with opposite parity and $\gcd(m,n)=1$ produces exactly one primitive perimeter

That already handles candidate generation. The filtering comes from the Euclid conditions: pairs with the same parity or a common factor do not produce primitive triples, so we discard them immediately. Once a primitive perimeter is known, every multiple of it corresponds to a non-primitive triple, so we mark all multiples in a counter array. After the sweep, a perimeter is singular precisely when its counter is equal to one.

Pseudocode

Create a counter array for all perimeters up to the limit.
Compute the largest necessary value of m.

For each m starting from 2:
    For each n with 1 <= n < m:
        If m and n have the same parity, skip this pair
        If gcd(m, n) is greater than 1, skip this pair

        Compute the primitive perimeter L0 = 2m(m + n)
        If L0 is above the limit, stop increasing n for this m

        For every multiple of L0 within the limit:
            increase the corresponding perimeter counter

Count how many perimeters were hit exactly once.
Return that count.

Complexity Analysis

Outer loop: The iterations over $(m, n)$ pairs total $\sum_{m=2}^{m_{\max}} (m-1) = O(m_{\max}^2) = O(L_{\max})$ before filtering.

Inner loop: For each primitive perimeter $L_0$, we mark $\lfloor L_{\max}/L_0 \rfloor$ multiples. The total work is:

By analogy with the sum of reciprocals over a sieved set, this is $O(L_{\max} \log \log L_{\max})$.

• Time: $O(L_{\max} \log \log L_{\max})$.
• Space: $O(L_{\max})$ for the counter array.

Answer

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

int main() {
    // Count singular perimeters L <= 1,500,000.
    // Generate primitive Pythagorean triples via Euclid: L0 = 2m(m+n).
    // Mark all multiples kL0. Count perimeters hit exactly once.

    const int LMAX = 1500000;
    vector<int> cnt(LMAX + 1, 0);

    int mlimit = (int)sqrt((double)LMAX / 2.0) + 1;

    for (int m = 2; m <= mlimit; m++) {
        for (int n = 1; n < m; n++) {
            if ((m - n) % 2 == 0) continue;
            if (__gcd(m, n) != 1) continue;

            int L0 = 2 * m * (m + n);
            if (L0 > LMAX) break;

            for (int L = L0; L <= LMAX; L += L0) {
                cnt[L]++;
            }
        }
    }

    int answer = 0;
    for (int L = 1; L <= LMAX; L++) {
        if (cnt[L] == 1) answer++;
    }

    cout << answer << endl;
    return 0;
}

"""
Project Euler Problem 75: Singular Integer Right Triangles

Count values of L <= 1,500,000 for which exactly one integer-sided
right triangle can be formed with perimeter L.

By Theorems 1-3, generate all primitive Pythagorean triple perimeters
via Euclid's parametrization L0 = 2m(m+n), then count multiples.
A perimeter is "singular" iff it is hit exactly once.
"""

from math import gcd, isqrt


def solve():
    LMAX = 1_500_000
    cnt = [0] * (LMAX + 1)

    mlimit = isqrt(LMAX // 2) + 1

    for m in range(2, mlimit + 1):
        for n in range(1, m):
            if (m - n) % 2 == 0:
                continue
            if gcd(m, n) != 1:
                continue
            L0 = 2 * m * (m + n)
            if L0 > LMAX:
                break
            for L in range(L0, LMAX + 1, L0):
                cnt[L] += 1

    return sum(1 for L in range(1, LMAX + 1) if cnt[L] == 1)


if __name__ == "__main__":
    answer = solve()
assert answer == 161667
print(answer)