# I Ain't No Fortunate One: Weekly Challege #155

We’re now at Weekly Challege #155. **155** is the product of the primes **5** and **31**, making it a **compound** number. I feel I *must* have heard *compound* as a term for not-prime numbers, but I don’t actually recall seeing it. It is also deficient and odious, which sounds a *lot* like mathematicians scouring through a dictionary to find names for new number sets.

### TASK #2 › Pisano Period

Submitted by: Mohammad S Anwar

Write a script to find the period of the3rd 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.

For reasons, I’m covering Task #2 before Task #1. A core one is that …

- the Perl CS Discord pointed to …
- a Hacker News thread about …
- a blog post about…
- Abigail’s
`is_prime`

regex solution… - which is
`perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]`

And of course I needed to look and understand it.

`(1 x shift)`

just creates a string that’s`1`

repeated the same number of times as the number in question:`1 x 3 => 111`

, for example.`=~`

means we’re running the following regex against that string`/^1?$/`

covers the**0**and**1**cases, where`(1 x shift)`

would result in an empty string or`1`

. Both this and the next section start with`^`

and end with`$`

, meaning we’re talking about the whole string.`(11+?)`

, which checks to see if there are 2 or more**1**s, non-greedily. I*think*, in this case, it means we’re starting with**11**and going out, rather than**all the 1s**and cutting back.By default, a quantified subpattern is “greedy”, that is, it will match as many times as possible (given a particular starting location) while still allowing the rest of the pattern to match. If you want it to match the minimum number of times possible, follow the quantifier with a “?”. Note that the meanings don’t change, just the “greediness”

`\1+`

matches the matched value one or more times. Assume we’re seeing if**9**is prime, and the match for`(11+?)`

is`111`

.`111`

is found within`111111111`

three times —`111 111 111`

— and thus 9 is not prime.

We *aren’t* looking for primes in this task, but we are looking for repetition, so that’s how I’m going forward.

I’ll say, however, that I am, in the code below, generating the matches with just digits, which would become problematic once we get to two-digit numbers, because then it wouldn’t know the difference between `1,11`

and `11,1`

because my join would only generate `111`

, but as we’re looking for single-digit divisors (I think), that isn’t a problem with this code.

You shouldn’t be surprised if you see an addendum post about this task.

```
# when going beyond the basics, it is good to know you can
# comment your regular expressions
do { ... } if $mod =~ /
^ # start of string being matched
(\d{3,}) # a digit of three or more characters
# (to avoid matching 1,1 at the beginning
# of every fibonacci series)
\1+ # the previous match, repeated once or more
$ # end of string being matched
/mx;
```

Another way I’m going forward is with **iterators**. Clearly, I could just use a standard iteration function to generate fibonacci numbers, but I decided to create *fibo_factory*, a subroutine that creates an anonymous subroutine that, each time it’s called, returns the next fibonacci value. When I’m done with another divisor, I start fresh with a new iterator. I don’t *need* to do that, but it’s the kind of higher-order thinking I don’t think I do enough of in my challenge answers.

Beyond that, I think I use my standard complement of Modern Perl features, such as `say`

, `state`

, `postderef`

and `signatures`

, as well as loop labels. If there’s a thing you don’t understand here, don’t hesitate to ask.

That is to say, I’m confident in all the code I created, but I’m less confident that I’m actually giving the requested answer. What I’m displaying is the divisor, the period of the the repetition and the actual repeats. I’ll look at other answers to find if I’m correct here.

#### Show Me The Code

```
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };
OUTER: for my $j ( 2 .. 10 ) {
my @mod;
my $fib = fibo_factory();
for my $i ( 1 .. 60 ) {
my $f = $fib->();
my $m = $f % $j;
push @mod, $m;
my $mod = join '', @mod;
do {
my $sub = $1;
say join "\t", ' ', $j, ( length $sub ), $sub;
next OUTER;
}
if $mod =~ /
^ # start of string being matched
(\d{3,}) # a digit of three or more characters
# (to avoid matching 1,1 at the beginning
# of every fibonacci series)
\1+ # the previous match, repeated once or more
$ # end of string being matched
/mx;
}
}
# creates an anonymous function that's an iterator, returning the next
# fibonacci value each time it's called.
sub fibo_factory ( ) {
return sub {
state $calls = 0;
state @fibonacci;
$fibonacci[0] = 1 unless $fibonacci[0];
$fibonacci[1] = 1 unless $fibonacci[1];
$calls++;
return 1 if $calls < 3;
push @fibonacci, $fibonacci[-1] + $fibonacci[-2];
return $fibonacci[-1];
}
}
# abigail's prime regex, insspiration for my repeats test
sub is_prime ($n) {
return ( 1 x $n ) !~ /^1?$|^(11+?)\1+$/ ? 1 : 0;
}
```

```
$ ./ch-2.pl
2 3 110
3 8 11202210
4 6 112310
5 20 11230331404432022410
6 24 112352134150554314532510
7 16 1123516066542610
8 12 112350552710
9 24 112358437180887641562810
```

### TASK #1 › Fortunate Numbers

Submitted by: Mohammad S Anwar

Write a script to produce first8 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

It’s good to know the expected output. In this case, it’s because **23** shows up once, but if you just list the first eight fortunate numbers, 23 shows up twice and 37 not at all. I handle this with `uniq sort { $a <=> $b }`

, taking `uniq`

(as well as `product`

) from the favored package, List::Util

I pulled out my less-cool older `is_prime`

, because Abigail’s code cause perl to complain about too much recursion. (**“This Looks Like A Job For…!**) My `is_prime`

is all about the iteration because, in this context, it makes sense.

#### Show Me The Code

```
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };
use List::Util qw{ product uniq };
my $c = 1;
my @fortune;
my @prime;
OUTER: while ( $c < 40 && scalar @fortune < 8 ) {
$c++;
if ( is_prime($c) ) {
push @prime, $c;
my $p = product @prime;
my $d = 1;
while ( $d < 50 ) {
$d++;
my $f = $p + $d;
my $is = is_prime($f);
if ($is) {
# the non-sorted, non-unique list of the first
# eight fortunate numbers contains 23 twice, so
# 1) we need to accomodate that possibility by
# starting each $d back at 2, and
# 2) we need to remove it before the outer while
# loop accounts for it
# so that's why $d=1 in the while loop and
# why we don't just push $d
@fortune = uniq sort { $a <=> $b } @fortune, $d;
next OUTER;
}
}
}
}
say 'FORTUNATE NUMBERS: ' . join ', ', @fortune;
# using my is_prime rather than Abigail's, because that
# one was giving me "too much recursion" errors.
sub is_prime ($n) {
for ( 2 .. sqrt $n ) { return 0 unless $n % $_ }
return 1;
}
```

```
$ ./ch-1.pl
FORTUNATE NUMBERS: 3, 5, 7, 13, 17, 19, 23, 37
```