Perl Weekly Challenge 125: Pythagorean Triples

Input: $N = 5
Output: (3, 4, 5)
        (5, 12, 13)

Input: $N = 13
Output: (5, 12, 13)
        (13, 84, 85)

Input: $N = 1
Output: -1

We will resort to doing a brute force search. We will consider two cases: first the case where the given number (\(n\)) isn't the hypotenuse, followed by the case where \(n\) is the hypotenuse. One or both cases may result in solutions. (There will be solutions if and only if \(n\) exceeds 2).

In this case, \(n\) is one of the shorter sides. W.l.o.g, assume \(n\) is \(a\). So, we now must find \(b\) and \(c\) such that \(n^2 + b^2 = c^2\). We do this by trying increasing values of \(c\), and checking whether \(b = \sqrt{c^2 - n^2}\) is a perfect square.

Since the \(c\) is the larger of the numbers, the minimum value of \(c\) to consider is \(n + 1\). Note that there are Pythagorian triples where \(c\) is one more than other sides. \((3, 4, 5)\) and \((5, 12, 13)\) are two examples.

We can stop our search if \(b > c - 1\). Then \[ \begin{array}{lc} b = \sqrt{c^2 - n^2} > c - 1 && \implies \\ b^2 = c^2 - n^2 > (c - 1)^2 && \implies \\ c^2 - (c - 1)^2 > n^2 && \implies \\ c^2 - c^2 + 2 \cdot c - 1 = 2 \cdot c - 1 > n^2 && \end{array} \]

Now, for each \(c\) within those limits, we calculate \(b^2 = c^2 - n^2\), and \(b = \lfloor 0.4 + \sqrt{b^2} \rfloor\). Now, \(b^2\) is a perfect square, if and only if \(b^2 = b \cdot b\). And if \(b^2\) is a perfect square, then \((n, b, c)\) is a Pythagorian Triple.

Then \(n = c\). W.l.o.g. assume \(a < b\) (they cannot equal). Since there are no Pythagorian Triples were one of the sides has length \(1\) or \(2\), we have \(3 \leq a\). Also, since \(a < b\), we have:

\[ \begin{array}{lc} a^2 + b^2 = n^2 && \implies \\ 2 \cdot b^2 < n^2 && \implies \\ b^2 < \frac{n^2}{2} && \implies \\ a < b < \sqrt{\frac{n^2}{2}} = \frac{n}{\sqrt{2}} && \implies \\ a \leq \left\lfloor \frac{n}{\sqrt{2}} \right\rfloor && \end{array} \]

So, for each \(3 \leq a \left\lfloor \frac{n}{\sqrt{2}} \right\rfloor\) we calculate \(b^2 = n^2 - a^2\), and check whether this is a perfect square in the same was as above. In such a case, \(a, b, n\) is a Pythagorian Triple.

First a function which calculates \(\left\lfloor 0.4 + \sqrt{b^2} \right\rfloor\):

sub introot ($square) {
    int (.4 + sqrt ($square));
}

Checking whether $n can be part of a Pythagorian Triple:

say (-1) if $n <= 2;

The case where $n is not the hypotenuse:

my $n_sq = $n * $n;

my $c    = $n + 1;
my $c_sq = $n_sq + 2 * $n + 1;
while (2 * $c - 1 <= $n_sq) {
    my $b_sq = $c_sq - $n_sq;
    my $b    = introot ($b_sq);

    say "$n $b $c" if $b_sq == $b * $b;
    $c_sq += 2 * $c ++ + 1;  # (c + 1)^2 == c^2 + 2 * c + 1
}

Note that if \(c = n + 1\), then \(c^2 = (n + 1)^2 = n^2 + 2 \cdot n + 1\). In the same way, \((c + 1)^2 = c^2 + 2 \cdot c + 1\).

Now, the case where $n is the hypotenuse:

my $max_a = int ($n / sqrt (2));
for (my $a = 3; $a <= $max_a; $a ++) {
    my $b_sq = $n_sq - $a * $a;
    my $b    = introot ($b_sq);
    say "$a $b $n" if $b_sq == $b * $b;
}

Find the full program on GitHub.

We also have very similar solutions in AWK, C, Go, Java, Lua, Node.js, Pascal, Python, R, Ruby, and Tcl.