This is my response to The Weekly Challenge #168.
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, ….)
13 Perrin Primes.
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
Further information can be found on Wikipedia and OEIS.
Example:
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.