Merge pull request #6246 from PerlMonk-Athanasius/branch-for-challenge-168

Perl & Raku solutions to Tasks 1 & 2  for Week 168

4 files changed, 542 insertions, 0 deletions

diff --git a/challenge-168/athanasius/perl/ch-1.pl b/challenge-168/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..52cd051ca2
--- /dev/null
+++ b/challenge-168/athanasius/perl/ch-1.pl
@@ -0,0 +1,98 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 168
+=========================
+
+TASK #1
+-------
+*Perrin Prime*
+
+Submitted by: Roger Bell_West
+
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is
+the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+        A Perrin prime is a number in the Perrin sequence which is also a prime
+        number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193,
+         792606555396977]
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+Generate successive terms in the Perrin sequence using the recurrence relation
+p(n) = p(n-2) + p(n-3).
+
+Test whether each new term is a prime number using the is_prime() function from
+the CPAN module Math::Prime::Util (aka ntheory).
+
+Output Perrin primes as they are found, until the output count reaches 13.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Math::Prime::Util qw( is_prime );
+
+const my @INIT_TRIPLET => (3, 0, 2);
+const my $TARGET       => 13;
+const my $USAGE        => "Usage:\n  perl $0\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    $| = 1;
+    print "\nChallenge 168, Task #1: Perrin Prime (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+    my $args = scalar @ARGV;
+       $args == 0 or die 'ERROR: Expected 0 command line arguments, found ' .
+                         "$args\n$USAGE";
+
+    my @triplet = @INIT_TRIPLET;
+    my %primes  = map { $_ => 1 } grep { is_prime $_ } @triplet;
+
+    printf "f(%d) =\n  %s", $TARGET,
+                            join ', ', sort { $a <=> $b } keys %primes;
+
+    while (scalar keys %primes < $TARGET)
+    {
+        my $n = $triplet[ 0 ] + $triplet[ 1 ];
+
+        shift @triplet;
+        push  @triplet, $n;
+
+        if (is_prime $n)
+        {
+            ++$primes{ $n };
+
+            print ", $n" if $primes{ $n } == 1;
+        }
+    }
+
+    print "\n";
+}
+
+###############################################################################
diff --git a/challenge-168/athanasius/perl/ch-2.pl b/challenge-168/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..dc4b283e2f
--- /dev/null
+++ b/challenge-168/athanasius/perl/ch-2.pl
@@ -0,0 +1,165 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 168
+=========================
+
+TASK #2
+-------
+*Home Prime*
+
+Submitted by: Mohammad S Anwar
+
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+In number theory, the home prime HP(n) of an integer n greater than 1 is the
+prime number obtained by repeatedly factoring the increasing concatenation of
+prime factors including repetitions.
+
+Further information can be found on [ https://en.wikipedia.org/wiki/Home_prime
+|Wikipedia] and [ https://oeis.org/A037274 |OEIS].
+
+Example
+
+As given in the Wikipedia page,
+
+  HP(10) = 773, as
+   10 factors as 2×5 yielding HP10(1)                                =  25,
+   25 factors as 5×5 yielding HP10(2) = HP25(1)                      =  55,
+   55          = 5×11 implies HP10(3) = HP25(2) = HP55(1)            = 511, and
+  511          = 7×73 gives   HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773,
+                                                                a prime number.
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Interface
+---------
+If the constant $VERBOSE is set to a true value (the default), all the steps in
+the calculation of a home prime are given as they are performed. For example,
+for input 10 the trajectory (set of steps) is:
+
+    Trajectory: 10 -> 2|5 -> 5|5 -> 5|11 -> 7|73
+
+which shows that 10 has prime factors 2 and 5; 25 has prime factors 5 and 5; 55
+has prime factors 5 and 11; and 511 has prime factors 7 and 73; producing 773,
+which is prime.
+
+If the constant $TIMER is set to a true value (it is false by default), the
+time, in seconds, required to find the requested home prime is also displayed.
+
+Implementation
+--------------
+Factorization and primality testing are performed by the CPAN module Math::
+Prime::Util::GMP, which uses the GNU Multiple Precision Arithmetic Library
+(GMP). GMP employs "[h]ighly optimized assembly language code for the most
+important inner loops, specialized for different processors." [1] This results
+in very efficient (and therefore very fast) processing for large numbers.
+
+Performance
+-----------
+HP(2) to HP(48) are each calculated in 0.02 seconds or less. (Note: the value
+of HP(49) = HP(77) is not currently known.)
+
+Reference
+---------
+[1] "GNU Multiple Precision Arithmetic Library", Wikipedia,
+     https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Math::Prime::Util::GMP qw( factor is_prime );
+use Regexp::Common;
+
+use constant TIMER => 0;
+
+const my $VERBOSE  => 1;
+const my $USAGE    =>
+"Usage:
+  perl $0 <n>
+
+    <n>    An integer greater than 1\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    $| = 1;
+    print "\nChallenge 168, Task #2: Home Prime (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+    use if TIMER, 'Time::HiRes' => qw( gettimeofday tv_interval );
+
+    my $t0  = [gettimeofday]    if TIMER;
+    my $n   = parse_command_line();
+    my $hp  = $n;
+
+    unless (is_prime $hp)
+    {
+        print "Trajectory: $n"  if $VERBOSE;
+
+        until (is_prime $hp)
+        {
+            my @prime_factors = factor $hp;
+
+               $hp     = join '',  @prime_factors;
+            my $hp_str = join '|', @prime_factors;
+
+            print " -> $hp_str" if $VERBOSE;
+        }
+
+        print "\n\n"            if $VERBOSE;
+    }
+
+    print "HP($n) = $hp\n";
+
+    my $t   = tv_interval($t0)  if TIMER;
+    print  "\n$t seconds\n"     if TIMER;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+    my $args = scalar @ARGV;
+       $args == 1 or error( "Expected 1 command line argument, found $args" );
+
+    my $n = $ARGV[ 0 ];
+
+    $n =~ / ^ $RE{num}{int} $ /x
+                  or error( qq["$n" is not a valid integer] );
+
+    $n > 1        or error( qq["$n" is not greater than one] );
+
+    return $n;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+    my ($message) = @_;
+
+    die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-168/athanasius/raku/ch-1.raku b/challenge-168/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..0ac6070758
--- /dev/null
+++ b/challenge-168/athanasius/raku/ch-1.raku
@@ -0,0 +1,97 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 168
+=========================
+
+TASK #1
+-------
+*Perrin Prime*
+
+Submitted by: Roger Bell_West
+
+The Perrin sequence is defined to start with [3, 0, 2]; after that, term N is
+the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ….)
+
+        A Perrin prime is a number in the Perrin sequence which is also a prime
+        number.
+
+Calculate the first 13 Perrin Primes.
+
+f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193,
+         792606555396977]
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+Generate successive terms in the Perrin sequence using the recurrence relation
+p(n) = p(n-2) + p(n-3).
+
+Test whether each new term is a prime number using Raku's in-build is-prime
+method.
+
+Output Perrin primes as they are found, until the output count reaches 13.
+
+=end comment
+#==============================================================================
+
+my      constant @INIT-TRIPLET = 3, 0, 2;
+my UInt constant $TARGET       = 13;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    "\nChallenge 168, Task #1: Perrin Prime (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN()
+#==============================================================================
+{
+    my UInt @triplet      = @INIT-TRIPLET;
+    my UInt %primes{UInt} = @triplet.grep( *.is-prime ).map: { $_ => 1 };
+
+    "f(%d) =\n  %s".printf: $TARGET, %primes.keys.sort.join: ', ';
+
+    while %primes.keys.elems < $TARGET
+    {
+        my UInt $n = [+] @triplet[ 0, 1 ];
+
+        @triplet.shift;
+        @triplet.push: $n;
+
+        if $n.is-prime
+        {
+            ++%primes{ $n };
+
+            ", $n".print if %primes{ $n } == 1;
+        }
+    }
+
+    put();
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+    my Str $usage = $*USAGE;
+
+    $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+
+    $usage.put;
+}
+
+###############################################################################
diff --git a/challenge-168/athanasius/raku/ch-2.raku b/challenge-168/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..a657074b74
--- /dev/null
+++ b/challenge-168/athanasius/raku/ch-2.raku
@@ -0,0 +1,182 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 168
+=========================
+
+TASK #2
+-------
+*Home Prime*
+
+Submitted by: Mohammad S Anwar
+
+You are given an integer greater than 1.
+
+Write a script to find the home prime of the given number.
+
+In number theory, the home prime HP(n) of an integer n greater than 1 is the
+prime number obtained by repeatedly factoring the increasing concatenation of
+prime factors including repetitions.
+
+Further information can be found on [ https://en.wikipedia.org/wiki/Home_prime
+|Wikipedia] and [ https://oeis.org/A037274 |OEIS].
+
+Example
+
+As given in the Wikipedia page,
+
+  HP(10) = 773, as
+   10 factors as 2×5 yielding HP10(1)                                =  25,
+   25 factors as 5×5 yielding HP10(2) = HP25(1)                      =  55,
+   55          = 5×11 implies HP10(3) = HP25(2) = HP55(1)            = 511, and
+  511          = 7×73 gives   HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773,
+                                                                a prime number.
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2022 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Interface
+---------
+If the constant $VERBOSE is set to True (the default), all the steps in the
+calculation of a home prime are given as they are performed. For example, for
+input 10 the trajectory (set of steps) is:
+
+    Trajectory: 10 -> 2|5 -> 5|5 -> 5|11 -> 7|73
+
+which shows that 10 has prime factors 2 and 5; 25 has prime factors 5 and 5; 55
+has prime factors 5 and 11; and 511 has prime factors 7 and 73; producing 773,
+which is prime.
+
+If the constant $TIMER is set to True (it is False by default), the time, in
+seconds, required to find the requested home prime is also displayed.
+
+Implementation and Performance
+------------------------------
+Primality testing is performed by Raku's in-built is-prime() method.
+
+Factorization is performed by the get-prime-factors() routine, which tests for
+factors of 2, then for the odd numbers 3, 5, 7, ... in turn. This is one to two
+orders of magnitude slower than the Perl implementation using Math::Prime::
+Util::GMP, but still finds home primes in less than half a second for n = 2 to
+47  But for n = 48, the factorization of 35957822911130063089 into 835996339
+and 43011938251 is very slow because the smaller of the two factors is so big:
+21 minutes as compared to 0.02 seconds for the Perl version!
+
+=end comment
+#==============================================================================
+
+my Bool constant $TIMER   = False;
+my Bool constant $VERBOSE = True;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    "\nChallenge 168, Task #2: Home Prime (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+    Int:D $n where * > 1                           #= An integer greater than 1
+)
+#==============================================================================
+{
+    my DateTime $t0 = DateTime.now                 if $TIMER;
+
+    my UInt $hp = $n;
+
+    "Trajectory: $n".print                         if $VERBOSE;
+
+    until $hp.is-prime
+    {
+        my @prime-factors = get-prime-factors( $hp );
+
+        $hp = @prime-factors.join.Int;
+
+        " -> %s".printf: @prime-factors.join: '|'  if $VERBOSE;
+    }
+
+    "\n".put                                       if $VERBOSE;
+
+    "HP($n) = $hp".put;
+
+    my DateTime $t = DateTime.now                  if $TIMER;
+
+    "\n%s seconds\n".printf: ($t - $t0).Str        if $TIMER;
+}
+
+#------------------------------------------------------------------------------
+sub get-prime-factors( Int:D $n where * > 1 --> Seq:D[UInt:D] )
+#------------------------------------------------------------------------------
+{
+    my UInt @prime-factors;
+    my UInt $dividend = $n;
+
+    while $dividend %% 2
+    {
+        @prime-factors.push: 2;
+
+        $dividend = ($dividend / 2).Int;
+    }
+
+    my UInt $start = 3;
+
+    L-OUTER:
+    while $dividend > 1
+    {
+        loop (my UInt $factor = $start; ; $factor += 2)
+        {
+            if $factor.is-prime && $dividend %% $factor
+            {
+                @prime-factors.push: $factor;
+
+                $dividend = ($dividend / $factor).Int;
+                $start    =  $factor;
+
+                if $dividend.is-prime
+                {
+                    @prime-factors.push: $dividend;
+                    last L-OUTER;
+                }
+
+                next L-OUTER;
+            }
+        }
+    }
+
+    return @prime-factors.sort;
+}
+
+#------------------------------------------------------------------------------
+sub error( Str:D $message )
+#------------------------------------------------------------------------------
+{
+    "ERROR: $message".put;
+
+    USAGE();
+
+    exit 0;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+    my Str $usage = $*USAGE;
+
+    $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+
+    $usage.put;
+}
+
+###############################################################################