Problem 39: Integer Right Triangles

Mathematical Development

Definitions

Definition 1. A Pythagorean triple $(a, b, c)$ is a triple of positive integers satisfying $a^2 + b^2 = c^2$. It is primitive if $\gcd(a, b, c) = 1$.

Definition 2. For a positive integer $p$, define

Theoretical Development

Theorem 1 (Euclid’s parametrization). Every primitive Pythagorean triple $(a, b, c)$ with $a$ odd and $b$ even is uniquely given by

where $m, n \in \mathbb{Z}_{>0}$ satisfy $m > n$, $\gcd(m, n) = 1$, and $m \not\equiv n \pmod{2}$. Conversely, every such $(m, n)$ produces a primitive triple.

Proof. This is classical. From $a^2 = c^2 - b^2 = (c-b)(c+b)$ with $\gcd(a,b,c) = 1$ and standard divisibility arguments, one establishes the bijection. The coprimality and opposite-parity conditions on $(m, n)$ are necessary and sufficient for primitivity. $\blacksquare$

Lemma 1 (Perimeter formula). For the primitive triple generated by $(m, n)$, the perimeter is $p_0 = 2m(m + n)$. The general triple $(ka, kb, kc)$ for $k \ge 1$ has perimeter $p = 2km(m + n)$.

Proof. $a + b + c = (m^2 - n^2) + 2mn + (m^2 + n^2) = 2m^2 + 2mn = 2m(m + n)$. Scaling by $k$ multiplies the perimeter by $k$. $\blacksquare$

Corollary 1.1. Every Pythagorean triple has even perimeter. Hence $N(p) = 0$ for all odd $p$.

Proof. By Lemma 1, $p = 2km(m+n)$ is even. $\blacksquare$

Theorem 2 (Closed-form for $b$). Given $a + b + c = p$ and $a^2 + b^2 = c^2$ with $a, b, c > 0$, we have

Proof. Substitute $c = p - a - b$ into $a^2 + b^2 = c^2$:

Cancelling $a^2 + b^2$:

$\blacksquare$

Lemma 2 (Bounds on $a$). For a valid triple with $1 \le a \le b < c$ and $a + b + c = p$:

1. $a \ge 1$.
2. $a < p/3$.

Proof. From $a \le b < c$ and $a + b + c = p$: since $b \ge a$ and $c > b \ge a$, we get $p = a + b + c > 3a$, whence $a < p/3$. Also $b > 0$ requires $p(p - 2a) > 0$, i.e., $a < p/2$, but $p/3 < p/2$ is the tighter bound. $\blacksquare$

Theorem 3 (Counting via divisors). $N(p)$ equals the number of integers $a$ with $1 \le a < p/3$ such that $2(p-a) \mid p(p-2a)$ and the resulting $b \ge a$.

Proof. By Theorem 2, given $p$ and $a$, the value $b = p(p-2a)/[2(p-a)]$ is the unique candidate. It yields a valid triple iff $b$ is a positive integer and $b \ge a$. The bound $a < p/3$ is from Lemma 2. $\blacksquare$

Theorem 4 (Solution). Among all $p \le 1000$, the maximum of $N(p)$ is achieved at $p = 840$, with $N(840) = 8$.

Proof. $840 = 2^3 \cdot 3 \cdot 5 \cdot 7$ has $\tau(840) = 32$ divisors, making it highly composite. By Theorem 3, each valid factorization $p = 2km(m+n)$ contributes one triple. The large divisor count of 840 maximizes the number of such factorizations.

The 8 triples with perimeter 840 are:

Exhaustive computation over all even $p \le 1000$ confirms no other perimeter achieves $N(p) \ge 8$. $\blacksquare$

Editorial

We examine only even perimeters, since odd perimeters cannot occur for Pythagorean triples. For each admissible perimeter $p \le P$, we enumerate the smallest side $a$ in its valid range, recover the unique candidate value of $b$ from the derived closed formula, and count the cases in which $b$ is an integer satisfying $b \ge a$. The perimeter with the largest count is retained throughout the scan.

Pseudocode

Algorithm: Perimeter with the Most Integer Right Triangles
Require: A perimeter bound P.
Ensure: The perimeter p ≤ P for which the equation a^2 + b^2 = c^2 with a + b + c = p has the most integer solutions.
1: Initialize best_p ← 0 and best_count ← 0.
2: For each even perimeter p with 12 ≤ p ≤ P do:
3:     Count the admissible values of a for which b ← p(p - 2a) / (2(p - a)) is integral and yields a valid Pythagorean triple.
4:     If this count exceeds best_count, update best_count ← count and best_p ← p.
5: Return best_p.

Complexity Analysis

Proposition. The algorithm runs in $O(P^2)$ time and $O(1)$ space.

Proof. The outer loop runs $P/2$ times (even values only). The inner loop runs at most $\lfloor p/3 \rfloor < P/3$ times per iteration. Each iteration performs $O(1)$ arithmetic (a division and modulus check). Total operations: $\sum_{p \text{ even}} \lfloor p/3 \rfloor \le (P/2) \cdot (P/3) = P^2/6$. Hence $O(P^2)$. With $P = 1000$: at most $\sim 1.7 \times 10^5$ iterations. $\blacksquare$

Answer

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

int main() {
    const int LIMIT = 1000;
    int best_p = 0, best_count = 0;

    for (int p = 2; p <= LIMIT; p += 2) {
        int count = 0;
        for (int a = 1; a < p / 3; a++) {
            int num = p * (p - 2 * a);
            int den = 2 * (p - a);
            if (num % den == 0 && num / den >= a)
                count++;
        }
        if (count > best_count) {
            best_count = count;
            best_p = p;
        }
    }

    cout << best_p << endl;
    return 0;
}

"""Project Euler Problem 39: Integer Right Triangles"""

def solve():
    LIMIT = 1000
    best_p, best_count = 0, 0
    for p in range(2, LIMIT + 1, 2):
        count = 0
        for a in range(1, p // 3):
            num = p * (p - 2 * a)
            den = 2 * (p - a)
            if num % den == 0 and num // den >= a:
                count += 1
        if count > best_count:
            best_count = count
            best_p = p
    return best_p

answer = solve()
assert answer == 840
print(answer)