Project Euler

Right-angled Triangles That Share a Cathetus

The four right triangles with sides (9,12,15), (12,16,20), (5,12,13), and (12,35,37) all share a cathetus (leg) of length 12. It can be shown that no other integer right triangle exists with 12 as...

Source sync May 21, 2026

Problem #0176

Level Level 10

Solved By 2,247

Languages C++, Python

Answer 96818198400000

Length 372 words

linear_algebramodular_arithmeticnumber_theory

The four right-angled triangles with sides $(9,12,15)$, $(12,16,20)$, $(5,12,13)$ and $(12,35,37)$ all have one of the shorter sides (catheti) equal to $12$. It can be shown that no other integer sided right-angled triangle exists with one of the catheti equal to $12$.

Find the smallest integer that can be the length of a cathetus of exactly $47547$ different integer sided right-angled triangles.

Mathematical Development

Counting Right Triangles with a Given Leg

For a fixed leg $a$ , we need to count integer solutions to:

a^2 + b^2 = c^2 \implies (c-b)(c+b) = a^2

Case 1: $a$ is odd with $a = p_1^{e_1} \cdots p_k^{e_k}$ .

All divisor pairs $(d_1, d_2)$ of $a^2$ with $d_1 < d_2$ have the same (odd) parity, giving valid $(b, c)$ . The count is:

f(a) = \frac{d(a^2) - 1}{2} = \frac{\prod(2e_i + 1) - 1}{2}

Case 2: $a$ is even with $a = 2^{e_0} \cdot p_1^{e_1} \cdots p_k^{e_k}$ , $e_0 \geq 1$ .

We need both $c - b$ and $c + b$ to be even. Setting $c - b = 2s$ , $c + b = 2t$ , we get $st = a^2/4$ . The count of valid pairs is:

f(a) = \frac{d(a^2/4) - 1}{2} = \frac{(2e_0 - 1)\prod(2e_i + 1) - 1}{2}

Setting Up the Equation

We need $f(a) = 47547$ .

Odd case: $\prod(2e_i + 1) = 95095$

Even case: $(2e_0 - 1)\prod(2e_i + 1) = 95095$

Factoring 95095

95095 = 5 \times 7 \times 11 \times 13 \times 19

Finding the Minimum

We enumerate all multiplicative partitions of 95095 into factors $\geq 2$ . For each partition:

Odd case: Each factor $f_i$ gives exponent $e_i = (f_i - 1)/2$ for an odd prime. Assign largest exponents to smallest primes to minimize $a$ .
Even case: One factor $f_0$ gives $e_0 = (f_0 + 1)/2$ for the prime 2. Remaining factors give exponents for odd primes.

After exhaustive search over all partitions, the minimum is achieved in the even case with partition $\{19, 13, 11, 7, 5\}$ where factor 19 is assigned to prime 2 ( $e_0 = 10$ ) and the rest to odd primes:

a = 2^{10} \times 3^6 \times 5^5 \times 7^3 \times 11^2 = 96818198400000

Verification

$(2 \times 10 - 1)(2 \times 6 + 1)(2 \times 5 + 1)(2 \times 3 + 1)(2 \times 2 + 1) = 19 \times 13 \times 11 \times 7 \times 5 = 95095$ and $(95095 - 1)/2 = 47547$ . Confirmed.

Editorial

Once the divisor formula is written down, the search is no longer geometric. We only need to realize the target value

2f(a)+1 = 95095 = 5 \cdot 7 \cdot 11 \cdot 13 \cdot 19

as the product of the odd factors coming from the prime exponents of the leg length. That means enumerating multiplicative partitions of 95095 and translating each factor into an exponent.

For every partition, the candidate leg is minimized by assigning the largest exponents to the smallest primes. The code checks both the odd-leg interpretation and the even-leg interpretation, where one factor is reserved for the power of 2 through the term $2e_0-1$ . Taking the minimum over all such assignments yields the smallest leg with exactly 47547 right-triangle partners.

Pseudocode

Factor the target odd product 95095.
Enumerate every multiplicative partition of 95095 into factors at least 2.

For each partition:
    Interpret all factors as odd-prime exponent terms.
    Convert each factor $f$ into exponent $(f-1)/2$.
    Assign the largest exponents to the smallest odd primes and form the candidate leg.
    Update the best answer if this candidate is smaller.

    Then try the even-leg case:
        choose one factor to play the role of $2e_0-1$,
        convert it into the exponent of 2 via $(f+1)/2$,
        convert the remaining factors as before,
        assign the remaining exponents to the smallest odd primes,
        and update the best answer again.

Return the smallest candidate found.

Complexity Analysis

The algorithm enumerates multiplicative partitions of 95095. Since 95095 has only five prime factors and relatively few factor-groupings, the search space is tiny. Each partition is processed in time linear in its number of parts, so the whole computation is effectively constant-time.

Answer

\boxed{96818198400000}

C++ project_euler/problem_176/solution.cpp

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

// Problem 176: Right-angled Triangles That Share a Cathetus
// Find smallest a with exactly 47547 right triangles having leg a.
//
// For odd a = prod p_i^{e_i}: f(a) = (prod(2e_i+1) - 1) / 2
// For even a = 2^{e0} * prod p_i^{e_i}: f(a) = ((2e0-1)*prod(2e_i+1) - 1) / 2
//
// We need f(a) = 47547, so the product = 95095 = 5*7*11*13*19.

typedef __int128 lll;

int target = 95095;
vector<int> divisors;
vector<vector<int>> partitions;

void get_divisors(int n) {
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    divisors.push_back(n);
    sort(divisors.begin(), divisors.end());
}

void gen_partitions(int n, int min_f, vector<int>& cur) {
    if (n == 1) {
        partitions.push_back(cur);
        return;
    }
    for (int d : divisors) {
        if (d < min_f) continue;
        if (d > n) break;
        if (n % d != 0) continue;
        cur.push_back(d);
        gen_partitions(n / d, d, cur);
        cur.pop_back();
    }
}

int small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

// Compute value using logarithms for comparison, actual value for result
double log_value(int e0, vector<int>& exps) {
    double v = e0 * log(2.0);
    sort(exps.rbegin(), exps.rend());
    for (int i = 0; i < (int)exps.size(); i++)
        v += exps[i] * log((double)small_primes[i + 1]);
    return v;
}

lll actual_value(int e0, vector<int>& exps) {
    sort(exps.rbegin(), exps.rend());
    lll v = 1;
    for (int j = 0; j < e0; j++) v *= 2;
    for (int i = 0; i < (int)exps.size(); i++)
        for (int j = 0; j < exps[i]; j++)
            v *= small_primes[i + 1];
    return v;
}

void print128(lll x) {
    if (x == 0) { printf("0\n"); return; }
    string s;
    while (x > 0) { s += '0' + (int)(x % 10); x /= 10; }
    reverse(s.begin(), s.end());
    printf("%s\n", s.c_str());
}

int main() {
    get_divisors(target);
    vector<int> cur;
    gen_partitions(target, 2, cur);

    double best_log = 1e18;
    lll best_val = -1;

    for (auto& p : partitions) {
        // Case 1: odd a
        {
            vector<int> exps;
            for (int f : p) exps.push_back((f - 1) / 2);
            double lv = 0;
            sort(exps.rbegin(), exps.rend());
            for (int i = 0; i < (int)exps.size(); i++)
                lv += exps[i] * log((double)small_primes[i + 1]);
            if (lv < best_log) {
                best_log = lv;
                best_val = actual_value(0, exps);
            }
        }

        // Case 2: even a
        set<int> seen;
        for (int idx = 0; idx < (int)p.size(); idx++) {
            if (!seen.insert(p[idx]).second) continue;
            int e0 = (p[idx] + 1) / 2;
            vector<int> exps;
            for (int j = 0; j < (int)p.size(); j++) {
                if (j == idx) continue;
                int e = (p[j] - 1) / 2;
                if (e > 0) exps.push_back(e);
            }
            sort(exps.rbegin(), exps.rend());
            double lv = e0 * log(2.0);
            for (int i = 0; i < (int)exps.size(); i++)
                lv += exps[i] * log((double)small_primes[i + 1]);
            if (lv < best_log) {
                best_log = lv;
                best_val = actual_value(e0, exps);
            }
        }
    }

    print128(best_val);
    return 0;
}

Python project_euler/problem_176/solution.py

"""
Problem 176: Right-angled Triangles That Share a Cathetus

Find the smallest integer that is a leg of exactly 47547 right triangles.

For odd leg a: f(a) = (prod(2*ei+1) - 1) / 2
For even leg a = 2^e0 * m: f(a) = ((2*e0-1)*prod(2*ei+1) - 1) / 2

We need the product = 95095 = 5 * 7 * 11 * 13 * 19.
Enumerate all multiplicative partitions into factors >= 2 (odd factors since 95095 is odd).
"""

TARGET = 95095

def get_divisors(n):
    divs = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n // i)
        i += 1
    return sorted(divs)

divisors = [d for d in get_divisors(TARGET) if d >= 2]

partitions = []

def gen_partitions(n, min_f, current):
    if n == 1:
        partitions.append(current[:])
        return
    for d in divisors:
        if d < min_f:
            continue
        if d > n:
            break
        if n % d != 0:
            continue
        current.append(d)
        gen_partitions(n // d, d, current)
        current.pop()

gen_partitions(TARGET, 2, [])

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

best = float('inf')

for partition in partitions:
    # Case 1: odd a - all factors map to exponents for odd primes
    exps = sorted([(f - 1) // 2 for f in partition], reverse=True)
    a_val = 1
    for i, e in enumerate(exps):
        a_val *= primes[1 + i] ** e  # odd primes starting from 3
    if a_val < best:
        best = a_val

    # Case 2: even a - one factor becomes (2*e0-1), rest map to odd prime exponents
    seen = set()
    for idx in range(len(partition)):
        if partition[idx] in seen:
            continue
        seen.add(partition[idx])
        f2 = partition[idx]
        e0 = (f2 + 1) // 2  # 2*e0-1 = f2 => e0 = (f2+1)/2

        remaining = sorted([(partition[j] - 1) // 2 for j in range(len(partition))
                            if j != idx], reverse=True)
        # Remove zero exponents
        remaining = [e for e in remaining if e > 0]

        a_val = 2 ** e0
        for i, e in enumerate(remaining):
            a_val *= primes[1 + i] ** e
        if a_val < best:
            best = a_val

print(best)