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 right-angled triangle with integer sides has legs $a$, $b$ and hypotenuse $c$ with $a^2+b^2=c^2$. The statement calls it primitive when $\gcd(a,b)=1$ and $\gcd(b,c)=1$, perfect when it is primitive and $c$ is a perfect square, and super-perfect when it is perfect and its area $ab/2$ is a multiple of the perfect numbers $6$ and $28$. ^[1] ^[2] Its example $(7,24,25)$ is primitive, has $c=25=5^2$, and its area $84$ equals $6\cdot14$ and $28\cdot3$. We must find how many perfect triangles with $c\le10^{16}$ are not super-perfect.

The whole solution in one sentence: Euclid's formula turns the square hypotenuse $c=m^2+n^2$ into a second primitive right-angled triangle with legs $m$ and $n$, and this second triangle decides, through remainders modulo $4$, $3$ and $7$, whether the area $mn(m^2-n^2)$ is a multiple of $84=\mathrm{lcm}(6,28)$.

Mathematical Approach

We apply Euclid's formula twice to describe every perfect triangle and then examine its area with remainders modulo $4$, $3$ and $7$, the prime-power factors of $84$; no triangle has to be enumerated.

1. Small cases

Sorted by the hypotenuse, with the odd leg first, the first six perfect triangles and their areas are

$(7,24,25)$ with $c=5^2$ and area $84=84\cdot1$;
$(119,120,169)$ with $c=13^2$ and area $7140=84\cdot85$;
$(161,240,289)$ with $c=17^2$ and area $19320=84\cdot230$;
$(527,336,625)$ with $c=25^2$ and area $88536=84\cdot1054$;
$(41,840,841)$ with $c=29^2$ and area $17220=84\cdot205$;
$(1081,840,1369)$ with $c=37^2$ and area $454020=84\cdot5405$.

Every area is a multiple of $84$. For primitive triangles in general this is false: $(3,4,5)$, $(5,12,13)$, $(8,15,17)$ and $(20,21,29)$ have the areas $6$, $30$, $60$ and $210$, all multiples of $6$, but $60$ is not a multiple of $7$ and $210=2\cdot3\cdot5\cdot7$ is not a multiple of $4$. The triangle $(15,20,25)$ has the square hypotenuse $25$ but is not primitive, and its area $150$ is a multiple of neither $4$ nor $7$. Both conditions in the definition of a perfect triangle will therefore be needed.

2. Exactly one leg is even

Every square leaves the remainder $0$ or $1$ on division by $4$, because $(2k)^2=4k^2$ and $(2k+1)^2=4(k^2+k)+1$. If both legs were odd, $c^2=a^2+b^2$ would leave the remainder $2$, which no square does; if both were even, $\gcd(a,b)$ would be at least $2$. So a primitive triangle has exactly one even leg, and its hypotenuse is odd. ^[3] A triangle is determined by its sides, not by their order, so from now on $b$ denotes the even leg. The two gcd conditions of the statement say the same thing: a prime dividing two of the numbers $a$, $b$, $c$ divides the square of the third, for example $a^2=c^2-b^2$, and therefore the third number itself. Hence $\gcd(a,b)=1$, $\gcd(b,c)=1$ and $\gcd(a,c)=1$ are equivalent.

3. Euclid's formula

The primitive triangles with even leg $b$ are exactly the triples

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

with integers $m\gt n\gt0$ that are coprime, that is, have no common divisor larger than $1$, and of opposite parity, one even and one odd; different pairs $(m,n)$ give different triangles. ^[3] To prove it, start from a primitive triangle. Since $a$ and $c$ are odd, $c-a$ and $c+a$ are even, and

$$\Bigl(\frac b2\Bigr)^2=\frac{c-a}2\cdot\frac{c+a}2.$$

A common divisor of the two factors on the right divides their sum $c$ and their difference $a$, so they are coprime. Every exponent in the prime factorisation of a square is even, and each prime of the product lies entirely in one of two coprime factors, so each factor is a square: ^[4] $(c+a)/2=m^2$ and $(c-a)/2=n^2$ with $m\gt n\gt0$. A common divisor of $m$ and $n$ would divide $a$ and $c$, so $\gcd(m,n)=1$, and $m^2+n^2=c$ is odd, so exactly one of $m$, $n$ is even. Adding and subtracting the two equations gives $c=m^2+n^2$ and $a=m^2-n^2$, and $b^2=4m^2n^2$ gives $b=2mn$.

Conversely, for such $m$ and $n$ the identity $(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$ holds and $c$ is odd; a common divisor of $a$ and $c$ is odd and divides $c+a=2m^2$ and $c-a=2n^2$, hence divides $\gcd(m^2,n^2)=1$. The pair $(m,n)$ is unique because $m^2=(c+a)/2$ and $n^2=(c-a)/2$. For example, $(m,n)=(2,1)$ gives $(3,4,5)$ and $(4,3)$ gives $(7,24,25)$. The area of the triangle with parameters $m$, $n$ is

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

4. A square hypotenuse gives a second triangle

A primitive triangle is perfect when $m^2+n^2=c=r^2$ for an integer $r$. Then $m$, $n$, $r$ are the sides of a right-angled triangle, primitive because $\gcd(m,n)=1$; we call it the second triangle. For $(7,24,25)$ its legs are $4$, $3$ and its hypotenuse is $5$; for $(119,120,169)$ they are $12$, $5$ and $13$.

Conversely, the legs of any primitive triangle with hypotenuse $r$ are coprime and of opposite parity by Section 2, hence different, so the larger leg $m$ and the smaller leg $n$ are admissible parameters for Section 3 and produce a perfect triangle with $c=r^2$. Perfect triangles therefore correspond one to one to primitive triangles, with $c$ the square of $r$, and the bound $c\le10^{16}$ becomes $r\le10^8$. Euclid's formula applied to the second triangle gives coprime integers $u\gt v\gt0$ of opposite parity with

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

where $2uv$ is the even one of $m$, $n$. For the second triangle $(12,5,13)$ we get $(u,v)=(3,2)$.

5. What has to be proved

Since $6=2\cdot3$ and $28=2^2\cdot7$, a number is a multiple of both exactly when it is a multiple of their least common multiple $84=2^2\cdot3\cdot7$, which takes every prime with its larger exponent, ^[4] and, because $4$, $3$ and $7$ are pairwise coprime, exactly when it is a multiple of each of $4$, $3$ and $7$. So a perfect triangle is super-perfect if and only if $4$, $3$ and $7$ divide $A=mn(m^2-n^2)$.

We use congruences: $x\equiv y\pmod k$ means that $k$ divides $x-y$, and congruences modulo $k$ can be added and multiplied like equations. ^[5] So $x\equiv y$ implies $x^2\equiv y^2$, and the remainders of squares modulo $k$ are found by squaring $0,1,\dots,k-1$.

6. The factor 3

Modulo $3$ the squares of $0$, $1$, $2$ are $0$, $1$, $1$. If $3$ divides $m$ or $n$, it divides $A$. Otherwise $m^2\equiv n^2\equiv1\pmod 3$, so $3$ divides $m^2-n^2$. Either way $3$ divides $A$. This holds for all integers $m$, $n$; with the factor $2$ of $mn$ it gives the classical fact that the area of every primitive right-angled triangle is a multiple of $6$. ^[3]

7. The factor 4

By Section 4 the even one of $m$, $n$ is the leg $2uv$ of the second triangle, and one of $u$, $v$ is even, so $2uv$ is a multiple of $4$; this is the known fact that one leg of every primitive triangle is divisible by $4$, ^[3] applied to the second triangle. Hence $4$ divides $mn$ and therefore $A$. In the six triangles of Section 1 the even parameter is $4$, $12$, $8$, $24$, $20$ and $12$. This is the first place where the square hypotenuse matters: the primitive triangle $(3,4,5)$ has $(m,n)=(2,1)$, so $mn=2$, and its area $6$ is not a multiple of $4$.

8. The factor 7

Modulo $7$ the squares of $0,1,\dots,6$ are $0,1,4,2,2,4,1$, so a square not divisible by $7$ leaves the remainder $1$, $2$ or $4$. ^[6] If $7$ divides $m$ or $n$, it divides $A$. Otherwise $m^2$ and $n^2$ leave remainders in $\{1,2,4\}$, and the six possible sums are

$$1+1\equiv2,\quad 2+2\equiv4,\quad 4+4\equiv1\pmod 7,$$

$$1+2\equiv3,\quad 1+4\equiv5,\quad 2+4\equiv6\pmod 7.$$

The sum $m^2+n^2=r^2$ must leave the remainder of a square, so the three cases of the second line, which end in the non-squares $3$, $5$, $6$, are impossible. In each case of the first line the two remainders are equal, so $m^2\equiv n^2\pmod 7$ and $7$ divides $m^2-n^2$. Either way $7$ divides $A$; Section 11 shows the case in which $7$ divides neither parameter. Without a square hypotenuse the argument breaks down: $(8,15,17)$ has $(m,n)=(4,1)$, the sum $16+1=17$ leaves the non-square remainder $3$, and its area $60$ is not a multiple of $7$.

9. Combining the three factors

Section 5 reduced the super-perfect condition to the divisibility of $A$ by $4$, $3$ and $7$, and Sections 6, 7 and 8 examined each of these for an arbitrary perfect triangle; together they settle the classification asked for, and the bound $10^{16}$ is never used. Both hypotheses entered the argument: the square hypotenuse produced the second triangle of Sections 7 and 8, and primitivity made Euclid's formula available. Without primitivity the construction fails: $(15,20,25)$ is $5$ times $(3,4,5)$, whose parameters are $(2,1)$, and although its hypotenuse $25=5\cdot(2^2+1^2)$ is a square, $2^2+1^2=5$ is not, so there is no second triangle.

10. The area as a polynomial in $u$ and $v$

Substituting the second Euclid formula expresses the area through $u$ and $v$ alone. With $m=u^2-v^2$ and $n=2uv$ the difference $m^2-n^2$ equals $u^4-6u^2v^2+v^4$, and exchanging $m$ and $n$ only changes its sign, so in both cases

$$A=2uv\,(u^2-v^2)\,\bigl|u^4-6u^2v^2+v^4\bigr|,$$

and the odd leg is $a=|u^4-6u^2v^2+v^4|$; for $(u,v)=(2,1)$ this gives $2\cdot2\cdot1\cdot3\cdot|{-7}|=84$. The formula gives a second proof of the factor $7$ by Fermat's little theorem, $x^{p-1}\equiv1\pmod p$ for a prime $p$ not dividing $x$. ^[7] If $7$ divides $u$ or $v$, it divides $2uv$. Otherwise $u^6\equiv v^6\equiv1\pmod 7$, and because $-6\equiv1\pmod 7$,

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

$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6\equiv0\pmod 7,$$

so $7$ divides $(u^2-v^2)\,a$, a factor of $A$.

11. Worked example: the perfect triangle with $c=169$

Start from $(u,v)=(3,2)$, which are coprime and of opposite parity. The second triangle has legs $u^2-v^2=5$ and $2uv=12$ and hypotenuse $u^2+v^2=13$, so $m=12$ and $n=5$, again coprime and of opposite parity. Euclid's formula gives

$$\begin{aligned}a&=144-25=119,\\ b&=2\cdot12\cdot5=120,\\ c&=144+25=169=13^2,\end{aligned}$$

and indeed $119^2+120^2=28561=169^2$ with $\gcd(119,120)=1$. The area is $A=12\cdot5\cdot119=7140$. The parameter $m=12=2uv$ supplies the factors $4$ and $3$; neither $12$ nor $5$ is a multiple of $7$, but $12^2\equiv5^2\equiv4\pmod 7$, so $7$ divides $a=119$. Hence $84$ divides $7140$, and indeed $7140=84\cdot85$. The polynomial of Section 10 agrees:

$$2\cdot3\cdot2\cdot5\cdot\bigl|81-216+16\bigr|=60\cdot119=7140.$$

How the Code Works

The C++ program ^[8] has a parser, a brute-force check and a solver. parse_arguments accepts --skip-checkpoints and --limit= followed by decimal digits, which parse_i64_after_prefix reads into the field limit of Options (default $10^{16}$). An unknown argument, an empty or non-digit number, or a final limit below $1$ makes main return the exit code $1$. The digit loop has no overflow check, so a value beyond the signed 64-bit range causes undefined behaviour instead of a reliable rejection.

Unless --skip-checkpoints is given, run_checkpoints calls brute_non_superperfect with the bound $10^6$. It enumerates the parameters of Section 3: $m$ runs from $2$ while $m^2$ stays within the bound and $n$ from $1$ to $m-1$; pairs with an even difference $m-n$ or with std::gcd(m, n) different from $1$ are skipped, and the inner loop stops once $c=m^2+n^2$ exceeds the bound, since $c$ grows with $n$. A square is recognised by truncating the long double square root of $c$ to an integer root and comparing root * root with $c$. For each perfect triangle the function computes the area $ab/2$ and counts the areas with a nonzero remainder modulo $84$, the criterion of Section 5. run_checkpoints accepts only its built-in expected count; otherwise it prints an error and main returns the exit code $2$.

solve ignores its argument and returns a fixed literal justified by the mathematics above, which main prints, so --limit never changes the output. The check computes in std::int64_t, and since every leg is below $c\le10^6$, the products $ab$ stay below $10^{12}$. Its square test is exact, because $c$ converts to long double without rounding and IEEE arithmetic returns the exact square root of a perfect square; ^[9] an exhaustive comparison with an integer square root for all $c\le10^8$ agreed.

The Python file only prints a fixed literal, with the reasoning in comments, and runs no check. The Java program uses long for its bound and the triangle arithmetic and repeats the brute-force loop for the limit $10^{16}$ with its own Euclidean gcd and Math.sqrt, but the test m > 1000 at the end of the outer loop body stops it after $m=1001$. It visits all $500500$ pairs with $2\le m\le1001$ and $n\lt m$ and meets $179$ perfect triangles, up to $c=1325^2$. It counts the failures in the int variable count, but never reads it and prints a fixed literal unconditionally, so in Java the loop cannot report a failure.

Complexity and Verification

The work does not depend on the requested limit: the bound of the C++ check and the cap of the Java loop are fixed, and Python performs no search. For a check bound $L$ the pairs with $n\lt m$ and $m^2+n^2\le L$ fill an eighth of a disc of radius $\sqrt L$, about $\pi L/8$ pairs, and each pair with an odd difference costs a gcd of $O(\log L)$ steps, so the check takes $O(L\log L)$ time and constant memory. For $L=10^6$ the inner loop runs $392402$ times, computes $196451$ gcds, tests $159139$ values of $c$, one per primitive triangle with $c\le10^6$, and finds $158$ perfect triangles; the Java loop makes $500500$ iterations. In our tests each loop took a few milliseconds.

At the real bound the same loop would need about $3.9\cdot10^{15}$ iterations, and its products $ab$ would overflow $64$ bits. Enumerating second triangles is far cheaper: by Section 4 the perfect triangles with $c\le10^{16}$ correspond to the primitive triangles with hypotenuse at most $10^8$, and by Lehmer's theorem the number of primitive triangles with hypotenuse below $N$ is asymptotically $N/(2\pi)$. ^[10] For $N=10^8$, an even number and hence never a primitive hypotenuse, the exact count is $15915492$. ^[11]

These checks were run for this article; only the C++ check itself is part of the published solutions.

The C++ check passes, and the three programs print the same value; so does the C++ program with --skip-checkpoints and with --limit=1000.
A separate C program enumerated all $19632440$ pairs $u\gt v\gt0$ of opposite parity with $u^2+v^2\le10^8$ and built from the $15915492$ coprime ones, as in Section 4, the perfect triangles with $c\le10^{16}$. For each it confirmed $c=r^2$ and $\gcd(a,b)=1$ and tested the area for divisibility by $84$ in exact 128-bit arithmetic, in agreement with Sections 6 to 8.
A direct search over $(m,n)$ with an exact integer square root found the same $158$ perfect triangles for $c\le10^6$ and $15919$ for $c\le10^{10}$, with areas in agreement with Sections 6 to 8.
A computer algebra system confirmed the identities of Section 10.

Footnotes and References

The references below supply the background facts used above. The second-triangle reduction and the divisibility proofs are derived here, and the loop and triangle counts were computed for this article.

Project Euler 218 — Perfect Right-angled Triangles. The official statement defines perfect and super-perfect right-angled triangles, illustrates both with the triangle (7, 24, 25) of area 84, and asks how many perfect triangles with c ≤ 10¹⁶ are not super-perfect.
Wikipedia — Perfect number. A perfect number is a positive integer equal to the sum of its positive divisors smaller than itself; the first two are 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14.
Wikipedia — Pythagorean triple. Euclid's formula gives a primitive triple exactly when m and n are coprime and exactly one of them is even, and every primitive triple comes from a unique such pair; in a primitive triple exactly one leg is even, exactly one leg is divisible by 4 and the area is divisible by 6.
Wikipedia — Fundamental theorem of arithmetic. Factorisation into primes is unique up to order, and the gcd and the lcm take every prime with the smaller and the larger exponent.
Wikipedia — Modular arithmetic. Congruence modulo m means that the difference is a multiple of m, and it is compatible with addition, subtraction and multiplication.
Wikipedia — Quadratic residue. Its table lists 0, 1, 2 and 4 as the quadratic residues modulo 7.
Wikipedia — Fermat's little theorem. For a prime p and an integer a not divisible by p, a^(p−1) ≡ 1 (mod p).
C++ — Euler218.cpp. The linked immutable revision is the C++ program described above.
cppreference — std::sqrt. IEEE arithmetic rounds the square root correctly, so a representable exact root is returned exactly.
MathWorld — Pythagorean Triple. The page states Lehmer's 1900 result that the number of primitive triples with hypotenuse less than N, divided by N, tends to 1/(2π).
OEIS A101931 — Number of primitive Pythagorean triples with hypotenuse < 10^n. The sequence begins 1, 16, 158, 1593, 15919, 159139, 1591579, 15915492; its eighth term is the count quoted above.

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;
    }
}