Problem 218: Perfect Right-angled Triangles

Project Euler Problem 218 Solution

EulerSolve provides an optimized solution for Project Euler Problem 218, Perfect Right-angled Triangles, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

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

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

Problem 218 source code

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <cmath>
#include <functional>

namespace {

using i64 = std::int64_t;

struct Options {
    i64 limit = 10000000000000000LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_i64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

i64 brute_non_superperfect(const i64 limit) {
    i64 count = 0;

    for (i64 m = 2; m * m <= limit; ++m) {
        for (i64 n = 1; n < m; ++n) {
            if (((m - n) & 1LL) == 0LL || std::gcd(m, n) != 1LL) {
                continue;
            }

            const i64 c = m * m + n * n;
            if (c > limit) {
                break;
            }

            const i64 root = static_cast<i64>(std::sqrt(static_cast<long double>(c)));
            if (root * root != c) {
                continue;
            }

            const i64 a = m * m - n * n;
            const i64 b = 2 * m * n;
            const i64 area = (a * b) / 2;
            if (area % 84LL != 0LL) {
                ++count;
            }
        }
    }

    return count;
}

i64 solve(const i64 /*limit*/) {
    // Every primitive right triangle with square hypotenuse is super-perfect,
    // so the required count is zero.
    return 0;
}

bool run_checkpoints() {
    if (brute_non_superperfect(1000000LL) != 0LL) {
        std::cerr << "Checkpoint failed for brute bound 1e6" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

# Problem 218: Perfect Right-angled Triangles
# Every primitive right triangle with square hypotenuse is super-perfect.
# The answer is 0.

def solve():
    # Mathematical proof: For any primitive Pythagorean triple (a,b,c) where c is a perfect square,
    # the area (a*b/2) is always divisible by 6 and by 28 (hence by 84).
    # Therefore there are no "non-super-perfect" triangles, and the count is 0.
    print(0)

solve()

Java

public class Euler218 {
    // Every primitive right triangle with a square hypotenuse is super-perfect,
    // so the answer is 0.
    public static void main(String[] args) {
        long limit = 10000000000000000L;
        // Brute confirm for small range
        int count = 0;
        for (long m = 2; m * m <= limit; m++) {
            for (long n = 1; n < m; n++) {
                if (((m - n) & 1) == 0 || gcd(m, n) != 1)
                    continue;
                long c = m * m + n * n;
                if (c > limit)
                    break;
                long r = (long) Math.sqrt((double) c);
                if (r * r != c)
                    continue;
                long a = m * m - n * n, b = 2 * m * n;
                long area = (a * b) / 2;
                if (area % 84 != 0)
                    count++;
            }
            if (m > 1000)
                break; // only check small range
        }
        System.out.println(0);
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}