Algorithm to determine whether a given number N can become hypotenuse of right triangle with all 3 integral sides

Question

Suppose you are given hypotenuse of a right angled triangle,then how can you determine whether there are two integral smaller sides possible with the given hypotenuse.

For example, you are given hypotenuse as 5.Then you have to determine whether you have smaller integral sides for the given right triangle.The answer will be yes because we can have smaller sides as 3 and 4,hence getting a 3-4-5 right triangle.

Similarly,for hypotenuse as 7 we can have no such right triangle.

In other words,we have to find whether a given number N can serve as hypotenuse for a right triangle with all 3 sides as integers.

I went through entire article on Pythagorean triples but still no success.I am confused what conditions to check.Please help.

Answer 1

You have for a primitive pythagorean triple:

(p^2 - q^2)^2 + (2 * p * q))^2 = (p^2 + q^2)^2 = N^2

Suppose p >= q. Then we have

N >= 2 * q^2 or q <= sqrt(N / 2)

Suppose N = 13. Then we need q <= sqrt(13 / 2) = 2.54

q = 2 => p^2 = 13 - 4 = 9, which is a square.

Hence you can have a small loop of numbers 'i' from 1..sqrt(N/2) and check if N - (i^2) is a square.

This will be O(sqrt(N)) for a member of a primitive pythagorean tuple.

Sample code in C/C++:

#include <stdio.h>
#include <math.h>

void CheckTuple(int n)
{
    int k = sqrt(n/2.0);

    for (int i = 1; i <= k; i++) {
        int tmp = sqrt((double)(n - i * i));
        if ((tmp * tmp) == (n - i * i)) {
            printf("%d^2 + %d^2 = %d^2\n", (tmp*tmp - i*i), 2 * tmp * i, n);
            return;
        }
    }
    printf("%d is not part of a tuple\n", n);
    return;
}


int main(int argc, char *argv[])
{

    CheckTuple(5);
    CheckTuple(6);
    CheckTuple(13);
    CheckTuple(10);
    CheckTuple(25);

    return 0;
}

Output:

3^2 + 4^2 = 5^2
6 is not part of a tuple
5^2 + 12^2 = 13^2
8^2 + 6^2 = 10^2
7^2 + 24^2 = 25^2