Given hypotenuse, find the other two sides.

Question

Note that we are only interested in integral pythagorean triplets, we are given the hypotenuse $c$, how can I efficiently find the other two sides of the right angled triangle. I need something better than the bruteforce approach of iterating over all lengths $a$ below $c$, and checking perfect square for $b = \sqrt{c^2-a^2}$.
For multiple solutions, I need one with the smallest $a$ possible.

Answer 1

You cannot, because there exist infinitely many right angled triangles with the same hypotenuse length.

For example, if the length of the hypotenuse is $1$, then for every $x\in(0,1)$, $(x, \sqrt{1-x^2})$ are possible lengths of the other two sides.

Answer 2

How about using the standard formula for generating Pythagorean triples? Solve $c = m^2 + n^2$ for $m$ and $n$. Then you have $a = m^2 - n^2$ and $b = 2mn$. (If $m$ and $n$ are co-prime and of opposite parity, the triple is primitive, otherwise not.) This requires less brute force than the approach you wanted to avoid, since $c < c^2$.

Answer 3

One could further sieve the search by casting $c=m^2+n^2$ over a modular base, for example base two as say $2z=4(x^2+2x+1)+4y^2$ which reduces to $z=2(x^2+y^2)+2(x+1)$. Clearly $z$ is also congruent to zero modulo two, so immediately here you get another four fold reduction in the bound to $z_1=x^2+y^2+x+1$. Since $c$ is known the more general sieve $az+r_z=(ax+r_x)^2+(ay+r_y)^2$ would allow brute force search reduction once you have solved $r_z\equiv r_x^2+r_y^2$. This may or may not be a good step depending on other factors like the totient of the base $a$. We could also look at $c+b=m^2+n^2+2mn=(m+n)^2$ which of course says that $b$ is $c$ less than a perfect square. So we would be checking perfect squares greater than $c$. There are many directions to go. I am not aware of a closed form solution to the number of pythagorean triples associated with a given hypotenuse however. I'm not sure there is one.