by Arne Sommer

# Primarily Prime with Raku and Perl

[187] Published 12. June 2022.

This is my response to The Weekly Challenge #168.

## Challenge #168.1: Perrin Prime

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]

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

#### What the ****

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

### A Perl Version

This is straight forwardish translation of the Raku version, using a queue (with `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 ```

## Challenge #168.2: Home Prime

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

### Perl

This is a straight forward translation of the Raku version.

File: home-prime-perl ```#! /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.