laurent_r

These are some answers to the Week 155 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 13, 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: Fortunate Numbers

Write a script to produce first 8 Fortunate Numbers (unique and sorted).

According to Wikipedia:

A Fortunate number, named after Reo Fortune, is the smallest integer m > 1 such that, for a given positive integer n, pn# + m is a prime number, where the primorial pn# is the product of the first n prime numbers.

Expected Output:

3, 5, 7, 13, 17, 19, 23, 37

Fortunate Numbers in Raku

We first create an infinite (lazy) list (@primes) of prime numbers. Then, we use it to create a list of primordials (@primorials). And then, we use it to find fortunate numbers.

my @primes = grep { .is-prime }, 1..Inf;
my @primorials = (0, | (gather { take ([*] @primes[0..$_-1]) for 1..20}));
# say @primorials[0..8];  # (0 2 6 30 210 2310 30030 510510 9699690)

sub find-fortunate (Int $n) {
    my $pn = @primorials[$n-1];
    # say $pn;
    for 2..Inf -> $m {
        return $m if is-prime $pn + $m;
    }
}
my $fortunates = (map { find-fortunate $_ }, 2..20).Set;
say ($fortunates.keys.sort)[0..7];

This program displays the following output:

$ raku ./fortunate.raku
(3 5 7 13 17 19 23 37)

Fortunate Numbers in Perl

This a port to Perl of the Raku program above. We need to roll out our own is_prime and prime_list subroutines.

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

my @primes = prime_list(MAX);
my %fortunates = map { find_fortunate($_) => 1} 1..15;
my @result = sort { $a <=> $b } keys %fortunates;
say join " ", @result[0..7];

sub is_prime {
        my $num = shift;
        return 1 if $num == 2;
        return 0 unless $num % 2;
        my $test = 3;
        while ($test < $num/2) {
                return 0 if $num % $test == 0;
                $test += 2;
        }
        return 1;
}

sub prime_list {
    my $max = shift;
    my @prime_list = (2, 3, 5);
    for my $c (7..$max) {
        push @prime_list, $c if is_prime($c);
    }
    return @prime_list;
}


sub find_fortunate {
    my $n = shift;
    my $pn = 1;
    $pn *= $_ for @primes[0..$n-1];
    # say $pn;
    for my $m (2..50) {
        return $m if is_prime($pn + $m);
    }
}

This program displays the following output:

$ perl ./fortunate.pl
 3 5 7 13 17 19 23 37

Task 2: Pisano Period

Write a script to find the period of the 3rd Pisano Period.

In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.

The Fibonacci numbers are the numbers in the integer sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

For any integer n, the sequence of Fibonacci numbers F(i) taken modulo n is periodic. The Pisano period, denoted π(n), is the value of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:

0, 1, 1, 2, 0, 2, 2, 1,
0, 1, 1, 2, 0, 2, 2, 1,
0, 1, 1, 2, 0, 2, 2, 1, ...

This sequence has period 8, so π(3) = 8.

Well, the fact that we find the same sequence repeated three times as in the example above might not be an absolute mathematical proof that the sequence is really periodic. But it is a quite strong indication that it probably is. If we have a repeated sequence of (at least) two numbers, then the third (or next) number ought to be the same, and so on for the next terms. But that doesn’t necessarily mean we’ve found the longest repeated sequence.

Finding such sequences is relatively easy, but a bit painful with bunches of nested loops. We have a tool specialized in doing this kind of work: regexes.

Pisano Period in Raku

First, we use the infix ... sequence operator to compute an infinite list of Fibonacci numbers modulo 3. All terms will be one-digit integers between 0 and 2. The we join part of this list (say the first 30 terms) into a string. Then we use a regex to find a repeated pattern. Finally, we output the length of this pattern:

my @fibmod = 1, 1, (* + *) % 3 ... *;
my $seq = @fibmod[0..30].join('');
# say $seq; # 1120221011202210112022101120221
my $repeated = $0 if $seq ~~ /(.+) $0+/;
say $repeated.chars;

This script displays the following output:

$ raku ./pisano.raku
8

Pisano Period in Perl

This is essentially a port to Perl of the Raku program above, with the slight change that we’re using a loop to populate the Fibonacci numbers modulo 3.

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

my @fibmod = (1, 1);
$fibmod[$_] = ($fibmod[$_-1] + $fibmod[$_-2]) % 3 for 2..30;
my $seq = join '', @fibmod[0..30];
# say $seq; # 1120221011202210112022101120221 
my $repeated = $1 if $seq =~ /(.+)\1+/;
say length $repeated;

This program displays the following output:

$ perl ./pisano.pl
8

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