TL;DR

Here we are with TASK #1 from The Weekly Challenge #125. Enjoy!

# The 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Â²+bÂ² = cÂ².

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  # The questions Well, I really donâ€™t have questions for this one. I would argue that printing -1 troubles me a bit, but Iâ€™ll stick to the requirement. Oh, by the wayâ€¦ Iâ€™ll assume that any ordering will do! # The solution This took me a good deal of time. Thereâ€™s a few ways to generate Pythagorean triples. One of the most famous is Euclidâ€™s formula, which unfortunately generates a lot, but not all of them. And weâ€™re going to need all of them here, potentially. Had I immediately read through Formulas for generating Pythagorean triples, I would not have wasted my time with an article that eventually provedâ€¦ unuseful. I would be tempted to post it here just to have a different pair of eyes confirming its lack of usefulness, but Iâ€™m inclined to believe that I would waste someone elseâ€™s time too. Ring me a bell in case. I eventually landed on two possible options: • use an algorithm to find all primitive triples, i.e. triples where the three sides are mutually prime, and use that to find them all, OR • use Dicksonâ€™s method, which (as I read) is guaranteed to generate them all. I eventually landed on the latter, so here we go with Raku: #!/usr/bin/env raku use v6; sub pythagorean-triples (Int:D$N where * > 0) {

# this finds all possible (distinct) ways of expressing $n as a # product of two positive integers. The first item is by definition # lower than, or equal to, the second so that we know that only # distinct pairs are considered; this also means that the first # element cannot be greater than sqrt($n)
sub factor-in-pairs ($n) { (1 .. sqrt($n))            # first element 1 .. sqrt($n) .grep({$n %% $_}) # make sure first element divides$n
.map({($_,$n / $_)}); # take it and its counterpart } # I know that gather/take is slow... but it's too cool gather { # https://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples#Dickson's_method # parameter$r spans positive even integers
R: # this marks the outer loop, for exiting lazy iteration
for 2, 4, 6 ... Inf -> $r { for factor-in-pairs($rÂ²/2) -> ($s,$t) {
my @triple = ($r +$s, $r +$t, $r +$s + $t); # if the very first triple's first element is over$N,
# our iteration is over because any element will be
# greater than $N from now on last R if$s == 1 && $N < @triple[0]; # only take the triple if it contains our target$N
take @triple if $N == @triple.any; } } } } sub MAIN (Int:D$N = 5) {
my @triples = pythagorean-triples($N); if @triples { put '(' ~$_.join(', ') ~ ')' for @triples }
else        { put -1 }
}


I hope the comments are enough to understand whatâ€™s going on.

Iâ€™ve been told multiple times that gather/take is quite inefficient but I still love the idea and I think itâ€™s anyway perfect here, where I donâ€™t expect too many results to come out (as I understand it, the performance penalty is linear with the number of takes).

One note about the take lineâ€™s condition, that was initially written as:

take @triple if $N ~~ @triple;  I thought the smart matching would do the right thing here, but it didnâ€™t, so I reverted to a more explicit Junction $N == @triple.any. Go figure.

The corresponding code in Perl is pretty much a straight translation, taking into account that the two languages have a few differences:

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use List::Util 'first';

sub factor_in_pairs ($n) { map { [$_, $n /$_] } grep { !($n %$_) } 1 .. sqrt($n) } sub pythagorean_triples ($N) {
my @retval;
my $r = 0; R: while ('necessary') {$r += 2;
for my $pair (factor_in_pairs($r * $r / 2)) { my ($s, $t) =$pair->@*;
my @triple = ($r +$s, $r +$t, $r +$s + $t); last R if$s == 1 && $N <$triple[0];
push @retval, \@triple if first { $N ==$_ } @triple;
}
}
return @retval;
}

my $N = shift // 5; my @triples = pythagorean_triples($N);
if (@triples) { say '(' . join(', ', \$_->@*) . ')' for @triples }
else          { say -1 }


Wellâ€¦ I guess itâ€™s enough for this post, have fun and stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!