Project Euler/176

Problem Statement

Link: https://projecteuler.net/problem=176

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.

Explanation

The number of integer-sided right-angled triangles with a given leg length $ s $ is given by a formula from the Wolfram Mathworld page on Pythagorean Triples. If the prime factorization of $ s $ is $ s = 2^{a_0} p_1^{a_1} \cdots p_n^{a_n} $, then:

$ L(s) = \begin{cases} \frac{1}{2}\left[(2a_1+1)(2a_2+1)\cdots(2a_n+1) - 1\right] & \text{for } a_0 = 0 \\ \frac{1}{2}\left[(2a_0-1)(2a_1+1)(2a_2+1)\cdots(2a_n+1) - 1\right] & \text{for } a_0 \ge 1 \end{cases} $

To find the smallest $ s $ with $ L(s) = 47547 $, set $ 2L(s) + 1 = 95095 $ and factor: $ 95095 = 5 \times 7 \times 11 \times 13 \times 19 $.

Assign the largest factor to the $ 2a_0 - 1 $ term (since powers of 2 give the smallest growth for $ s $) and the remaining factors in descending order to the smallest primes. Solving gives exponents $ a_0 = 10, a_1 = 6, a_2 = 5, a_3 = 3, a_4 = 2 $, yielding:

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

Answer

96818198400000