Problem 139: Pythagorean Tiles

Project Euler Problem 139 Solution

EulerSolve provides an optimized solution for Project Euler Problem 139, Pythagorean Tiles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The problem asks for the number of Pythagorean triples $(a,b,c)$ with perimeter $a+b+c<10^8$ that can form the classic “square hole” arrangement: four congruent right triangles are placed inside a $c\times c$ square, leaving a central square of side $|a-b|$. The arrangement becomes a genuine tiling only when that inner square side divides the outer side, so the arithmetic condition is $$|a-b|\mid c.$$ Rather than scan every non-primitive triple separately, the efficient strategy is to enumerate primitive triples first and then count all allowed multiples. Mathematical Approach The implementations are based on Euclid's parametrization of primitive Pythagorean triples, but the divisibility test hides a stronger structure. Once that structure is exposed, the code becomes easy to justify. The square hole and the divisibility invariant For a right triangle with legs $a,b$ and hypotenuse $c$, four copies fit inside a square of side $c$. The central gap is itself a square, and a short geometric inspection shows that its side length is exactly $$d=|a-b|.$$ If the large square is to be tiled by smaller copies of that inner square pattern, the side length of the hole must divide the side length of the outer square. So the entire problem reduces to checking whether $$d\mid c.$$ This is the only arithmetic test used by the implementations....

Detailed mathematical approach

Problem Summary

Let $a$ and $b$ be the legs and $c$ the hypotenuse of a right triangle with integer sides, so that $a^2+b^2=c^2$. Four copies of the triangle can be placed together to form a square of side $c$ with a square hole in the middle. For $(3,4,5)$ the hole is $1$ by $1$, and twenty-five $1$ by $1$ squares tile the $5$ by $5$ square; for $(5,12,13)$ the hole is $7$ by $7$, and such squares cannot tile the $13$ by $13$ square. We must count the Pythagorean triangles with perimeter $a+b+c$ less than $10^8$ whose $c$ by $c$ square can be tiled with copies of the hole; a triangle counts once, whichever leg is called $a$. ^[1] The statement gives no count to check; Section 9 derives the count $9$ for perimeters below $100$, which the C++ program checks.

The whole solution in one sentence: the hole tiles the square exactly when the difference of the legs divides $c$, which, once the common factor of the three sides is removed, happens only for consecutive legs, as in $(3,4,5)$ and $(20,21,29)$; these few triangles come from a Pell equation, and each of them with perimeter $p$ contributes its $\lfloor(10^8-1)/p\rfloor$ multiples.

Mathematical Approach

We turn the picture into a divisibility condition, find all triangles that satisfy it through a Pell equation and count them.

1. The square with a hole

The two legs are never equal: $a=b$ would give $c^2=2a^2$, so $\sqrt2=c/a$ would be a fraction, but $\sqrt2$ is irrational. ^[4] Write $d=|a-b|\ge1$. In the picture each copy is turned a quarter turn from the previous one, and the four hypotenuses form the sides of the $c$ by $c$ square. At every corner the long leg of one triangle and the short leg of the next end together on one line. The long leg reaches $d$ further than the short leg, and these four stretches of length $d$, which meet at right angles, are the sides of the hole. So the hole is a square of side $d$, and the areas agree:

$$4\cdot\frac{ab}{2}+(a-b)^2=a^2+b^2=c^2.$$

This is a classical proof of the theorem of Pythagoras. ^[2] For $(3,4,5)$ it reads $4\cdot6+1=25$, and for $(5,12,13)$ it reads $4\cdot30+49=169$.

2. When copies of the hole tile the square

Claim. Copies of a $d$ by $d$ square can tile a $c$ by $c$ square exactly when $d$ divides $c$, written $d\mid c$.

Proof. If $c=kd$, a grid of $k$ rows of $k$ squares does it. Conversely, suppose that $N$ copies tile the square. Comparing areas gives $c^2=Nd^2$, so the fraction $c/d$ has the integer square $N$. Write $c/d=r/s$ in lowest terms. Then $r^2=Ns^2$, so every prime factor of $s$ divides $r^2$ and hence $r$, which is impossible in lowest terms. So $s=1$, and $c/d=r$ is an integer.

So a triangle allows the tiling exactly when $d\mid c$. For $(3,4,5)$, $d=1$ divides $5$; for $(5,12,13)$, $d=7$, and $13$ leaves the remainder $6$.

3. Primitive triangles and Euclid's formula

A Pythagorean triple is primitive when $a$, $b$ and $c$ have no common factor greater than $1$. Dividing the sides by their greatest common divisor $g$ gives a primitive triangle, so every Pythagorean triangle is $g$ times exactly one primitive triangle. ^[3] In a primitive triple $\gcd(a,b)=1$, because a prime dividing $a$ and $b$ would divide $c^2=a^2+b^2$ and hence $c$. So the legs are not both even, and not both odd either, since two odd squares add up to $2$ more than a multiple of $4$, which no square is. Exactly one leg is even.

Euclid's formula lists all primitive triples. ^[3] For every pair of integers $m\gt n\ge1$ with $\gcd(m,n)=1$ and $m-n$ odd,

$$\begin{aligned}a&=m^2-n^2,\\b&=2mn,\\c&=m^2+n^2\end{aligned}$$

is a primitive triple, and every primitive triangle arises from exactly one such pair, with $b$ as its even leg. The perimeter $p=a+b+c$ is

$$p=2m^2+2mn=2m(m+n).$$

The pairs $(2,1)$, $(3,2)$, $(4,1)$, $(4,3)$, $(5,2)$, $(6,1)$ and $(5,4)$ give the seven primitive triangles with perimeter below $100$: $(3,4,5)$ with $p=12$, $(5,12,13)$ with $p=30$, $(15,8,17)$ with $p=40$, $(7,24,25)$ with $p=56$, $(21,20,29)$ with $p=70$, $(35,12,37)$ with $p=84$ and $(9,40,41)$ with $p=90$. As $(5,2)$ shows, the odd leg $m^2-n^2$ may be the longer one.

4. Multiples behave like their primitive triangle

The multiple $(ka,kb,kc)$ of a triangle has the hole side $kd$ and the hypotenuse $kc$, and $kd\mid kc$ holds exactly when $d\mid c$. So a triangle allows the tiling exactly when its primitive triangle does. For example, $(6,8,10)$ has $d=2$ and $10=5\cdot2$, so twenty-five $2$ by $2$ squares tile its square, just as for $(3,4,5)$, while $(10,24,26)$ has $d=14$ and fails like $(5,12,13)$.

5. Only consecutive legs work

Claim. A primitive triangle allows the tiling exactly when its legs are consecutive integers, that is, $d=1$.

Proof. If $d=1$, then $d\mid c$. For the converse, expanding $(a-b)^2$ gives

$$c^2=a^2+b^2=(a-b)^2+2ab,$$

so $2ab=c^2-d^2$; for $(5,12,13)$ both sides equal $120$, and for $(20,21,29)$ both equal $840$. If $d\mid c$, then $d$ divides $c^2-d^2=2ab$. One leg is even and the other odd, so $d$ is odd. Let $q$ be a prime factor of $d$. Then $q$ is odd and divides $2ab$, so it divides $a$ or $b$; since it also divides $a-b$, it divides both legs, which contradicts $\gcd(a,b)=1$. So $d$ has no prime factor at all, and $d=1$.

The seven primitive triangles of Section 3 have $d=1$, $7$, $7$, $17$, $1$, $23$ and $31$, and $c$ leaves the remainders $0$, $6$, $3$, $8$, $0$, $14$ and $10$ after division by $d$. Only $(3,4,5)$ and $(20,21,29)$ work, as the claim says.

6. Consecutive legs and a Pell equation

In Euclid's parameters $a-b=m^2-2mn-n^2$, and completing the square gives $m^2-2mn-n^2=(m-n)^2-2n^2$. With $x=m-n$ and $y=n$, the condition $d=1$ becomes

$$x^2-2y^2=\pm1,$$

an instance of Pell's equation, here with both signs. ^[5] Conversely, every solution in positive integers gives an admissible pair of Section 3: $m=x+y\gt n=y\ge1$; $m-n=x$ is odd, because $x^2=2y^2\pm1$ is odd; and $\gcd(m,n)=\gcd(x,y)=1$, because a common divisor of $x$ and $y$ divides $x^2-2y^2=\pm1$. So the primitive triangles that allow the tiling correspond one to one to the positive solutions of $x^2-2y^2=\pm1$. The first ones are $(1,1)$, $(3,2)$, $(7,5)$ and $(17,12)$, with $1-2=-1$, $9-8=1$, $49-50=-1$ and $289-288=1$. Through $(m,n)=(x+y,y)$ they give the triangles $(3,4,5)$, $(21,20,29)$, $(119,120,169)$ and $(697,696,985)$.

7. Every solution comes from the smallest one

Inside every solution except $(1,1)$ hides a smaller one. From $(17,12)$ we get $(2\cdot12-17,\,17-12)=(7,5)$, from $(7,5)$ we get $(3,2)$, and from $(3,2)$ we get $(1,1)$; the sign of $x^2-2y^2$ changes at each step.

Claim. Every positive solution of $x^2-2y^2=\pm1$ is obtained from $(1,1)$ by repeating the step $(x,y)\mapsto(x+2y,\,x+y)$.

Proof. Expanding gives $(x+2y)^2-2(x+y)^2$${}=-(x^2-2y^2)$, so the step turns a solution into a solution with the other sign. Now let $(x,y)$ be a solution with $y\ge2$. Then $x^2\ge2y^2-1\gt y^2$ and $x^2\le2y^2+1\lt4y^2$, so $y\lt x\lt2y$, and $(2y-x,\,x-y)$ is a solution in positive integers whose second entry $x-y$ is smaller than $y$. The step sends it back to $(x,y)$. Repeating this descent, the second entry decreases until it is $1$, and then $x^2=2\pm1$ forces $x=1$. Reading the descent backwards proves the claim.

In Euclid's parameters the step is $(m,n)\mapsto(2m+n,\,m)$, starting from $(2,1)$, so the parameters run through the Pell numbers $1,2,5,12,29,70,\dots$, each twice the previous one plus the one before. The triangles $(3,4,5)$, $(20,21,29)$, $(119,120,169)$, $(696,697,985)$, $(4059,4060,5741)$, … are the nearly isosceles right triangles built from consecutive Pell numbers. ^[6]

8. The perimeters grow geometrically

The step of Section 7 is a multiplication by $1+\sqrt2$:

$$\begin{aligned}&(x+y\sqrt2)(1+\sqrt2)\\&\quad=(x+2y)+(x+y)\sqrt2.\end{aligned}$$

So the $k$-th solution is given by $x_k+y_k\sqrt2=(1+\sqrt2)^k$. For the $k$-th triangle, $m=x_k+y_k=y_{k+1}$ and $m+n=x_k+2y_k=x_{k+1}$, so its perimeter $p_k=2m(m+n)=2x_{k+1}y_{k+1}$ is the coefficient of $\sqrt2$ in

$$\begin{aligned}&\bigl(x_{k+1}+y_{k+1}\sqrt2\bigr)^2\\&\quad=(1+\sqrt2)^{2k+2}\\&\quad=(3+2\sqrt2)^{k+1}.\end{aligned}$$

For example, $(3+2\sqrt2)^2=17+12\sqrt2$ gives $p_1=12$, and $(3+2\sqrt2)^3=99+70\sqrt2$ gives $p_2=70$. Since $z=3+2\sqrt2$ satisfies $z^2=6z-1$, the powers satisfy $z^{j+2}=6z^{j+1}-z^j$, and comparing the coefficients of $\sqrt2$ gives $p_{k+1}=6p_k-p_{k-1}$: the perimeters are $12,70,408,2378,13860,\dots$ ^[7] The step increases $m$ and $n$, so the perimeters increase, and the recurrence gives $5p_k\lt p_{k+1}\lt6p_k$. Hence $p_k\ge12\cdot5^{k-1}$: only $O(\log L)$ perimeters lie below a limit $L$, exactly ten below $10^8$, and the ratio of consecutive ones tends to $3+2\sqrt2\approx5.83$.

9. Counting the multiples

By Sections 4 and 5, for an integer limit $L$ the tiling triangles with perimeter below $L$ are the multiples $jT$ of the triangles $T$ of Section 7 with $jp\lt L$, where $p$ is the perimeter of $T$; that is, $1\le j\le\lfloor(L-1)/p\rfloor$, where $\lfloor\cdot\rfloor$ rounds down. Every triangle is counted exactly once, because its primitive triangle and the factor $j$ are unique. So the number of tiling triangles is

$$C(L)=\sum_{p_k\lt L}\left\lfloor\frac{L-1}{p_k}\right\rfloor.$$

Worked example, $L=100$. The multiples of the seven primitive triangles of Section 3 are all $17$ Pythagorean triangles with perimeter below $100$: $\lfloor99/12\rfloor=8$ multiples of $(3,4,5)$, $\lfloor99/30\rfloor=3$ of $(5,12,13)$, $\lfloor99/40\rfloor=2$ of $(8,15,17)$ and one each of the other four. By Section 5 only the multiples of $(3,4,5)$ and $(20,21,29)$ work; for instance $(24,32,40)$ has a hole of side $8$, and $40=5\cdot8$. So

$$\begin{aligned}C(100)&=\left\lfloor\frac{99}{12}\right\rfloor+\left\lfloor\frac{99}{70}\right\rfloor\\&=8+1=9,\end{aligned}$$

the checkpoint of the C++ program. In the same way $C(1000)=83+14+2=99$, where the third term comes from $(119,120,169)$ with perimeter $408$, and $C(10^4)=833+142+24+4$${}=1003$.

How the Code Works

The C++ program ^[9] starts in main, which reads its options with parse_arguments into an Options structure with the defaults limit = 100000000 and run_checkpoints = true: --limit=N sets the limit, read by parse_int_after_prefix from decimal digits only; --skip-checkpoints switches the checkpoint off; any other argument, or a limit below $3$, ends the program with exit status $1$. run_checkpoints verifies that solve(100) returns $9$ and otherwise exits with status $2$. Finally main prints solve(limit).

solve does not use the recurrence of Section 7; it runs through Euclid's pairs of Section 3 and lets the divisibility test find the triangles. The outer loop runs $m=2,3,\dots$ while 2 * m * (m + 1) < limit: for a fixed $m$ the smallest perimeter $2m(m+n)$ is the one with $n=1$, and it grows with $m$, so no later $m$ can give a triangle below the limit. The inner loop runs $n=1,\dots,m-1$ and skips a pair when $m-n$ is even or when std::gcd(m, n) is not $1$; the remaining pairs give every primitive triangle with perimeter below the limit exactly once, together with some larger ones. For each of them the code forms a, b, c and diff = std::abs(a - b), never $0$ by Section 1, and skips the pair unless c % diff == 0, the test of Section 2, which by Section 5 passes exactly for consecutive legs. A passing pair adds (limit - 1) / perimeter, the number of multiples of Section 9, to the 64-bit counter count; a pair whose perimeter is not below the limit adds $0$, so no separate perimeter test is needed. The sides are plain int: for the default limit $m\le7070$, $c\le99\,955\,661$ and every perimeter in the loop is below $2\cdot10^8$. Neither the parser nor the loop checks for overflow; the int arithmetic is safe for every limit up to $2\cdot32767\cdot32768$${}=2\,147\,418\,112$, and a larger --limit value overflows, which is undefined behaviour in C++.

The Python and Java versions run the same loops with the fixed limit $10^8$, without options or checkpoint; Python keeps them in a function solve, which also prints the count, and Java in main. Python leaves its for loop over $m$ with break once $2m(m+1)\ge10^8$ and uses math.gcd, % and floor division //; its integers never overflow. Java uses int sides and a long counter, joins the parity and gcd tests with ||, and computes the gcd with its own method gcd, the Euclidean algorithm with remainders. ^[8]

Complexity and Verification

For a limit $L$ the outer loop ends at the largest $M$ with $2M(M+1)\lt L$, about $\sqrt{L/2}$; for $L=10^8$ this is $M=7070$. The inner loop makes $M(M-1)/2\approx L/4$ steps, here $24\,988\,915$. Of these pairs $12\,496\,225$ have $m-n$ odd and compute a gcd, which takes $O(\log L)$ steps: Java's remainder loop obeys Lamé's bound, ^[8] and the library routines of C++ and Python are logarithmic too; both C++ libraries used here implement the binary gcd algorithm. Then $10\,130\,707$ coprime pairs, the primitive triangles, reach the divisibility test, and exactly ten pass it. Counting each operation on machine-size integers as one step, the time is $O(L\log L)$ and the memory $O(1)$. On a desktop computer, with Clang at -O2, OpenJDK 17 and CPython 3.11 and start-up included, the C++, Java and Python programs need about $0.2$, $0.3$ and $2$ seconds. Sections 7 and 8 give a far faster method: generate the triangles with $(m,n)\mapsto(2m+n,m)$ and add $\lfloor(L-1)/p_k\rfloor$ for each, $O(\log L)$ steps in all; the published programs keep the general search instead.

The C++ program checks $C(100)=9$ before the main run. Further checks, not part of the published solutions, were run for this article. Testing $d\mid c$ directly on each of the $743$ triangles with perimeter below $2000$, found by searching all pairs of legs, agrees with the loop of the programs and with the sum of Section 9 for every integer limit $L$ from $1$ to $2000$; for $L=10^6$ and $L=10^7$ the same holds for all $808\,948$ and $9\,706\,564$ triangles below the limit, tested one by one. For $L=10^8$ the pairs that pass the test are exactly the ten triangles of Section 7, and the solutions of $x^2-2y^2=\pm1$ with $y\le10^6$ are exactly the $16$ produced by its step. The C++ program, built with Clang and with GCC, and the Java and Python programs print the same number, equal to the sum of Section 9 computed from the recurrence.

Footnotes and References

The references below supply the background facts used above. The tiling criterion, the reduction to consecutive legs, the descent for $x^2-2y^2=\pm1$ and the formula for the perimeters are derived explicitly in this article.

Project Euler 139 — Pythagorean Tiles. Four copies of a right triangle with integer sides form a square with a square hole; for (3, 4, 5) the hole tiles the square, for (5, 12, 13) it does not. The task asks how many Pythagorean triangles with perimeter less than one hundred million allow such a tiling.
Wikipedia — Pythagorean theorem. One of the algebraic proofs arranges four copies of a right triangle with sides a, b and c inside a square of side c; the small square in the middle has side b − a, b being the longer leg, and the area of the large square is (b − a)² + 4 · ab/2 = a² + b².
Wikipedia — Pythagorean triple. Every triple is a multiple of a primitive one, in which a, b and c are coprime. Euclid's formula with m > n > 0 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.
Wikipedia — Square root of 2. The square root of 2, the hypotenuse of the isosceles right triangle with legs 1, is irrational.
Wikipedia — Pell's equation. For a positive integer n that is not a square, all solutions of x² − ny² = 1 in positive integers come from the fundamental solution through xₖ + yₖ√n = (x₁ + y₁√n)ᵏ; for n = 2 it is (3, 2).
Wikipedia — Pell number. Each Pell number is twice the previous one plus the one before, (1 + √2)ⁿ = Hₙ + Pₙ√2, and the pairs (Hₙ, Pₙ) are exactly the non-negative solutions of H² − 2P² = ±1; Pell numbers give the nearly isosceles right triangles (4, 3, 5), (20, 21, 29), (120, 119, 169), … with legs one unit apart.
OEIS A001542. The even Pell numbers a(n) = 6a(n − 1) − a(n − 2), with a(0) = 0 and a(1) = 2, begin 0, 2, 12, 70, 408, 2378, …; from a(2) = 12 on, the entry's formula writes each term as the perimeter X + (X + 1) + Z of a triangle (X, X + 1, Z), for example 70 = 20 + 21 + 29.
Wikipedia — Euclidean algorithm. It repeatedly replaces the larger number by its remainder after division by the smaller one until the remainder is zero; Lamé proved in 1844 that it never needs more steps than five times the number of decimal digits of the smaller number.
C++ — Euler139.cpp. The linked immutable C++ revision contains parse_arguments, solve and the checkpoint 9 for the limit 100 in run_checkpoints. It is the implementation record for this article.

Problem 139 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int limit = 100000000;
    bool run_checkpoints = true;
};

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

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(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_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

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

i64 solve(const int limit) {
    i64 count = 0;

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

            const int a = m * m - n * n;
            const int b = 2 * m * n;
            const int c = m * m + n * n;
            const int diff = std::abs(a - b);
            if (c % diff != 0) {
                continue;
            }

            const int perimeter = a + b + c;
            count += (limit - 1) / perimeter;
        }
    }

    return count;
}

bool run_checkpoints() {
    if (solve(100) != 9) {
        std::cerr << "Checkpoint failed for limit=100" << '\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 139: Pythagorean tiles
# Count primitive Pythagorean triples with perimeter < 10^8 where c % |a-b| == 0.

from math import gcd

def solve():
    limit = 100000000
    count = 0
    for m in range(2, limit):
        if 2 * m * (m + 1) >= limit: break
        for n in range(1, m):
            if (m - n) % 2 == 0: continue
            if gcd(m, n) != 1: continue
            a = m*m - n*n
            b = 2*m*n
            c = m*m + n*n
            diff = abs(a - b)
            if c % diff != 0: continue
            perimeter = a + b + c
            count += (limit - 1) // perimeter
    print(count)

solve()

Java

public class Euler139 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        int limit = 100000000;
        long count = 0;
        for (int m = 2; 2 * m * (m + 1) < limit; m++)
            for (int n = 1; n < m; n++) {
                if ((m - n) % 2 == 0 || gcd(m, n) != 1)
                    continue;
                int a = m * m - n * n, b = 2 * m * n, c = m * m + n * n, d = Math.abs(a - b);
                if (c % d != 0)
                    continue;
                count += (limit - 1) / (a + b + c);
            }
        System.out.println(count);
    }
}