A Pythagorean triplet is a set of three natural numbers, \(a \lt b \lt c\), for which, \[a^2 + b^2 = c^2.\]
For example, \(3^2 + 4^2 = 9 + 16 = 25 = 5^2\).
There exists exactly one Pythagorean triplet for which \(a + b + c = 1000\).
Find the product \(abc\).
This one can be solved without any code, through the use of Euclid's formula for generating Pythagorean triples. To quote the linked Wikipedia article: Any triple \(a, b, c\) can be generated uniquely by the formulae
\[\begin{aligned} a &= k \cdot \min \{m^2 - n^2, 2 m n\} \\ b &= k \cdot \max \{m^2 - n^2, 2 m n\} \\ c &= k \cdot (m^2 + n^2) \end{aligned}\]where \(m\), \(n\), and \(k\) are positive integers with \(m > n\), and with \(m\) and \(n\) coprime and not both odd.
We are given that \(a + b + c = 1000\). Substituting in the formulae, this equality becomes \(k(2m^2 + 2mn) = 1000\), which factors out to \(km(m+n)=500\).
This means that \(m\) divides \(500 = 2^2 5^3\), and because it's necessarily smaller than \(m + n\), it holds that \(m < \sqrt{500} < 23\). The only factors of 500 that are below 23 are 1, 2, 4, 5, 10, and 20, so we have a limited candidate pool to check.
We immediately rule out \(m=1\), because \(0 < n < m\). Because \(m\) and \(n\) must be coprime, \(m\) and \(m + n\) must be coprime. Because of this and the fact that \(m\) and \(n\) both divide \(2^2 5^3\), it follows that either \(m\) is a power of 2 and \(m+n\) is a power of 5, or vice versa. The remaining candidates for \(m\) are thus 2, 4, and 5.
Suppose \(m=5\). Then the only value of \(n\) less than \(m\) which would make \(m + n\) a power of 2 is 3; however, this would mean \(m + n = 8\) divides 500. We thus rule out this case. Now suppose \(m = 2\); then \(n\) can only be \(1\), but now \(m + n = 3\), which doesn't divide 500 either. Only one case remains, so we conclude \(m = 4\), and it immediately follows that \(n = 1\) and \(k = 25\).
Using these values of \(m\), \(n\), and \(k\) in Euclid's formulae, we get \((a, b, c) = (200, 375, 425)\). Their product is \(31875000\).