laurent_r

These are some answers to the Week 168 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days from now (on June 12, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

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]

On my first implementation, I originally obtained the following sequence:

2 3 2 5 5 7 17 29 277 367 853 14197 43721...

There are two major differences with the expected output: the sequence should be ordered (i.e. sorted in ascending order), and duplicates should be removed.

Perrin Primes in Raku

It is quite easy to do it with a Raku one-liner:

say (unique grep {.is-prime}, (3, 0, 2, -> $a, $b, $c { $a + $b } ... ∞))[0..12].sort;

Here, we use the ... sequence operator to build an infinite list of Perrin numbers. Then, we grep the output to retain only primes and use the unique built-in to remove duplicates. We finally take a slice of 13 items of that infinite array and sort the result in ascending order. Note that the order of the operations is important: for example, it is not possible to sort an infinite list, so the sort must occur at the end, after the extraction of the 13 elements.

This script displays the following output:

$ raku ./perrin.raku
(2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977)

Perrin Primes in Perl

The Perl solution is significantly more complicated for two reasons. First, we don’t have the sequence operator to build directly the Perrin sequence, and need to use a loop. Second, we need to implement our own is_prime subroutine.

use strict;
use warnings;
use feature "say";

my @perrin = (3, 0, 2);
my @result = (2, 3);
my %seen = map { $_ => 1 } @result;
while (1) {
    my $new_item = $perrin[-3] + $perrin[-2];
    push @perrin, $new_item;
    if (is_prime($new_item)) {
        push @result, $new_item unless $seen{$new_item};
        $seen{$new_item} = 1;
        last if @result > 12;
    }
}
say join " ", sort { $a <=> $b } @result;

sub is_prime {
   my $n = shift;
   return 1 if $n == 2;
   return 0 if $n % 2 == 0;
   return 0 if $n == 1;

   my $p = 3;
   my $sqrt = sqrt $n;
   while ($p <= $sqrt) {
       # return 1 if $p >= $n;
       return 0 if $n % $p == 0;
       $p += 2;
   }
   return 1;
}

This program displays the following output:

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

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on June 19, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.