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 Apr 19, 2026

Problem #0176

Level Level 10

Solved By 2,247

Languages C++, Python

Answer 96818198400000

Length 316 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 Analysis

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.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

\boxed{96818198400000}

Complexity

The algorithm enumerates multiplicative partitions of 95095 (a small number of partitions since 95095 has only 5 prime factors). For each partition, the computation is $O(k)$ where $k$ is the number of parts. Total time: effectively $O(1)$ .

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)