Perl Weekly Challenge 155.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 155.

Task 1: Fortunate Numbers

Submitted by: Mohammad S Anwar
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

The following one liner generates Fortunate numbers using the package Math::Prime::Util to generate primes.

perl -MMath::Prime::Util=pn_primorial,next_prime -E '
++$f{next_prime(($p=pn_primorial(++$i))+1)-$p} while(keys %f<8);
say join " ", sort {$a<=>$b} keys %f;'

Results:

3 5 7 13 17 19 23 37

This simple code apparently works correctly, but would fail if more than 8 unique, sorted Fortunate numbers were desired (see discussion below). In general, more primorial numbers should be explored than the amount of Fortunate numbers desired. Thus, I make a version with a couple of paramenters (how many Fortunate numbers are desired and how many primorials to use):

perl -MMath::Prime::Util=pn_primorial,next_prime -E '
push @f,next_prime(($p=pn_primorial(++$i))+1)-$p while(@f<$ARGV[1]);
@f{@f}=(1)x@f;say join " ", @{[sort {$a<=>$b} keys %f]}[0..$ARGV[0]-1];
' 9 14

Results:

3 5 7 13 17 19 23 37 47

The full, somewhat more careful version follows:

 1  # Perl weekly challenge 155
 2  # Task 1: Fortunate numbers
 3  #
 4  # See https://wlmb.github.io/2022/03/07/PWC155/#task-1-fortunate-numbers
 5  use v5.12;
 6  use warnings;
 7  use bigint;
 8  use Math::Prime::Util qw(next_prime pn_primorial);
 9  use Getopt::Lazy
10      'help|h|?' => 'Show help screen',
11      'Nf=i' => '*Number of Fortunates to generate',
12      'Np=i' => 'Number of primorials to use',
13      -summary => 'Generate lowest distinct fortunate numbers',
14      -usage => '%c %o',
15      ;
16  GetOptions;
17  show_help, exit if $help;
18  $Nf//=8;
19  $Np//=9;
20  my @primorial=map {pn_primorial($_)} (1..$Np) ; # start primorials in first prime
21  my @fortunate;
22  foreach(@primorial){
23      push @fortunate, next_prime($_+1)-$_;
24  }
25  my %fortunate;
26  @fortunate{@fortunate}=(1)x@fortunate;
27  die "Didn't find enough disctinct Fortunate numbers; please increase Np\n"
28          unless keys %fortunate>=$Nf;
29  say "The $Nf lowest distinct Fortunate numbers found are";
30  say join " ", @{[sort {$a<=>$b} keys %fortunate]}[0..$Nf-1];

Example:

./ch-1.pl

Results:

The 8 lowest distinct Fortunate numbers found are
3 5 7 13 17 19 23 37

Example asking for more results:

./ch-1.pl -Nf 9

Results:

Didn't find enough disctinct Fortunate numbers; please increase Np

Example increasing the number of primorials to test.

./ch-1.pl -Nf 9 -Np 10

Results:

The 9 lowest distinct Fortunate numbers found are
3 5 7 13 17 19 23 37 61

This example yields a wrong result which illustrates a problem. As Fortunate numbers are not produced in order, it is possible that lower numbers are obtained by looking further. Thus, for example, we may examine further primorial numbers,

./ch-1.pl -Nf 9 -Np 14

Results:

The 9 lowest distinct Fortunate numbers found are
3 5 7 13 17 19 23 37 47

So the error in the previous example is due to the fact that the 14-th Fortunate number is lower than 61, the 9-th we obtained by looking up to the 10-th, as we can verify by printing more results.

./ch-1.pl -Nf 13 -Np 16

Results:

The 13 lowest distinct Fortunate numbers found are
3 5 7 13 17 19 23 37 47 59 61 67 71

Therefore, the solution is not too robust and requires fidling with the parameters until a convinicing result is obtained.

Task 2: Pisano Period

Submitted by: Mohammad S Anwar
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.

As a Fibonacci number is determined by the previous two numbers, a cycle begins whenever a pair of two consecutive numbers coincide with a previous pair. In this particular case, the sequences repeat from the start, so I don’t have to subtract the initial index. I use a recursive Fibonacci function for the following one-liner.

perl -E '$N=shift @ARGV; $n=0; my @s; while(1){say("Input: $N\n Output: $n"), last
if $s[f($n)][f($n+1)]; $s[f($n)][f($n+1)]=1; ++$n;}
sub f{my $n=shift; return 0 if $n<=0; return 1%$N if $n==1; (f($n-2)+f($n-1))%$N};
' 3

Results:

Input: 3
 Output: 8

The full solution is

 1  # Perl weekly challenge 155
 2  # Task 2: Pisano period
 3  #
 4  # See https://wlmb.github.io/2022/03/07/PWC155/#task-2-pisano-period
 5  use v5.12;
 6  use warnings;
 7  use Memoize;
 8  memoize("fib");
 9  say("Usage: ./ch-2.pl n1 [n2 [n3...]]\n",
10        "to obtain the Pisano period of the Fibonacci sequence modulo n_i")
11        unless @ARGV;
12  for my $N(@ARGV){
13      my $n=0;
14      my @seen;
15      while(1){
16          my $s=$seen[fib($n, $N)][fib($n+1, $N)];
17          say("Input: $N Output: ", $n-$s), last
18              if defined $s;
19  	$seen[fib($n, $N)][fib($n+1, $N)]=$n;
20  	++$n;
21      }
22  }
23
24  sub fib{
25      my ($n, $N)=@_;
26      return 0 if $n<=0;
27      return 1%$N if $n==1;
28      return (fib($n-2, $N)+fib($n-1, $N))%$N;
29  };

The main differences are a loop to allow different moduli, memoizing the recursive function and recording and subtracting the iteration number corresponding to the repeated values, to allow sequences that don’t repeat from the start. In this case it is unnecesary, but in general it is safer.

Example:

./ch-2.pl `seq 10`

Results:

Input: 1 Output: 1
Input: 2 Output: 3
Input: 3 Output: 8
Input: 4 Output: 6
Input: 5 Output: 20
Input: 6 Output: 24
Input: 7 Output: 16
Input: 8 Output: 12
Input: 9 Output: 24
Input: 10 Output: 60
Written on March 7, 2022