Problem 139: Pythagorean Tiles

Mathematical Foundation

Theorem 1. Every primitive Pythagorean triple can be parameterized as $(a, b, c) = (m^2 - n^2, \; 2mn, \; m^2 + n^2)$ where $m > n > 0$, $\gcd(m, n) = 1$, and $m \not\equiv n \pmod{2}$.

Proof. Classical result. See any number theory textbook (e.g., Hardy & Wright, Chapter 13). $\square$

Theorem 2. The tiling condition $|b - a| \mid c$ is preserved under scaling: if it holds for a primitive triple $(a, b, c)$, it holds for $(ka, kb, kc)$ for any positive integer $k$.

Proof. $|kb - ka| \mid kc \iff k|b - a| \mid kc \iff |b - a| \mid c$. $\square$

Lemma 1. For the primitive triple $(a, b, c) = (m^2 - n^2, 2mn, m^2 + n^2)$:

The tiling condition becomes $(m^2 + n^2) \bmod |2mn - (m^2 - n^2)| = 0$.

Proof. Direct computation: $b - a = 2mn - (m^2 - n^2) = -(m^2 - 2mn - n^2) = -((m-n)^2 - 2n^2)$. So $|b - a| = |(m-n)^2 - 2n^2|$. The tiling condition is $|b - a| \mid c$, i.e., $(m^2 + n^2) \bmod |b - a| = 0$. $\square$

Theorem 3. For each primitive triple satisfying the tiling condition with perimeter $p_0 = 2m(m+n)$, the number of valid triples (including non-primitive) with perimeter at most $P$ is $\lfloor P / p_0 \rfloor$.

Proof. By Theorem 2, every multiple $k(a, b, c)$ also satisfies the tiling condition, and its perimeter is $kp_0$. We need $kp_0 \leq P$, giving $k \leq \lfloor P/p_0 \rfloor$. Every non-primitive Pythagorean triple satisfying the condition is a multiple of some primitive triple satisfying the condition (since the condition is scale-invariant by Theorem 2 and every Pythagorean triple is a multiple of a primitive one). $\square$

Editorial

Count Pythagorean triples (a, b, c) with perimeter <= 10^8 where c % |b - a| == 0 (the tiling condition). Enumerate primitive triples via (m, n) parameterization and count multiples.

Pseudocode

    P = 100000000
    count = 0
    For m from 2 to floor(sqrt(P/2)):
        For n from 1 to m-1:
            if (m - n) % 2 == 0: // same parity, skip
                continue
            If gcd(m, n) != 1 then
                continue
            a = m*m - n*n
            b = 2*m*n
            c = m*m + n*n
            perimeter = a + b + c // = 2*m*(m+n)
            If perimeter > P then
                break
            diff = abs(b - a)
            If c % diff == 0 then
                count += P // perimeter // floor division
    Return count

Complexity Analysis

• Time: $O(P / \log P)$ — the number of primitive Pythagorean triples with perimeter $\leq P$ is $O(P / \log P)$ by a result of Lehmer. For each, we do $O(\log m)$ work for the GCD.
• Space: $O(1)$ auxiliary space (no sieve needed; GCD is computed on the fly).

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long P = 100000000LL;
    long long count = 0;

    for (long long m = 2; 2 * m * (m + 1) <= P; m++) {
        for (long long n = 1; n < m; n++) {
            if ((m - n) % 2 == 0) continue;
            if (__gcd(m, n) != 1) continue;

            long long a = m * m - n * n;
            long long b = 2 * m * n;
            long long c = m * m + n * n;
            long long perim = a + b + c; // = 2*m*(m+n)

            if (perim > P) break;

            long long diff = abs(b - a);
            if (diff > 0 && c % diff == 0) {
                count += P / perim;
            }
        }
    }

    cout << count << endl;
    return 0;
}

"""
Problem 139: Pythagorean Tiles

Count Pythagorean triples (a, b, c) with perimeter <= 10^8 where
c % |b - a| == 0 (the tiling condition).

Enumerate primitive triples via (m, n) parameterization and count multiples.
"""

import math

def solve():
    P = 100_000_000
    count = 0

    m = 2
    while 2 * m * (m + 1) <= P:
        for n in range(1, m):
            if (m - n) % 2 == 0:
                continue
            if math.gcd(m, n) != 1:
                continue

            a = m * m - n * n
            b = 2 * m * n
            c = m * m + n * n
            perim = a + b + c

            if perim > P:
                break

            diff = abs(b - a)
            if diff > 0 and c % diff == 0:
                count += P // perim
        m += 1

    return count

if __name__ == "__main__":
    answer = solve()
assert answer == 10057761
print(answer)