# Perl Weekly Challenge 125: Pythagorean Triples

by Abigail ## Challenge

You are given a positive integer $N. Write a script to print all Pythagorean Triples containing $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.

### Example

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  ## Solution 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). #### Case 1: $$n$$ is not the hypotenuse 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. #### Case 2: $$n$$ is the hypotenuse 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. ### Perl 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.

### Other Languages

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

## Speed comparison

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.