Solution

Answer: 96818198400000

Let $N(n)$ denote the number of integer-sided right triangles having one cathetus equal to $n$.

We are asked for the smallest $n$ such that

$$N(n)=47547.$$

The key is to derive a divisor-function formula for $N(n)$.

1. Mathematical analysis

Suppose a right triangle has legs $n,b$ and hypotenuse $c$. Then

$$n^2+b^2=c^2.$$

Rearrange:

$$c^2-b^2=n^2$$

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

Define

$$u=c-b,\qquad v=c+b.$$

Then

$$uv=n^2,$$

and

$$c=\frac{u+v}{2},\qquad b=\frac{v-u}{2}.$$

Thus $u,v$ must have the same parity.

Odd case

If $n$ is odd, then $n^2$ is odd, so every divisor pair $(u,v)$ is odd automatically.

Each factorization

$$uv=n^2,\quad u<v$$

gives one triangle.

Hence:

$$N(n)=\frac{d(n^2)-1}{2},$$

where $d(m)$ is the number of divisors of $m$.

Even case

Write

$$n=2^a m,$$

with $m$ odd.

A standard derivation gives:

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

Equivalently, if

$$n=2^{a_0}\prod p_i^{a_i},$$

then

$$N(n)=\frac{\left(2a_0-1\right)\prod (2a_i+1)-1}{2}.$$

This is the crucial formula.

2. Transforming the condition

We need

$$N(n)=47547.$$

Therefore

$$\left(2a_0-1\right)\prod (2a_i+1) = 2\cdot 47547+1.$$

Compute:

$$2\cdot47547+1=95095.$$

Factor:

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

So we need

$$(2a_0-1)\prod (2a_i+1)=95095.$$

To minimize $n$, we use the standard optimization principle:

larger exponents go on smaller primes,
and exponents are determined from factors via

$$2a_i+1=f_i.$$

Thus

$$a_i=\frac{f_i-1}{2}.$$

We should assign the largest $f_i$ to the smallest prime base.

The factors are:

$$19,\ 13,\ 11,\ 7,\ 5.$$

Corresponding exponents:

$$9,\ 6,\ 5,\ 3,\ 2.$$

Now we must decide which factor corresponds to the power of $2$.

For the $2$-part we use

$$2a_0-1=f \quad\Rightarrow\quad a_0=\frac{f+1}{2}.$$

Trying the largest factor $19$:

$$a_0=10.$$

Then the remaining exponents are

$$6,5,3,2$$

on primes $3,5,7,11$.

Hence

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

This is minimal by the monotonicity argument (largest exponents on smallest primes).

3. Python implementation

from math import prod

# Target number of triangles
target = 47547

# We need:
# (2*a0 - 1) * Π(2*ai + 1) = 2*target + 1
M = 2 * target + 1

# Prime factorization of 95095:
factors = [19, 13, 11, 7, 5]

# Assign the largest factor to the power of 2:
# 2*a0 - 1 = 19  => a0 = 10
a0 = (19 + 1) // 2

# Remaining exponents:
# ai = (factor - 1)//2
odd_exponents = [
    (13 - 1) // 2,  # 6
    (11 - 1) // 2,  # 5
    (7  - 1) // 2,  # 3
    (5  - 1) // 2   # 2
]

# Corresponding odd primes
primes = [3, 5, 7, 11]

# Construct n
n = 2**a0
for p, e in zip(primes, odd_exponents):
    n *= p**e

print(n)

4. Code walkthrough

Step 1

target = 47547
M = 2 * target + 1

We convert the triangle count condition into the multiplicative condition:

$$(2a_0-1)\prod(2a_i+1)=95095.$$

Step 2

factors = [19, 13, 11, 7, 5]

These are the prime factors of $95095$.

Step 3

a0 = (19 + 1) // 2

Using

$$2a_0-1=19,$$

$$a_0=10.$$

Step 4

odd_exponents = [6,5,3,2]

Derived from

$$a_i=\frac{f_i-1}{2}.$$

Step 5

n = 2**a0
for p, e in zip(primes, odd_exponents):
    n *= p**e

Builds

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

5. Small-example verification

For $n=12$:

$$12 = 2^2\cdot 3.$$

Formula gives:

$$N(12) = \frac{(2\cdot2-1)(2\cdot1+1)-1}{2} = \frac{3\cdot3-1}{2} = 4.$$

Exactly matching the problem statement.

6. Final computation

Evaluate:

$$2^{10}3^6 5^5 7^3 11^2.$$

Compute stepwise:

$$2^{10}=1024$$

$$3^6=729$$

$$5^5=3125$$

$$7^3=343$$

$$11^2=121$$

Multiplying gives:

$$96818198400000.$$

The magnitude is reasonable: achieving $47547$ representations requires many divisor factors, hence a highly composite structured number.

Answer: 96818198400000

Project Euler Problem 176