You are given a positive integer

`$N`

.Write a script to print all

Pythagorean Triplescontaining`$N`

as a member. Print -1 if it can’t be a member of any.Triples with the same set of elements are considered the same, i.e. if your script has already printed

`(3, 4, 5)`

,`(4, 3, 5)`

should not be printed.The famous Pythagorean theorem states that in a right angle triangle, the length of the two shorter sides and the length of the longest side are related by \(a^2 + b^2 = c^2\).

A Pythagorean triple refers to the triple of three integers whose lengths can compose a right-angled triangle.

```
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.

We compared the running times of the various implementations. We did this by giving each program the number 1 till 1000 as input. The table below gives the results of the running times:

Language | Time |
---|---|

Pascal | 0m 00.78s |

Go | 0m 01.02s |

Node.js | 0m 01.55s |

Java | 0m 02.19s |

C | 0m 02.32s |

Lua | 0m 29.02s |

Ruby | 0m 55.85s |

Perl | 1m 04.15s |

AWK | 1m 11.33s |

R | 1m 23.77s |

Python | 2m 04.96s |

Tcl | 23m 42.27s |

As we can see, compiled languages are fast (with Pascal the surprising winner), while "scripting" languages like Ruby and Perl are a lot slower. Python is a about twice as slow as Ruby or Perl. Lua is halfway the fast and slow groups.

Tcl is just way, way slower than anything else.