Detailed mathematical approach

Problem Summary

For an integer wire length \(L\), we ask whether it can be bent into a right triangle with integer side lengths \((a,b,c)\). The goal is to count how many perimeters \(L \le 1{,}500{,}000\) admit exactly one such triangle.

The difficulty is that the same perimeter may come from several different Pythagorean triples. So the real task is not merely to generate right triangles, but to count how many distinct integer right triangles correspond to each perimeter.

Mathematical Approach

The solution is built around Euclid's parametrization of primitive Pythagorean triples. Once primitive triples are generated, every non-primitive triple appears as an integer multiple of one of them, so the whole problem becomes a perimeter-counting sieve.

Primitive right triangles from Euclid's formula

Every primitive integer right triangle can be written in the form

$a = m^2 - n^2,\qquad b = 2mn,\qquad c = m^2 + n^2,$

with integers \(m > n > 0\), \(\gcd(m,n)=1\), and \(m-n\) odd. The coprimality condition removes a common scale factor, and the parity condition prevents all three sides from being even. Conversely, each such pair \((m,n)\) produces one primitive Pythagorean triple.

The perimeter formula and its immediate consequences

Adding the three sides gives the primitive perimeter

$p_0 = a+b+c = (m^2-n^2)+2mn+(m^2+n^2)=2m(m+n).$

This already explains two important facts used by the implementations. First, every right-triangle perimeter counted by the program is even. Second, for a fixed \(m\), the smallest possible primitive perimeter occurs at \(n=1\), namely \(2m(m+1)\). Therefore, once \(2m(m+1) > N\), no larger \(m\) can contribute any perimeter up to the limit.

Why counting multiples is enough

Every non-primitive Pythagorean triple is uniquely of the form \(k(a,b,c)\), where \((a,b,c)\) is primitive and \(k \ge 1\). Its perimeter is then \(kp_0\). So from each primitive perimeter \(p_0\), all valid perimeters generated by that family are exactly

$p_0,\ 2p_0,\ 3p_0,\ \dots \le N.$

This gives the key invariant of the algorithm: if we increment a counter for every multiple of every primitive perimeter, then after all primitive generators have been processed, the counter at index \(L\) is exactly the number of distinct integer right triangles with perimeter \(L\).

Worked example: why \(120\) is not singular

The problem statement mentions \(L=120\), and Euclid's formula explains the three representations cleanly. Three primitive generators already suffice:

\(m=2,n=1\) gives \((3,4,5)\) with \(p_0=12\),

\(m=3,n=2\) gives \((5,12,13)\) with \(p_0=30\),

\(m=4,n=1\) gives \((15,8,17)\) with \(p_0=40\).

Since \(120 = 10 \cdot 12 = 4 \cdot 30 = 3 \cdot 40\), the perimeter \(120\) is produced by

$ (30,40,50),\qquad (20,48,52),\qquad (24,45,51). $

So \(120\) is not singular. By contrast, \(L=12\) comes only from \((3,4,5)\), so it is singular. The final answer is therefore the number of perimeters whose counter value is exactly \(1\).

How the Code Works

Enumerating primitive generators

The C++, Python, and Java implementations iterate over \(m \ge 2\) while \(2m(m+1) \le N\). For each \(m\), they test all \(1 \le n < m\), reject pairs with even \(m-n\), and reject pairs with \(\gcd(m,n)\ne 1\). The surviving pairs are precisely the primitive generators required by Euclid's formula.

Marking all reachable perimeters

For each accepted pair, the implementation computes the primitive perimeter \(p_0 = 2m(m+n)\). It then walks through the arithmetic progression \(p_0, 2p_0, 3p_0, \dots\) up to the limit and increments a perimeter-frequency array at each step. This is the entire counting mechanism: every valid triangle contributes exactly one increment to its own perimeter.

Extracting the final total

After all primitive generators have been processed, the implementation scans the array and counts how many entries are equal to \(1\). That is exactly the number of singular wire lengths. The C++ and Python implementations also verify the smaller checkpoint \(N=150\), for which the correct count is \(16\), before evaluating the main limit; the Java implementation applies the same algorithm directly to \(1{,}500{,}000\).

Complexity Analysis

The parameter search itself is bounded by \(m \le \sqrt{N/2}\), so enumerating candidate pairs \((m,n)\) costs \(O(N)\) in the worst case. The larger part of the work is updating all multiples of each primitive perimeter.

If the primitive perimeters are \(p_0\), then the number of counter updates is

$\sum_{p_0}\left\lfloor\frac{N}{p_0}\right\rfloor.$

This behaves like a harmonic sum over the generated primitive perimeters and is comfortably near \(O(N \log N)\) for this problem size. Memory usage is \(O(N)\) because the implementation stores one counter per perimeter up to \(1{,}500{,}000\).

Footnotes and References

1. Problem page: Project Euler 75
2. Pythagorean triples: Wikipedia - Pythagorean triple
3. Euclid's formula: Wikipedia - Euclid's formula
4. Background on primitive triples: Wolfram MathWorld - Pythagorean Triple
5. Greatest common divisors: Wikipedia - Euclidean algorithm