Pisano the Fortunate with Raku

[174] Published 13. March 2022.

This is my response to the Perl Weekly Challenge #155.

Challenge #155.1: Fortunate Numbers

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

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

Let us start with a program computing a single number (non-unique and unsorted):

File: fortunate-number-single

#! /usr/bin/env raku

subset PositiveInt of Int where * >= 1;

unit sub MAIN (PositiveInt $index = 7, :v(:$verbose));  # [1]

my $primes := (2 .. Inf).grep( *.is-prime );            # [2]

my $product = [*] $primes[^$index];                     # [3]

say ": Index: $index. Prime: $primes[$index-1]. Product: $product"
  if $verbose;

for 2 .. Inf -> $add                                    # [4]
{
  if ($product + $add).is-prime                         # [4a]
  {
    say $add;                                           # [4a]
    last;                                               # [4a]
  }
}

[1] The index, from 1 and upwards, as specified (as «n»).

[2] We need the prime numbers, so here it is as a sequence.

[3] Multiply the «n» first prime numbers, using the Reduction Metaoperator [] that (in this case, as the operator is *) multiplies all the values together.

See docs.raku.org/language/operators#Reduction_metaoperators for more information about the Reduction Metaoperator [].

[4] We are looking for the first prime number after the product we got in [3]. This loop does that. It prints the number we had to add to get to that prime and exits [4a].

Running it:

$ ./fortunate-number-single 1
3

$ ./fortunate-number-single 2
5

$ ./fortunate-number-single 3
7

$ ./fortunate-number-single 4
13

$ ./fortunate-number-single 5
23

$ ./fortunate-number-single 6
17

$ ./fortunate-number-single 7
19

$ ./fortunate-number-single 8
23

We got the expected result, the OEIS sequence A005235, as shown in the Wikipedia article - which is not the same as requested by the challenge, as it has duplicates (#5 and #23) and is not sorted.

Let us have a go at a sequence. Still with duplicates and unsorted.

File: fortunate-numbers-many

#! /usr/bin/env raku

subset PositiveInt of Int where * >= 1;

unit sub MAIN (PositiveInt $limit = 20, :v(:$verbose));  # [1]

my $primes := (2 .. Inf).grep( *.is-prime );

my @result;                                              # [2]

for 1 .. $limit -> $index                                # [3]
{
  my $product = [*] $primes[^$index];

  say ": Index: $index. Prime: $primes[$index-1]. Product: $product"
    if $verbose;

  for 2 .. Inf -> $add
  {
    if ($product + $add).is-prime
    {
      @result.push: $add;                                # [4]
      last;                                              # [4a]
    }
  }
}

say @result.join(", ");

[1] The number of values to print.

[2] The result (values to print) will end up here.

[3] For each index in the sequence, up to the upepr limit, compute the relevant value,

[4] add it to the result, and exit the inner loop (for the current index) [4a].

Running it gives the expected result:

$ ./fortunate-numbers-many 10
3, 5, 7, 13, 23, 17, 19, 23, 37, 61

$ ./fortunate-numbers-many -v 10
: Index: 1. Prime: 2. Product: 2
: Index: 2. Prime: 3. Product: 6
: Index: 3. Prime: 5. Product: 30
: Index: 4. Prime: 7. Product: 210
: Index: 5. Prime: 11. Product: 2310
: Index: 6. Prime: 13. Product: 30030
: Index: 7. Prime: 17. Product: 510510
: Index: 8. Prime: 19. Product: 9699690
: Index: 9. Prime: 23. Product: 223092870
: Index: 10. Prime: 29. Product: 6469693230
3, 5, 7, 13, 23, 17, 19, 23, 37, 61

Ok. Let us rewrite this to use a sequence:

File: fortunate-numbers-many-seq

#! /usr/bin/env raku

subset PositiveInt of Int where * >= 1;

unit sub MAIN (PositiveInt $limit = 20, :v(:$verbose));

my $primes := (2 .. Inf).grep( *.is-prime ).cache;
my $fn     := (1 .. $limit).map( { fn($_) });    # [1]

say $fn[^$limit].join(", ");

sub fn ($index)
{
  my $product = [*] $primes[^$index];

  say ": Index: $index. Prime: $primes[$index-1]. Product: $product"
    if $verbose;

  for 2 .. Inf -> $add
  {
    return $add if ($product + $add).is-prime;
  }
}

[1] This replaces the outer loop (marked [3]) in the previous version. The procedure call (and the code in it) replaces the content of that loop.

$ ./fortunate-numbers-many-seq 10
3, 5, 7, 13, 23, 17, 19, 23, 37, 61

$ ./fortunate-numbers-many-seq 20
3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103

Then we can have a go at the sorting order and getting rid of duplicates.

File: fortunate-numbers

#! /usr/bin/env raku

subset PositiveInt of Int where * >= 1;

unit sub MAIN (PositiveInt $limit = 20, :v(:$verbose));

my $primes := (2 .. Inf).grep( *.is-prime ).cache;
my $fn     := (1 .. Inf).map( { fn($_) });                              # [1]

say $fn.head(min(10, $limit * 2)).sort.squish.head($limit).join(", ");  # [2]

sub fn ($index)
{
  my $product = [*] $primes[^$index];

  say ": Index: $index. Prime: $primes[$index-1]. Product: $product"
    if $verbose;

  for 2 .. Inf -> $add
  {
    return $add if ($product + $add).is-prime;
  }
}

[1] We need more values than the limit, so we can use the fact that it is a sequence and set it up with an unlimited upper bound.

[2] Get enough values (double the end result, but minimum 10), sort them (with sort), get rid of adjacent duplicates (with squish), get the required number of values (with head) and print them.

See docs.raku.org/routine/head for more information about head.

Note that the array slice $primes[^$index] can be rewritten as $primes.head($index).

Running it gives the correct result:

$ ./fortunate-numbers 8
3, 5, 7, 13, 17, 19, 23, 37

The challenge did not actually require us to compute the values, just produce them. So we could have gotten away with this:

File: fortunate-numbers-quick

#! /usr/bin/env raku

say "3, 5, 7, 13, 17, 19, 23, 37";

What About Unfortunate Numbers?

I.e. numbers that are not Fortunate.

Let us have a go at them, using gather/take to collect the values:

File: unfortunate-numbers

#! /usr/bin/env raku

subset PositiveInt of Int where * >= 1;

unit sub MAIN (PositiveInt $limit = 20, :v(:$verbose));

my $primes := (2 .. Inf).grep( *.is-prime ).cache;
my $fn     := (1 .. Inf).map( { fn($_) });

my $unfortunate := gather
{
  my $current = 0;
  
  for $fn.head(min(10, $limit * 2)).sort.squish -> $fortunate
  {
    take $current while $current++ < $fortunate -1;
  }
}

say $unfortunate.head($limit).join(", ");

sub fn ($index)
{
  my $product = [*] $primes[^$index];

  say ": Index: $index. Prime: $primes[$index-1]. Product: $product"
    if $verbose;

  for 2 .. Inf -> $add
  {
    return $add if ($product + $add).is-prime;
  }
}

Running it:

$ ./unfortunate-numbers 20
1, 2, 4, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27

$ ./unfortunate-numbers 40
1, 2, 4, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28,\
29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48

I have decided that zero is not an Unfortunate number, even though it is not a Fortunate one. Feel free to consider this as an unfortunate decision.

Challenge #155.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.

Let us start with the plain sequence:

File: pisano-period-seq

#! /usr/bin/env raku

unit sub MAIN (Int :$n where $n != 0 = 3, :l(:$length) = 30);  # [1]

my $fibonacci     := (0, 1, * + * ... *);
my $pisano-period := $fibonacci.map( * % $n);

say $pisano-period[^$length];

[1] Division by zero is not a good idea, so we skip that value.

Running it:

$ ./pisano-period-seq -n=1
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

$ ./pisano-period-seq -n=2
(0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1)

$ ./pisano-period-seq -n=3
(0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2)

$ ./pisano-period-seq -n=4
(0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2 3 1 0 1 1 2 3 1)

$ ./pisano-period-seq -n=5
(0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 0 3 3 1 4)

Negative n values are ok:

$ ./pisano-period-seq -n=-3
(0 -2 -2 -1 0 -1 -1 -2 0 -2 -2 -1 0 -1 -1 -2 0 -2 -2 -1 0 -1 -1 -2 0 -2 -2 -1 0 -1)

Ok. Then we can have a go at figuring out the repeating pattern.

File: pisano-period

#! /usr/bin/env raku

unit sub MAIN (Int :$n where $n != 0 = 3,
                   :i(:$iterations) = 1000,     # [1]
                   :v(:$verbose));

my $fibonacci     := (0, 1, * + * ... *);
my $pisano-period := $fibonacci.map( * % $n); 

for 1 .. Inf -> $size                           # [2]
{
  next unless $pisano-period[$size + 1] == 0;   # [3]

  my $start = 0;                                # [4]

  my @first = $pisano-period[$start .. $size];  # [5]

  say ": [$start] - { @first.join(", ") }" if $verbose;

  loop                                          # [6]
  {
    my @next =                                  # [7]
      $pisano-period[$start + $size + 1 .. $start + $size + $size +1];

    say ": [$start] - { @next.join(", ") }" if $verbose;

    last unless @first cmp @next eq "Same";     # [8]
    $start = $start + $size +1;                 # [9]

    if $start > $size * $iterations             # [10]
    {
      say $size + 1;                            # [10a]
      exit;                                     # [10b]
    }
  }
}

[1] It is unclear how many times we have to find the repeating pattern until we can be certain that indeed is repeating ad infinitum. I have chosen to look for 1000 repetitions, but this can be overridden depending on your level of paranoia.

[2] Iterate over the size of the length of values to consider, from 1 and up.

[3] The second chunk (an instance of the repeating pattern) must start with zero, as the first one does so. So we can skip sizes that would lead to a second chunk starting with a non-zero value.

[4] The index of the first value.

[5] The first chunk.

[6] Go on looking forever.

[7] Get the next chunk.

[8] Compare the first and current chunk with cmp, as it will compare the two arrays - item for item. We have failed if they are not the same - i.e. have to look for a longer pattern.

See docs.raku.org/routine/cmp for more information about the Generic, "smart" three-way comparator cmp.

[9] Prepare for the next itertation (over the chunks).

[10] Still here after 1000 iterations? Then we can conclude that we have a recurring pattern, report the length [10a] and quit [10b].

Running it:

$ ./pisano-period -n=2
3

$ ./pisano-period -n=3
8

$ ./pisano-period -n=4
6

With verbose mode, and a low value for «i« to avoid the default 1000+ debug lines:

$ ./pisano-period -n=2 -v -i=10
: [0] - 0, 1, 1
: [0] - 0, 1, 1
: [3] - 0, 1, 1
: [6] - 0, 1, 1
: [9] - 0, 1, 1
: [12] - 0, 1, 1
: [15] - 0, 1, 1
: [18] - 0, 1, 1
3

$ ./pisano-period -n=3 -v -i=10
: [0] - 0, 1, 1, 2
: [0] - 0, 2, 2, 1
: [0] - 0, 1, 1, 2, 0, 2, 2, 1
: [0] - 0, 1, 1, 2, 0, 2, 2, 1
: [8] - 0, 1, 1, 2, 0, 2, 2, 1
: [16] - 0, 1, 1, 2, 0, 2, 2, 1
: [24] - 0, 1, 1, 2, 0, 2, 2, 1
: [32] - 0, 1, 1, 2, 0, 2, 2, 1
: [40] - 0, 1, 1, 2, 0, 2, 2, 1
: [48] - 0, 1, 1, 2, 0, 2, 2, 1
: [56] - 0, 1, 1, 2, 0, 2, 2, 1
: [64] - 0, 1, 1, 2, 0, 2, 2, 1
8

$ ./pisano-period -n=4 -v -i=10
: [0] - 0, 1, 1, 2, 3, 1
: [0] - 0, 1, 1, 2, 3, 1
: [6] - 0, 1, 1, 2, 3, 1
: [12] - 0, 1, 1, 2, 3, 1
: [18] - 0, 1, 1, 2, 3, 1
: [24] - 0, 1, 1, 2, 3, 1
: [30] - 0, 1, 1, 2, 3, 1
: [36] - 0, 1, 1, 2, 3, 1
: [42] - 0, 1, 1, 2, 3, 1
: [48] - 0, 1, 1, 2, 3, 1
6

And that's it.

Links

About me
Keyword Index
Raku Courses
Beginning Raku (book)
RSS Feed
Code (zip)
Reddit Comments