laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on March 6, 2022 at 24:00). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Missing Permutations

You are given possible permutations of the string ‘PERL’.

PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
LPER, LPRE, LEPR, LRPE, LREP

Write a script to find any permutations missing from the list.

We’ll assume that the permutations provided are correct, but that at least one is missing. In fact, if one of the permutation is wrong, this would not alter the result. For this task, we’ll generate all permutations and compare the result with the given list of permutations.

Missing Permutations in Raku

First, we store the given permutations in a set for fast lookup. Then, we use the permutations built-in routine to generate all permutations and loop through them to find those that are missing from the given list.

my $given_perm = set(qw/
    PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL
    ERLP ELPR ELRP RPEL RPLE REPL RELP RLPE RLEP
    LPER LPRE LEPR LRPE LREP /);
for "PERL".comb.permutations>>.join("") -> $perm {
    say "$perm is missing" if $perm ∉ $given_perm;
}

This script produces the following output:

$ raku ./missing_permutations.raku
LERP is missing

Here, we have hard-coded the “PERL” word used to generate all permutations, but, assuming the given list has only correct permutations, we can just pick any permutation from the list as the starting point. We’ll do that in the implementation below, using the $given_perm.keys[0] syntax. Another possible variation is that, since we’re using sets, we could store the full list of permutations in another set and use the built-in set difference operator ((-) or ∖) to find the missing permutations. Here, I won’t use the ∖ operator because I find it a bit confusing (it looks too much like the \ backslash operator).

my $given_perm = set(qw/
    PELR PREL PERL EPRL EPLR ERPL
    ERLP ELPR ELRP RPEL RLPE RLEP
    LPER LPRE LEPR LRPE LREP /);
my $perms = set($given_perm.keys[0].comb.permutations>>.join(""));
say "Missing: ", ~($perms (-) $given_perm);

Notice that I have also removed some permutations from the given list, in order to show what happens when there is more than one permutation missing.

This script produces the following output:

$ raku ./missing_permutations2.raku
Missing: PRLE REPL RPLE RELP PLER PLRE LERP

Missing Permutations in Perl

Perl doesn’t have sets, but we can achieve the same result (fast lookup) with hashes. Since there is also no built-in permutation function, we implement our own recursive permute subroutine.

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

my @permutations;
my %given_perm = map { $_ => 1 } qw/
    PELR PREL PERL PRLE PLER PLRE EPRL EPLR ERPL
    ERLP ELPR ELRP RPEL RPLE REPL RELP RLPE RLEP
    LPER LPRE LEPR LRPE LREP /;

sub permute { 
    my ($str, @vals) = @_;
    if (scalar @vals == 0) {
        push @permutations, $str;
        return;
    }
    permute("$str" . $vals[$_], @vals[0..$_-1], 
        @vals[$_+1..$#vals]) for 0..$#vals;
}
permute "", split //, (keys %given_perm)[0];
for my $perm (@permutations) {
    say "$perm is missing" unless exists $given_perm{$perm};
}

This program displays the following output:

$ perl ./missing_permutations.pl
LERP is missing

Task 2: Padovan Primes

A Padovan Prime is a Padovan Number that’s also prime.

In number theory, the Padovan sequence is the sequence of integers P(n) defined by the initial values.

P(0) = P(1) = P(2) = 1

and then followed by

P(n) = P(n-2) + P(n-3)

First few Padovan Numbers are as below:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...

Write a script to compute first 10 distinct Padovan Primes.

Expected Output:

2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057

So, the Padovan sequence is built in a way very similar to the Fibonacci sequence, except that instead of using Fibonacci’s P(n-1) + P(n-2), the Padovan sequence uses the following recurrence relation: P(n-2) + P(n-3). The terms quickly come close to a geometric progression with a common ratio of approximately 1.3247 (known as the plastic number). So it is growing very rapidly (but less rapidly than the Fibonacci sequence, whose common ratio is the golden mean, 1,618).

To give an idea of the growth, these are the first 140 Padovan numbers:

1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200 265 351 465 616 816 1081 1432 1897 2513 3329 4410 5842 7739 10252 13581 17991 23833 31572 41824 55405 73396 97229 128801 170625 226030 299426 396655 525456 696081 922111 1221537 1618192 2143648 2839729 3761840 4983377 6601569 8745217 11584946 15346786 20330163 26931732 35676949 47261895 62608681 82938844 109870576 145547525 192809420 255418101 338356945 448227521 593775046 786584466 1042002567 1380359512 1828587033 2422362079 3208946545 4250949112 5631308624 7459895657 9882257736 13091204281 17342153393 22973462017 30433357674 40315615410 53406819691 70748973084 93722435101 124155792775 164471408185 217878227876 288627200960 382349636061 506505428836 670976837021 888855064897 1177482265857 1559831901918 2066337330754 2737314167775 3626169232672 4803651498529 6363483400447 8429820731201 11167134898976 14793304131648 19596955630177 25960439030624 34390259761825 45557394660801 60350698792449 79947654422626 105908093453250 140298353215075 185855747875876 246206446668325 326154101090951 432062194544201 572360547759276 758216295635152 1004422742303477 1330576843394428 1762639037938629 2334999585697905 3093215881333057 4097638623636534 5428215467030962 7190854504969591 9525854090667496 12619069972000553 16716708595637087 22144924062668049 29335778567637640 38861632658305136 51480702630305689 68197411225942776

Padovan Primes in Raku

We first build an infinite (lazy) list of Padovan numbers using the infix ... sequence operator. We then loop over these numbers and, for each of hem, check whether it is prime using the is-prime built-in routine.

my @padovans = 1, 1, 1, -> $a, $b, $c { $a + $b } ... *;
# say @padovans[0..10];  # (1 1 1 2 2 3 4 5 7 9 12)
my $max = 10;
my $prev_pad = 1;
for @padovans -> $pad {
    next if $prev_pad == $pad;
    if $pad.is-prime {
        print "$pad ";
        $max--;
    }
    $prev_pad = $pad;
    last if $max <= 0;
}
say "";
say now - INIT now;

This program displays the following output:

$ raku ./padovan_prime.raku
2 3 5 7 37 151 3329 23833 13091204281 3093215881333057 
0.2039814

Note that I timed the execution and found the duration (0.2 sec.) to be much less than I feared for computations on such large numbers. I suppose that the Miller-Rabin primality test used by the is-prime built-in routine is so fast that you can use it more than 100 times in a split second (the tenth Padovan prime, 3,093,215,881,333,057, is the 129th Padovan number).

Padovan Primes in Perl

Here again, I was afraid about numerous primality tests on very large integers, and decided to first build a list of prime numbers so that I would have to test each Padovan numbers against only prime numbers (up to a certain limit), rather than, say, all odd numbers, in order to speed up the process. It turns out that it wasn’t really necessary as the process runs in about only 6 seconds without this optimization. Worse yet, the performance optimization improves the execution duration only by a very marginal factor (perhaps by at most 20%). Clearly, it wasn’t worth the effort. I know very well Donald Knuth’s famous quote about “premature optimization (being) the source of all evil.” I thought I knew better in this specific case, but that was a mistake.

use strict;
use warnings;
use feature "say";
use constant MAX => 10000; # MAX must be an even number

my @primes = prime_list(MAX);
# say "@primes"; # 2 3 5 7 11 13 17 19 23 29 31 37 41 ...

my @padovans = (1, 1, 1);
for my $i (3..140) {
    $padovans[$i] = $padovans[$i-2] + $padovans[$i-3]
} 
# say "@padovans"; # 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 ...

my $count = 0;
my $last_pad = 0;
for my $pad (@padovans) {
    next if $pad == $last_pad;
    $last_pad = $pad;
    next unless is_prime($pad);
    say $pad;
    $count++;
    last if $count > 9;
}

sub prime_list {
    my $max = shift;
    my @prime_list = (2, 3, 5);
    PRIMES: for my $c (7..$max) {
            for my $i (2..$c/2) {
                next PRIMES unless $c % $i;
            }
            push @prime_list, $c;
    }
    return @prime_list;
}
sub is_prime {
    my $num = shift;
    for my $prime (@primes) {
        return 1 if $num == $prime;
        return 0 if $prime > $num;
        return 0 unless $num % $prime;
    }
    my $test = MAX+1;
    while ($test < int(sqrt($num))) {
        return 0 unless $num % $test;
        $test += 2;
    }
    return 1;
}

This program displays the following output:

$ perl ./padovan_prime.pl
2
3
5
7
37
151
3329
23833
13091204281
3093215881333057

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 March 13, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.