Detailed mathematical approach

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\).

The Odd/Even Split for the Shared Cathetus

If \(n\) is odd, then \(n^2\) is odd, so every divisor pair of \(n^2\) is automatically odd-odd and therefore admissible. Because \(n^2\) is a square, it has an odd number of divisors, and one of them is the middle divisor \(\sqrt{n^2}=n\). Hence

$T(n)=\frac{d(n^2)-1}{2}\qquad\text{when \(n\) is odd}.$

If \(n\) is even, then \(u\) and \(v\) cannot both be odd because their product is even, so they must both be even. Write

$u=2r,\qquad v=2s.$

Then

$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$

and every factor pair \(r<s\) of \(\left(\frac{n}{2}\right)^2\) produces one triangle. Therefore

$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{when \(n\) is even}.$

It is convenient to introduce a reduced parameter \(m\): take \(m=n\) for odd \(n\), and \(m=n/2\) for even \(n\). Then both cases collapse to

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

Turning the Target Count into a Divisor Equation

For the target value \(T(n)=47547\), the previous formula becomes

$d(m^2)=2\cdot 47547+1=95095.$

If

$m=\prod_i p_i^{e_i},$

then

$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$

So the inverse problem is: write \(95095\) as a product of odd integers, and interpret each factor \(f\) as an exponent contribution

$e=\frac{f-1}{2}.$

The implementations do not guess a single factorization. They enumerate every odd multiplicative partition of \(95095\) in nondecreasing order, so every valid exponent multiset is considered exactly once.

For this particular target,

$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$

but grouping some of these prime factors together is also allowed, because a term such as \(35\) would simply mean an exponent \((35-1)/2=17\) on one prime of \(m\).

Why the Smallest Cathetus Uses Descending Exponents on Ascending Primes

Once a multiset of exponents is fixed, the smallest corresponding integer is obtained by assigning the largest exponent to the smallest available prime, the next-largest exponent to the next-smallest prime, and so on. The reason is the swap inequality

$p^a q^b \le p^b q^a\qquad\text{for }p<q\text{ and }a\ge b.$

That is why the implementations sort the exponent list in descending order before building a candidate.

The even case needs one extra remark. If \(n\) is even, then \(n=2m\). Suppose the exponent of \(2\) inside \(m\) is \(a\). Its contribution to \(d(m^2)\) is

$2a+1.$

The search therefore reserves one odd factor of \(95095\) for the power of \(2\), translates it to \(a=(f-1)/2\), and then the final cathetus receives the power

$2^{a+1},$

because \(n=2m\). All remaining odd factors are converted into exponents on \(3,5,7,\dots\).

Worked Example: Why the Smallest Solution for \(T(n)=4\) Is \(12\)

This smaller target is useful because it is explicitly checked by the implementations. If \(T(n)=4\), then

$d(m^2)=2\cdot 4+1=9.$

For an odd cathetus, the only odd-factor partition is \(9\), which gives exponent \(4\) on one odd prime and leads to the candidate \(n=3^4=81\).

For an even cathetus, we can reserve a factor \(3\) for the power of \(2\). Then

$2a+1=3\qquad\Longrightarrow\qquad a=1,$

and the remaining factor \(3\) gives exponent \(1\) on the odd prime \(3\). So

$m=2^1\cdot 3^1=6,\qquad n=2m=12.$

Indeed, \(\left(\frac{12}{2}\right)^2=36\) has the factor pairs

$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$

which correspond to the four triangles

$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$

The full target works the same way. After exploring every admissible odd multiplicative partition of \(95095\), the minimum cathetus is

$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. First they convert the target count into

$2T+1=95095,$

because that is the required value of \(d(m^2)\).

Enumerating Admissible Exponent Patterns

The main search is a recursion over odd multiplicative partitions. It generates factorizations in nondecreasing order, which prevents duplicate exponent multisets from appearing in different orders. One pass handles odd catheti, where the entire product \(95095\) is assigned to odd primes. A second pass handles even catheti by choosing one odd divisor to represent the contribution \(2a+1\) of the prime \(2\) inside \(m\), and then factorizing the remaining quotient among odd primes.

Each odd factor \(f\) becomes an exponent \((f-1)/2\). The resulting exponent list is sorted from large to small and attached to the primes \(3,5,7,\dots\), while the even branch contributes a leading power of \(2^{a+1}\). The implementations keep the smallest candidate seen so far.

Integer Construction and Validation

The candidate integer can be very large, so the implementations build it with arbitrary-precision arithmetic in Python and Java, and with carefully capped 128-bit arithmetic in C++. The C++ version also includes small checkpoint tests: it verifies that a cathetus of \(12\) produces \(4\) triangles, that target count \(4\) has smallest solution \(12\), and that target count \(1\) has smallest solution \(3\).

Although the final solver never searches directly over catheti, the implementations also contain the direct divisor-count formula for \(T(n)\). That routine is useful for the checkpoints and makes the link between the derivation and the computed answer explicit.

Complexity Analysis

Let \(P=2T+1\). The hard part is not scanning values of \(n\); it is enumerating all odd multiplicative partitions of \(P\) and, in the even branch, doing the same for quotients \(P/f\) where \(f\) is an odd divisor of \(P\). If \(\Pi(P)\) denotes the number of such partitions explored, the search cost is essentially proportional to \(\Pi(P)\), with only a short exponent list to sort for each candidate.

For the actual problem \(P=95095\), this search space is tiny. Memory usage is \(O(k)\) for a recursion stack and a current factor list of length \(k\), so the practical footprint is minimal. The algorithm is fast because it replaces an impossible brute-force search over catheti by a very small recursive search over divisor patterns.

Footnotes and References

1. Project Euler problem page: Project Euler 176
2. Pythagorean triple: Wikipedia - Pythagorean triple
3. Difference of two squares: Wikipedia - Difference of two squares
4. Divisor function: Wikipedia - Divisor function
5. Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic