Problem 176: Right-angled Triangles That Share a Cathetus

Project Euler Problem 176 Solution

EulerSolve provides an optimized solution for Project Euler Problem 176, Right-angled Triangles That Share a Cathetus, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For a fixed positive integer cathetus $n$, let $T(n)$ be the number of distinct integer right triangles that use $n$ as one leg. The task is to find the smallest $n$ for which $T(n)=47547$. A brute-force search over candidate catheti would be completely impractical. The key observation is that each triangle can be encoded by a factor pair of a square, so the problem becomes an inverse divisor-count problem rather than a geometric search. Mathematical Approach Write the triangle as $(a,n,c)$, where $a$ is the other leg and $c$ is the hypotenuse. The whole derivation comes from rewriting the Pythagorean equation in a form that exposes divisors of a square. Encoding a Triangle by a Product $uv=n^2$ Starting from $$a^2+n^2=c^2,$$ we rewrite it as $$c^2-a^2=(c-a)(c+a)=n^2.$$ Now define $$u=c-a,\qquad v=c+a.$$ Then $u$ and $v$ are positive integers with $u<v$ and $$uv=n^2.$$ Conversely, every factor pair $u<v$ of $n^2$ with the same parity produces $$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$ which are integers and therefore define a valid right triangle. So counting triangles with cathetus $n$ is exactly the same as counting same-parity factor pairs of $n^2$, excluding the central pair $u=v$, which would give the degenerate case $a=0$....

Detailed mathematical approach

Problem Summary

A right-angled triangle has two shorter sides, the catheti, and the hypotenuse. For a positive integer $n$ let $T(n)$ be the number of different right-angled triangles with integer sides in which $n$ is one of the two catheti. The statement shows that $T(12)=4$: the triangles are $(9,12,15)$, $(12,16,20)$, $(5,12,13)$ and $(12,35,37)$, and there are no others. We must find the smallest integer $n$ with $T(n)=47547$. ^[1]

The whole solution in one sentence: a triangle with cathetus $n$ is a way to write $n^2$ as a product of two different factors of equal parity, so the number of triangles is determined by the exponents in the prime factorisation of $n$, and the smallest $n$ with $47547$ triangles is the smallest of $255$ candidates built from the ways to write $2\cdot47547+1=95095$ as a product of odd factors, with the largest exponents on the smallest primes.

Mathematical Approach

Instead of testing $n=1,2,3,\dots$ one by one, we find a formula for $T(n)$ in terms of the prime factorisation of $n$ and then build the smallest number for which it equals $47547$.

1. Small cases

For a small cathetus $n$ we can try every other cathetus $a$ and test whether $a^2+n^2$ is a perfect square; Section 2 shows that $a\lt n^2/2$, so this search is finite. For $n=1,2,\dots,16$ it gives the counts

$0, 0, 1, 1, 1, 1, 1, 2,$
$2, 1, 1, 4, 1, 1, 4, 3.$

For example, $15$ is a cathetus of $(8,15,17)$, $(15,20,25)$, $(15,36,39)$ and $(15,112,113)$. Every odd prime $p$ is a cathetus of exactly one triangle, $(p,\,(p^2-1)/2,\,(p^2+1)/2)$, while $12=2^2\cdot3$ and $15=3\cdot5$ are catheti of four. Powers of $2$ behave differently from powers of odd primes: $T(16)=3$, but $T(81)=4$, and $T(2^k)=k-1$ for every $k\ge1$.

2. A triangle is a factor pair of $n^2$

Let $a$ be the other cathetus and $c$ the hypotenuse, so $a^2+n^2=c^2$. Moving $a^2$ to the other side and factoring the difference of two squares gives ^[2]

$$n^2=c^2-a^2=(c-a)(c+a).$$

Put $u=c-a$ and $v=c+a$. These are positive integers with $uv=n^2$, and their difference $v-u=2a$ is positive and even, so $u\lt v$ and $u$, $v$ have the same parity. Conversely, if $u\lt v$ are positive integers of the same parity with $uv=n^2$, then $a=(v-u)/2$ and $c=(u+v)/2$ are positive integers with $c^2-a^2=uv=n^2$. The two constructions undo each other, so $T(n)$ is the number of factorisations $n^2=uv$ with $u\lt v$ and $u\equiv v\pmod 2$. Since $u\ge1$, the other cathetus satisfies $a\lt v/2\le n^2/2$.

For $n=12$, the factorisations of $144$ with $u\lt v$ are $1\cdot144$, $2\cdot72$, $3\cdot48$, $4\cdot36$, $6\cdot24$, $8\cdot18$ and $9\cdot16$. Three of them pair an odd factor with an even one; the other four give $a=35,16,9,5$, exactly the four triangles of the statement.

3. Counting the factor pairs

Write $d(x)$ for the number of positive divisors of $x$. ^[4] The divisors of a square $y^2$ come in pairs $u$ and $y^2/u$, and only $u=y$ is its own partner, so $d(y^2)$ is odd and exactly $(d(y^2)-1)/2$ divisors are smaller than $y$. Because $uv=n^2$, the condition $u\lt v$ means $u\lt n$.

If $n$ is odd, all divisors of $n^2$ are odd, the parity condition always holds, and $T(n)=(d(n^2)-1)/2$.
If $n$ is even, $uv=n^2$ is even, so one factor is even, and equal parity makes both even: $u=2r$ and $v=2s$ with $rs=(n/2)^2$ and $r\lt s$. Conversely, every such pair $r\lt s$ gives the admissible pair $(2r,2s)$. Hence $T(n)=(d((n/2)^2)-1)/2$.

With $m=n$ for odd $n$ and $m=n/2$ for even $n$, both cases read

$$T(n)=\frac{d(m^2)-1}{2}.$$

For $n=12$ we get $m=6$ and $d(36)=9$, so $T(12)=4$ once more; the divisors $r=1,2,3,4$ of $36$ below $6$ give $u=2,4,6,8$. For an odd number $o$, the numbers $o$ and $2o$ have the same $m$, so $T(2o)=T(o)$. The OEIS entry for the number of Pythagorean triangles with leg $n$ records the same formula. ^[5]

4. The divisors of a square

By the fundamental theorem of arithmetic, $m$ has exactly one factorisation $m=p_1^{e_1}\cdots p_r^{e_r}$ into powers of distinct primes, up to the order of the factors; for $m=1$ the list is empty and the product is $1$. ^[3] A divisor of $m^2=p_1^{2e_1}\cdots p_r^{2e_r}$ is formed by choosing every exponent independently from $0,1,\dots,2e_i$, so ^[4]

$$d(m^2)=(2e_1+1)(2e_2+1)\cdots(2e_r+1).$$

Now we return from $m$ to $n$. Write $n=2^k q_1^{e_1}\cdots q_r^{e_r}$ with $k\ge0$ and distinct odd primes $q_i$. If $k=0$, then $m=n$. If $k\ge1$, then $m=n/2$ contains the prime $2$ with the exponent $k-1$, which contributes the factor $2(k-1)+1=2k-1$. So $T(n)=(D(n)-1)/2$, where

$$D(n)=\begin{cases}(2e_1+1)\cdots(2e_r+1), & k=0,\\(2k-1)(2e_1+1)\cdots(2e_r+1), & k\ge1.\end{cases}$$

For example, $D(12)=3\cdot3=9$ and $D(15)=3\cdot3=9$, so both numbers have four triangles, while $D(16)=2\cdot4-1=7$ and $D(81)=2\cdot4+1=9$. This explains Section 1: an exponent $k$ contributes $2k-1$ on the prime $2$ but $2k+1$ on an odd prime.

5. The target as a factorisation problem

So $T(n)=47547$ holds exactly when $D(n)=2\cdot47547+1=95095$, and

$$95095=5\cdot7\cdot11\cdot13\cdot19.$$

Write $t$ for a target number of triangles and $P=2t+1$. A number $n$ with $T(n)=t$ yields an unordered list of odd factors $2e_i+1\ge3$, one for each odd prime of $n$, whose product is $P$ or, if $n$ is even, $P/g$ with $g=2k-1\ge1$, the factor of the prime $2$. An unordered list of factors greater than $1$ with a given product is called a multiplicative partition. ^[8] Conversely, an odd divisor $g$ of $P$ and a multiplicative partition of $P/g$, the empty one if $P/g=1$, describe numbers with $t$ triangles: $2$ gets the exponent $k=(g+1)/2$, and every factor $f$ gives the exponent $(f-1)/2$ to its own odd prime; odd numbers $n$ correspond to the partitions of $P$ itself. The divisor $g=1$ means $k=1$, so $n=2o$ with $o$ odd; by Section 3 the smaller number $o$ has the same count, so $g=1$ never wins.

6. Which primes get which exponents

Fix $k$ and the list of odd exponents. Every choice of distinct odd primes for them gives the same $D(n)$, and a choice with the smallest product exists because the products are positive integers. Two exchanges find it:

if an odd prime $q$ is used while a smaller odd prime $p$ is not, replacing $q$ by $p$ makes $n$ smaller, so only the smallest odd primes $3,5,7,\dots$ are used;
if primes $p\lt q$ carry exponents $a\lt b$, swapping the exponents turns $p^aq^b$ into $p^bq^a$, which is smaller by the factor $(p/q)^{b-a}\lt1$.

Both exchanges keep $D(n)$ and decrease $n$, so the smallest product puts the exponents in non-increasing order on $3,5,7,\dots$. In logarithms this is the rearrangement inequality: $\sum e_i\ln p_i$ is smallest when the $e_i$ and the $\ln p_i$ are ordered oppositely. ^[7] Highly composite numbers have the same shape for the same reason. ^[6] The prime $2$ stays out of these exchanges, because by Section 4 moving an exponent between $2$ and an odd prime changes $D(n)$; its factor $g$ is therefore chosen separately, by trying every odd divisor of $P$.

7. Why the smallest candidate is the answer

For every odd divisor $g$ of $P$ and every multiplicative partition of $P/g$, and for every multiplicative partition of $P$ itself, build the number of Section 6; we call these numbers the candidates. Every candidate has exactly $t$ triangles by Section 4, so none is smaller than the smallest number $n^{*}$ with $t$ triangles, which exists because $2^{t+1}$, for example, has $t$ triangles. Conversely, the exponents of $n^{*}$ determine one of the choices above, and by Section 6 the candidate of that choice is at most $n^{*}$. Hence the smallest candidate is $n^{*}$.

8. Worked example: four triangles

For $t=4$ we have $P=9$, whose multiplicative partitions are $9$ and $3\cdot3$. The odd candidates are $3^4=81$ and $3\cdot5=15$. For even candidates, $g=1$ gives $2\cdot81=162$ and $2\cdot15=30$; $g=3$ gives $k=2$ and leaves the factor $3$, so $2^2\cdot3=12$; and $g=9$ gives $k=5$, so $2^5=32$. The smallest of these six candidates is $12$: the cathetus of the statement is also the smallest number with four triangles, which is one of the checks in the C++ program.

9. Worked example: 52 triangles

For $t=52$ we have $P=105=3\cdot5\cdot7$. The multiplicative partitions $105$, $3\cdot35$, $5\cdot21$, $7\cdot15$ and $3\cdot5\cdot7$ give the odd candidates $3^{52}$, $3^{17}\cdot5$, $3^{10}\cdot5^2$, $3^7\cdot5^3$ and $3^3\cdot5^2\cdot7=4725$. For even candidates, each odd divisor $g$ of $105$ fixes $k=(g+1)/2$ and leaves $105/g$ to the odd primes:

$g=1$, $k=1$: twice the odd candidates, at best $9450$;
$g=3$, $k=2$: $2^2\cdot3^{17}$ or $2^2\cdot3^3\cdot5^2=2700$;
$g=5$, $k=3$: $2^3\cdot3^{10}$ or $2^3\cdot3^3\cdot5=1080$;
$g=7$, $k=4$: $2^4\cdot3^7$ or $2^4\cdot3^2\cdot5=720$;
$g=15,21,35,105$: $2^8\cdot3^3=6912$, $2^{11}\cdot3^2=18432$, $2^{18}\cdot3=786432$ and $2^{53}$.

The smallest of these $20$ candidates is $720=2^4\cdot3^2\cdot5$, and a direct scan of all smaller numbers confirms that $720$ is the first cathetus with exactly $52$ triangles.

10. How many candidates there are

Because $95095$ is a product of five different primes, a multiplicative partition of it is the same as a partition of the set $\{5,7,11,13,19\}$ into groups, each group multiplied together. The partitions of a set of $j$ elements are counted by the Bell number $B_j$, with $B_3=5$, $B_4=15$, $B_5=52$ and $B_6=203$. ^[8] So there are $52$ odd candidates. For the even candidates, add a sixth element, a marker $\star$, and partition all six: the primes in the group of $\star$ multiply to $g$, which is $1$ if $\star$ is alone, and the other groups form the partition of $95095/g$. Every even candidate arises from exactly one such partition, so there are $B_6=203$ of them. Only $52+203=255$ candidates have to be compared, and since no partition has more than five parts, only the odd primes $3,5,7,11,13$ can occur.

How the Code Works

The C++ program accepts two optional arguments: --target-count= followed by a number replaces $47547$ by another target $t$, and --skip-checkpoints turns off the checks. Otherwise run_checkpoints first tests Sections 3 and 8, and a failure stops the program: count_triangles_for_cathetus(12) must be $4$, computed as $(d(36)-1)/2$ by divisor_count_square, which finds $d(m^2)=\prod(2e_i+1)$ by trial division, and solve_u128 must return $12$ for four triangles and $3$ for one.

solve_u128 sets product_target to $P=2t+1$. The recursive collect_factorizations lists the multiplicative partitions of Section 5 into odd factors: it tries every odd factor from min_factor up to remaining and, for each divisor, recurses on the quotient with that divisor as the new minimum, so every partition appears exactly once, with non-decreasing factors. The first block uses all partitions of $P$, for the odd catheti; then a loop over the odd numbers $1,3,\dots,P$ calls the lambda try_odd_factorization for every divisor $g$, which sets two_exponent to $(g+1)/2$ and uses the partitions of $P/g$. Each factor $f$ becomes the exponent $(f-1)/2$, and build_number sorts the exponents from largest to smallest and multiplies $2^k$ by $3^{e_1}5^{e_2}\cdots$ from a table of the first $20$ odd primes, as in Section 6. best keeps the smallest value; to_string_u128 converts it to decimal text, which main prints.

Some candidates are enormous: the single factor $95095$ gives $3^{47547}$, a number with $22686$ digits. The C++ code uses unsigned 128-bit integers ^[9] and passes best to build_number as a cap: before every shift or multiplication, build_number and capped_pow_u128 check whether the result would exceed the cap and, if so, return the cap, which the test candidate < best rejects. So no product overflows, and a candidate that reaches the cap never replaces best. Other targets meet two limits: if no candidate is below $2^{128}-1$, the program prints $2^{128}-1$, as for $t=128$, where $P=257$ is prime and the smallest cathetus is $2^{129}$; and the parser and $2t+1$ use int without range checks, so targets from about $2^{30}$ on overflow. The empty partition of $1$ is added twice, so the candidate $2^{t+1}$ is built twice, which is harmless.

The Python version follows the same plan without a cap, because Python integers have unlimited precision; it starts from best = float('inf'), which compares correctly with every integer, and never calls its divisor_count_square. The Java version uses BigInteger, collects the partitions by backtracking on one list, repeats the empty partition like the C++ code and has an unused helper powU64. Both always solve $t=47547$ and run no checkpoints.

Complexity and Verification

The search never looks at individual catheti; its cost depends only on $P$. For $t=47547$ the loop over odd $g$ makes $47548$ passes and finds the $32$ odd divisors of $95095$; a call of collect_factorizations on a value $R$ tests the odd numbers from its minimum factor up to $R$, $220960$ trial divisions in all; and $255$ candidates are built ($256$ in C++ and Java), each a power of $2$ times at most five odd prime powers. The recursion is at most five levels deep, and every list of partitions has at most $52$ entries. C++ abandons a candidate as soon as it passes best, while Python and Java compute every candidate exactly, $3^{47547}$ included; these big-integer products take at most a few milliseconds. In tests on a desktop computer each program finished in well under a second.

The C++ checkpoints pass, and all three programs print the same number for $47547$ triangles. Further checks, not part of the published solutions: a direct search over the other cathetus $a\lt n^2/2$ agrees with $T(n)=(d(m^2)-1)/2$ for every $n\le1000$; a sieve of $T(n)$ over all $n\le10^8$ gives the first cathetus with each count, a separately written search of Sections 5 to 7 reproduces it for every count that occurs, and every other count $t\le5000$ gets a result above $10^8$; the C++ program with --target-count agrees with that search for all $2260$ positive targets $t\le5000$ whose smallest cathetus is below $2^{128}-1$; and for $t=47547$ the separate search gives the same number as the three programs.

Footnotes and References

The references below supply the background facts used above. The reduction of the count to $D(n)$, the special factor $2k-1$ of the prime $2$, the candidate search and its completeness proof are derived explicitly in this article.

Project Euler 176 — Common Cathetus Right-angled Triangles. The official statement lists the four integer-sided right-angled triangles with a cathetus 12, (9, 12, 15), (12, 16, 20), (5, 12, 13) and (12, 35, 37), and asks for the smallest integer that is a cathetus of exactly 47547 different integer-sided right-angled triangles.
Wikipedia — Pythagorean triple. A Pythagorean triple is three positive integers a, b, c with a² + b² = c², called primitive when they are coprime, and the article's proofs use the factorisation (c − a)(c + a) = b² of a difference of two squares.
Wikipedia — Fundamental theorem of arithmetic. Every integer greater than 1 is a product of primes in exactly one way, up to the order of the factors.
Wikipedia — Divisor function. σ₀(n), also written d(n) or τ(n), counts the divisors of n; for n = p₁^a₁ p₂^a₂ ⋯ it equals (a₁ + 1)(a₂ + 1)⋯, one divisor per choice of exponents 0 ≤ xᵢ ≤ aᵢ, and it is odd for squares.
OEIS A046079 — Number of Pythagorean triangles with leg n. The entry starts 0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, … and gives a(n) = (τ(n²) − 1)/2 for odd n and (τ((n/2)²) − 1)/2 for even n, the formula of Section 3, together with the product form of Section 4, whose factor for the prime 2 is 2a₀ − 1.
Wikipedia — Highly composite number. A highly composite number uses exactly the first k primes with non-increasing exponents; otherwise a smaller prime or a swap of two exponents would give a smaller number with as many divisors.
Wikipedia — Rearrangement inequality. For x₁ ≤ ⋯ ≤ xₙ and y₁ ≤ ⋯ ≤ yₙ, the sum x₁y_σ(1) + ⋯ + xₙy_σ(n) over all permutations σ is smallest when the two sequences are ordered oppositely.
Wikipedia — Bell number. Bₙ counts the partitions of a set of n elements (1, 1, 2, 5, 15, 52, 203, …) and the multiplicative partitions of a squarefree number with n prime factors; Wikipedia — Multiplicative partition defines these as unordered factorisations into integers greater than 1.
GCC manual — 128-bit Integers documents unsigned __int128; Python — numeric types states that integers have unlimited precision and that mixed-type comparisons use the exact values; Java — BigInteger provides immutable arbitrary-precision integers.

Problem 176 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    int target_count = 47547;
    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, "--target-count=", options.target_count)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.target_count >= 1;
}

u128 capped_pow_u128(const u64 base, const int exp, const u128 cap) {
    u128 result = 1;
    for (int i = 0; i < exp; ++i) {
        if (result > cap / static_cast<u128>(base)) {
            return cap;
        }
        result *= static_cast<u128>(base);
    }
    return result;
}

u64 divisor_count_square(u64 n) {
    u64 result = 1;
    int exponent = 0;
    while ((n & 1ULL) == 0ULL) {
        n >>= 1U;
        ++exponent;
    }
    if (exponent > 0) {
        result *= static_cast<u64>(2 * exponent + 1);
    }
    for (u64 p = 3; p * p <= n; p += 2) {
        if (n % p != 0) {
            continue;
        }
        exponent = 0;
        while (n % p == 0) {
            n /= p;
            ++exponent;
        }
        result *= static_cast<u64>(2 * exponent + 1);
    }
    if (n > 1) {
        result *= 3ULL;
    }
    return result;
}

u64 count_triangles_for_cathetus(const u64 n) {
    const u64 m = (n % 2ULL == 0ULL) ? (n / 2ULL) : n;
    return (divisor_count_square(m) - 1ULL) / 2ULL;
}

void collect_factorizations(int remaining, int min_factor,
                            std::vector<int>& current,
                            std::vector<std::vector<int>>& out) {
    if (remaining == 1) {
        out.push_back(current);
        return;
    }
    for (int factor = min_factor; factor <= remaining; factor += 2) {
        if (remaining % factor != 0) {
            continue;
        }
        current.push_back(factor);
        collect_factorizations(remaining / factor, factor, current, out);
        current.pop_back();
    }
}

u128 build_number(int two_exponent, std::vector<int> exponents, u128 cap) {
    static const std::vector<u64> odd_primes{
        3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL,
        37ULL, 41ULL, 43ULL, 47ULL, 53ULL, 59ULL, 61ULL, 67ULL, 71ULL, 73ULL};
    std::sort(exponents.begin(), exponents.end(), std::greater<int>());

    if (exponents.size() > odd_primes.size()) {
        return cap;
    }

    u128 value = 1;
    if (two_exponent > 0) {
        if (two_exponent >= 128) {
            return cap;
        }
        if (value > (cap >> two_exponent)) {
            return cap;
        }
        value <<= static_cast<unsigned>(two_exponent);
    }
    for (std::size_t i = 0; i < exponents.size(); ++i) {
        const u128 p = capped_pow_u128(odd_primes[i], exponents[i], cap);
        if (p == cap) {
            return cap;
        }
        if (value > cap / p) {
            return cap;
        }
        value *= p;
    }
    return value;
}

u128 solve_u128(const int target_count) {
    const int product_target = 2 * target_count + 1;
    u128 best = std::numeric_limits<u128>::max();

    auto try_odd_factorization = [&](int two_factor_odd_part) {
        if (product_target % two_factor_odd_part != 0) {
            return;
        }
        const int remaining = product_target / two_factor_odd_part;
        const int two_exponent = (two_factor_odd_part + 1) / 2;

        std::vector<std::vector<int>> factorizations;
        std::vector<int> current;
        collect_factorizations(remaining, 3, current, factorizations);
        if (remaining == 1) {
            factorizations.push_back({});
        }

        for (const auto& odd_factors : factorizations) {
            std::vector<int> odd_exponents;
            odd_exponents.reserve(odd_factors.size());
            for (int f : odd_factors) {
                odd_exponents.push_back((f - 1) / 2);
            }
            const u128 candidate = build_number(two_exponent, odd_exponents, best);
            if (candidate < best) {
                best = candidate;
            }
        }
    };

    // Odd catheti: no factor from powers of 2 in the divisor-count product.
    {
        std::vector<std::vector<int>> factorizations;
        std::vector<int> current;
        collect_factorizations(product_target, 3, current, factorizations);
        for (const auto& odd_factors : factorizations) {
            std::vector<int> odd_exponents;
            odd_exponents.reserve(odd_factors.size());
            for (int f : odd_factors) {
                odd_exponents.push_back((f - 1) / 2);
            }
            const u128 candidate = build_number(0, odd_exponents, best);
            if (candidate < best) {
                best = candidate;
            }
        }
    }

    // Even catheti: (2k-1) contributes to the divisor-count product.
    for (int factor = 1; factor <= product_target; factor += 2) {
        if (product_target % factor != 0) {
            continue;
        }
        try_odd_factorization(factor);
    }

    return best;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

bool run_checkpoints() {
    if (count_triangles_for_cathetus(12) != 4ULL) {
        std::cerr << "Checkpoint failed for cathetus 12" << '\n';
        return false;
    }
    if (to_string_u128(solve_u128(4)) != "12") {
        std::cerr << "Checkpoint failed for target-count 4" << '\n';
        return false;
    }
    if (to_string_u128(solve_u128(1)) != "3") {
        std::cerr << "Checkpoint failed for target-count 1" << '\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 << to_string_u128(solve_u128(options.target_count)) << '\n';
    return 0;
}

Python

def solve():
    TARGET = 47547

    def divisor_count_square(n):
        result = 1
        e = 0
        while n % 2 == 0:
            n //= 2
            e += 1
        if e > 0:
            result *= (2*e + 1)
        p = 3
        while p * p <= n:
            if n % p == 0:
                e = 0
                while n % p == 0:
                    n //= p
                    e += 1
                result *= (2*e + 1)
            p += 2
        if n > 1:
            result *= 3
        return result

    def collect_factorizations(remaining, min_factor):
        if remaining == 1:
            return [[]]
        result = []
        f = min_factor
        while f <= remaining:
            if remaining % f == 0:
                for sub in collect_factorizations(remaining // f, f):
                    result.append([f] + sub)
            f += 2
        return result

    ODD_PRIMES = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73]

    def build_number(two_exp, exponents):
        exponents = sorted(exponents, reverse=True)
        val = 1 << two_exp if two_exp > 0 else 1
        for i, e in enumerate(exponents):
            val *= ODD_PRIMES[i] ** e
        return val

    product_target = 2 * TARGET + 1
    best = float('inf')

    # Odd catheti
    for factors in collect_factorizations(product_target, 3):
        exps = [(f - 1) // 2 for f in factors]
        cand = build_number(0, exps)
        if cand < best:
            best = cand

    # Even catheti
    for factor in range(1, product_target + 1, 2):
        if product_target % factor != 0:
            continue
        remaining = product_target // factor
        two_exp = (factor + 1) // 2
        facs = collect_factorizations(remaining, 3)
        if remaining == 1:
            facs = [[]]
        for odd_factors in facs:
            exps = [(f - 1) // 2 for f in odd_factors]
            cand = build_number(two_exp, exps)
            if cand < best:
                best = cand

    return str(best)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;
import java.util.*;

public class Euler176 {
    static long powU64(long base, int exp) {
        long r = 1;
        while (exp-- > 0)
            r *= base;
        return r;
    }

    static void collectFactorizations(int remaining, int minFactor, List<Integer> current, List<List<Integer>> out) {
        if (remaining == 1) {
            out.add(new ArrayList<>(current));
            return;
        }
        for (int f = minFactor; f <= remaining; f += 2) {
            if (remaining % f != 0)
                continue;
            current.add(f);
            collectFactorizations(remaining / f, f, current, out);
            current.remove(current.size() - 1);
        }
    }

    static BigInteger buildNumber(int twoExp, List<Integer> exponents) {
        long[] oddPrimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73 };
        List<Integer> sorted = new ArrayList<>(exponents);
        sorted.sort(Collections.reverseOrder());
        BigInteger val = BigInteger.ONE;
        if (twoExp > 0)
            val = val.shiftLeft(twoExp);
        for (int i = 0; i < sorted.size(); i++)
            val = val.multiply(BigInteger.valueOf(oddPrimes[i]).pow(sorted.get(i)));
        return val;
    }

    public static void main(String[] args) {
        int targetCount = 47547;
        int productTarget = 2 * targetCount + 1;
        BigInteger best = null;
        // Odd catheti
        List<List<Integer>> facts = new ArrayList<>();
        collectFactorizations(productTarget, 3, new ArrayList<>(), facts);
        for (List<Integer> of : facts) {
            List<Integer> exp = new ArrayList<>();
            for (int f : of)
                exp.add((f - 1) / 2);
            BigInteger c = buildNumber(0, exp);
            if (best == null || c.compareTo(best) < 0)
                best = c;
        }
        // Even catheti
        for (int factor = 1; factor <= productTarget; factor += 2) {
            if (productTarget % factor != 0)
                continue;
            int remaining = productTarget / factor;
            int twoExp = (factor + 1) / 2;
            List<List<Integer>> f2 = new ArrayList<>();
            collectFactorizations(remaining, 3, new ArrayList<>(), f2);
            if (remaining == 1)
                f2.add(new ArrayList<>());
            for (List<Integer> of : f2) {
                List<Integer> exp = new ArrayList<>();
                for (int f : of)
                    exp.add((f - 1) / 2);
                BigInteger c = buildNumber(twoExp, exp);
                if (best == null || c.compareTo(best) < 0)
                    best = c;
            }
        }
        System.out.println(best);
    }
}