Detailed mathematical approach

Problem Summary

A primitive right-angled triangle has integer sides \((a,b,c)\), satisfies \(a^2+b^2=c^2\), and has \(\gcd(a,b,c)=1\). In this problem such a triangle is called perfect when the hypotenuse \(c\) is itself a perfect square, and super-perfect when its area is divisible by \(84\).

The task is to count perfect primitive right triangles under the problem's bound \(c \le 10^{16}\) whose area is not divisible by \(84\). The striking point is that the final answer does not come from a large search at all: the mathematics shows that every perfect primitive right triangle is automatically super-perfect, so the required count is zero.

Mathematical Approach

The whole solution is a short chain of structural facts about primitive Pythagorean triples. The key move is that a square hypotenuse creates a second primitive triple hidden inside the first one.

Euclid's parameterization for a primitive right triangle

Every primitive right triangle can be written in Euclid's 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 opposite parity. Those conditions are exactly what make the triple primitive.

For Problem 218 we additionally require \(c\) to be a square, so there is an integer \(r\) such that

$m^2+n^2=r^2.$

That means \((m,n,r)\) is itself a primitive Pythagorean triple: \(m\) and \(n\) are coprime and of opposite parity already, so no common factor can appear in the new triple either.

The square hypotenuse forces a second Pythagorean parameterization

Since \((m,n,r)\) is primitive, its two legs must again have Euclidean form. Reordering the two legs of this auxiliary triple if necessary, there exist coprime integers \(u>v>0\) of opposite parity such that

$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$

This is the main structural fact behind the theorem. A perfect triangle is not an arbitrary primitive triple with a square hypotenuse; it is a primitive triple whose Euclid parameters are themselves the two legs of another primitive triple.

Factorizing the area

The area of the original triangle is

$A=\frac{ab}{2}=mn(m^2-n^2).$

Because the auxiliary parameterization may swap the roles of \(m\) and \(n\), it is cleaner to write

$A=mn\,|m^2-n^2|.$

Now substitute \(\{m,n\}=\{u^2-v^2,\ 2uv\}\):

$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|.$

Expanding the last factor gives

$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$

For divisibility arguments the sign is irrelevant, so the whole problem is reduced to proving that the product above is always divisible by \(4\), by \(3\), and by \(7\).

Why divisibility by 4, 3, and 7 is unavoidable

Factor \(4\). Because \(u\) and \(v\) have opposite parity, exactly one of them is even, so \(uv\) is even. The factor \(2uv\) therefore contributes at least two powers of 2, which proves \(4 \mid A\).

Factor \(3\). If \(3\mid u\) or \(3\mid v\), then \(3\mid A\) immediately. Otherwise \(u\not\equiv 0\) and \(v\not\equiv 0\pmod 3\), so

$u^2\equiv v^2\equiv 1 \pmod 3,$

and therefore

$u^2-v^2\equiv 0 \pmod 3.$

In either case, \(3\mid uv(u^2-v^2)\), hence \(3\mid A\).

Factor \(7\). If \(7\mid u\) or \(7\mid v\), there is nothing to prove. Otherwise Fermat's little theorem gives

$u^6\equiv v^6\equiv 1 \pmod 7.$

Modulo \(7\), the quartic factor simplifies because \(-6\equiv 1\):

$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$

Now use the identity

$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$

The right-hand side is \(0 \pmod 7\), so

$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$

Thus \(7\mid A\) as well.

Combining the three parts yields

$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$

hence

$84=4\cdot 3\cdot 7 \mid A.$

So every perfect primitive right triangle is automatically super-perfect. There are no counterexamples to count.

Worked example: the triangle \(7\text{-}24\text{-}25\)

The smallest familiar example already illustrates the theorem. Taking Euclid parameters \(m=4\) and \(n=3\) gives

$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$

So \((7,24,25)\) is perfect. The hidden auxiliary triple is \((3,4,5)\), which corresponds to \(u=2\), \(v=1\). The factorized area formula becomes

$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$

The first perfect primitive triangle is already super-perfect, and the proof above shows that this is not a coincidence but a universal fact.

How the Code Works

The implementation uses the theorem in its strongest possible form. Once the mathematics proves that every perfect primitive right triangle is super-perfect, the count of non-super-perfect triangles below any bound is identically zero. The final solver therefore returns \(0\) directly instead of trying to enumerate triangles up to \(10^{16}\).

The C++, Python, and Java implementations all embody that same conclusion. The Python version is the distilled theorem-only form. The C++ and Java versions additionally keep a bounded brute-force checkpoint: they loop over Euclid parameters, enforce coprimality and opposite parity, test whether \(m^2+n^2\) is a square, compute the corresponding area, and verify on a small range that no counterexample with area not divisible by \(84\) appears.

That checkpoint is a sanity test, not the real method. The real method is the proof above, which collapses the search space completely.

Complexity Analysis

For the actual solution, the time complexity is \(O(1)\) and the memory usage is \(O(1)\): the program returns the theorem's conclusion immediately.

The auxiliary checkpoint enumeration used for validation on small ranges is much slower, roughly quadratic in the chosen Euclid-parameter cutoff, but it is intentionally kept far below the true problem bound. It does not change the complexity of the final solver, whose whole point is to avoid any large-scale search.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=218
2. Pythagorean triple and Euclid's formula: Wikipedia - Pythagorean triple
3. Primitive Pythagorean triples: Wikipedia - Primitive Pythagorean triples
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Fermat's little theorem: Wikipedia - Fermat's little theorem