How to resolve the algorithm Pythagorean triples step by step in the Raku programming language

Published on 12 May 2024 09:40 PM
#Raku

How to resolve the algorithm Pythagorean triples step by step in the Raku programming language

Table of Contents

Problem Statement

A Pythagorean triple is defined as three positive integers

( a , b , c )

{\displaystyle (a,b,c)}

where

a < b < c

{\displaystyle a<b<c}

, and

a

2

b

2

=

c

2

.

{\displaystyle a^{2}+b^{2}=c^{2}.}

They are called primitive triples if

a , b , c

{\displaystyle a,b,c}

are co-prime, that is, if their pairwise greatest common divisors

g c d

( a , b )

g c d

( a , c )

g c d

( b , c )

1

{\displaystyle {\rm {gcd}}(a,b)={\rm {gcd}}(a,c)={\rm {gcd}}(b,c)=1}

. Because of their relationship through the Pythagorean theorem, a, b, and c are co-prime if a and b are co-prime (

g c d

( a , b )

1

{\displaystyle {\rm {gcd}}(a,b)=1}

).   Each triple forms the length of the sides of a right triangle, whose perimeter is

P

a + b + c

{\displaystyle P=a+b+c}

.

The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.

Deal with large values.   Can your program handle a maximum perimeter of 1,000,000?   What about 10,000,000?   100,000,000? Note: the extra credit is not for you to demonstrate how fast your language is compared to others;   you need a proper algorithm to solve them in a timely manner.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pythagorean triples step by step in the Raku programming language

Source code in the raku programming language

constant limit = 100;

for [X] [^limit] xx 3 -> (\a, \b, \c) {
    say [a, b, c] if a < b < c and a + b + c <= limit and a*b + b*b == c*c
}


my $limit = 10000;
my atomicint $i = 0;
my @triples[$limit/2];
(3 .. $limit/2).race.map: -> $c {
   for 1 .. $c -> $a {
       my $b = ($c * $c - $a * $a).sqrt;
       last if $c + $a + $b > $limit;
       last if $a > $b;
       @triples[$i⚛++] = ([gcd] $c, $a, $b) > 1 ?? 0 !! 1 if $b == $b.Int;
   }
}

say my $result = "There are {+@triples.grep:{$_ !eqv Any}} Pythagorean Triples with a perimeter <= $limit,"
 ~"\nof which {[+] @triples.grep: so *} are primitive.";


sub triples($limit) {
    my $primitive = 0;
    my $civilized = 0;
 
    sub oyako($a, $b, $c) {
        my $perim = $a + $b + $c;
        return if $perim > $limit;
        ++$primitive; $civilized += $limit div $perim;
        oyako( $a - 2*$b + 2*$c,  2*$a - $b + 2*$c,  2*$a - 2*$b + 3*$c);
        oyako( $a + 2*$b + 2*$c,  2*$a + $b + 2*$c,  2*$a + 2*$b + 3*$c);
        oyako(-$a + 2*$b + 2*$c, -2*$a + $b + 2*$c, -2*$a + 2*$b + 3*$c);
    }
 
    oyako(3,4,5);
    "$limit => ($primitive $civilized)";
}
 
for 10,100,1000 ... * -> $limit {
    say triples $limit;
}


constant @coeff = [[+1, -2, +2], [+2, -1, +2], [+2, -2, +3]],
                  [[+1, +2, +2], [+2, +1, +2], [+2, +2, +3]],
                  [[-1, +2, +2], [-2, +1, +2], [-2, +2, +3]];

sub triples($limit) {

    sub oyako(@trippy) {
        my $perim = [+] @trippy;
        return if $perim > $limit;
        take (1 + ($limit div $perim)i);
        for @coeff -> @nine {
            oyako (map -> @three { [+] @three »*« @trippy }, @nine);
        }
        return;
    }

    my $complex = 0i + [+] gather oyako([3,4,5]);
    "$limit => ({$complex.re, $complex.im})";
}

for 10, 100, 1000, 10000 -> $limit {
    say triples $limit;
}

You may also check:How to resolve the algorithm Events step by step in the Racket programming language
You may also check:How to resolve the algorithm Guess the number step by step in the GML programming language
You may also check:How to resolve the algorithm Gapful numbers step by step in the Crystal programming language
You may also check:How to resolve the algorithm Sorting algorithms/Radix sort step by step in the Scala programming language
You may also check:How to resolve the algorithm Substitution cipher step by step in the Ring programming language