with Raku and Perl

This is my response to The Weekly Challenge #168.

The

A Perrin prime is a number in the Perrin sequence which is also a prime number.

Calculate the first

f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]

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

The Perrin sequence resembles the Padovan Sequence (in the way it is set up - not the actual values) from Challenge 154. The Raku and Perl code is taken from my Padovan is Missing with Raku and Perl article, and modified to fit the new sequence. (I have remedied my Grep debacle, as explained in Fooled by a Sequence, Twice, as well.)

First the plain sequence:

File: perrin-seq#! /usr/bin/env raku
unit sub MAIN (:c(:$count) = 10); # [1]
my $perrin := (3, 0, 2, ( * + * + * * 0 ) ... Inf);
# ############ [2] #### # [2a] ########## [2b] ###
say $perrin[^$count].join(", "); # [3]

[1] The number of items (values) to print, with 10 as default.

[2] The sequence, starting with the three values `3. 0, 2`

, then a pattern
for the following values [2a] until we reach infinity (i.e. forever) [2b].

Let us have a closer look at the pattern in [2a]:

( * + * + * * 0 )
A B C D E F G

[A] The first `*`

is a placeholder, referring to the previous value in the
sequence.

[B] This is a literal plus sign, used for addition.

[C] This second `*`

is also a placeholder. They are ordered from the right,
so this one is (now) referring to the previous value, and the one in [A] the one before
that in the sequence. The result so far is that we have added these two values
together.

[D] Another addition, followed by another placeholder [E]. This shifts the previous
two values (in [A] and [C] further up memory lane (previous values)), so that we get
the values we need. This one (N-1) is not needed, so we multiply it (yes this
`*`

is not magic) [F] with zero [G] to get rid of it. Multiplication has
higher precedence than addition, so this works out.

[3] Print the required number of values, nicely comma separated.

Running it:

$ ./perrin-seq
3, 0, 2, 3, 2, 5, 5, 7, 10, 12
$ ./perrin-seq -c=50
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, \
277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610, 6107, 8090, \
10717, 14197, 18807, 24914, 33004, 43721, 57918, 76725, 101639, 134643, \
178364, 236282, 313007, 414646, 549289, 727653, 963935

Looking good.

Then we can have a go at the Perrin prime sequence:

File: perrin-prime```
#! /usr/bin/env raku
unit sub MAIN (Int :c(:$count) where $count > 1 = 13); # [1]
my $pp := ( 3, 0, 2, ( * + * + * * 0 ) ... Inf).unique.grep( *.is-prime ); # [2]
say $pp[^$count].join(", "); # [1]
```

[1] The number of values to print from the sequence, with 13 as the default.

[2] We use `unique`

to get rid of duplicates,
as we do not want them (and the Perrin Sequence has 3 of them). Then we use
`grep`

and `is-prime`

to get rid of non-prime values.

See
docs.raku.org/routine/is-prime
for more information about `is-prime`

.

Running it:

$ ./perrin-prime
3, 2, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977

Yes, except the order (of the two first values).

File: perrin-prime-sorted```
#! /usr/bin/env raku
unit sub MAIN (Int :c(:$count) where $count > 1 = 13); # [1a]
my $pp := ( 3, 0, 2, ( * + * + * * 0 ) ... Inf).unique.grep( *.is-prime );
say $pp[^$count].sort.join(", "); # [1]
```

[1] The order is fixable with `sort`

. This will evaluate
a lazy data structure, so is not something we can do on the (infinite) sequence itself.
But we can do it on this list with a finite number of elements. Note that this will
give the wrong result if were top ask for one value only, so the minimum is 2 courtesy
of the `where`

clause in [1a].

See
docs.raku.org/routine/sort
for more information about `sort`

.

Running it:

$ ./perrin-prime-sorted
2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977

`shift`

and `push`

):
File: perrin-prime-perl
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
use feature 'state';
use bigint;
use Math::Prime::Util 'is_prime';
no warnings qw(experimental::signatures);
my $count = $ARGV[0] || 13;
sub next_perrin
{
state @perrin;
if (! @perrin)
{
@perrin = (3,0,2);
}
else
{
push(@perrin, $perrin[-2] + $perrin[-3]);
}
shift @perrin if @perrin == 4;
return $perrin[-1];
}
my @pp;
while (@pp < $count)
{
my $next = next_perrin;
next if @pp && $next <= $pp[-1];
next unless is_prime($next);
push(@pp, $next);
}
say join(", ", @pp);

Running it gives the same result as the Raku version:

$ ./perrin-prime-perl
2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977

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.

As given in the Wikipedia page,

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 Wikipedia and 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.

My «factors» procedure, introduced in Centenary Sequences with Raku - Part 5: Divisors and Factors is handy here, and in fact does almost everything:

File: home-prime#! /usr/bin/env raku
unit sub MAIN (Int $number is copy where $number > 1); # [1]
$number = factors($number).join.Int until $number.is-prime; # [2]
say $number;
sub factors ($number is copy)
{
return (1) if $number == 1;
return ($number) if $number.is-prime;
my @factors;
for (2 .. $number div 2).grep( *.is-prime) -> $candidate
{
while $number %% $candidate
{
@factors.push: $candidate;
$number /= $candidate;
}
}
return @factors;
}

[1] Ensure a positive integer.

[2] Get the factors, `join`

them together (and coerce the resulting string
to an integer, as `is-prime`

does not like strings), `until`

we
have a prime number.

Running it:

$ ./home-prime 10
773
$ ./home-prime 11
11
$ ./home-prime 12
223

Looking good.

Do not try the following, as it will probably freeze your computer due to the sheer amount of work going on:

$ ./home-prime 8

#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings 'experimental::signatures';
use Math::Prime::Util 'is_prime';
my $number = int($ARGV[0]) || 0;
die "Please specify a positive integer"
unless $number =~ /^[1-9]\d*$/ && $number > 1;
$number = join("", factors($number)) until is_prime($number);
say $number;
sub factors ($number)
{
return (1) if $number == 1;
return ($number) if is_prime($number);
my @factors;
for my $candidate (grep { is_prime($_) } 2 .. $number / 2)
{
while ($number % $candidate == 0)
{
push(@factors, $candidate);
$number /= $candidate;
}
}
return @factors;
}

Running it gives the same result as the Raku version:

$ ./home-prime-perl 10
773
$ ./home-prime-perl 11
11
$ ./home-prime-perl 12
223

Do not try the following, as it will probably freeze your computer due to the sheer amount of work going on:

$ ./home-prime-perl 8

And that's it.