Pisa Party

Wherein we look for something unique as we slowly add to the products of what came before..

THE WEEKLY CHALLENGE – PERL & RAKU #155 Task 2

---

“Pizza makes me think that anything is possible.”

— Henry Rollins

---

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.

ANALYSIS

Ok, so let’s see… we’ll need a list of Fibonacci numbers.

Check — no trouble there.

Then, thinking in terms of a general solution, we will need to make mappings of this list of Fibonaccis taken modulo various numbers, and from these compile a new set of lists, one for each modulo value.

And then comes the hard part: spotting the cycles.

METHOD

You know what’s really good for, you know, matching patterns? Some sort of pattern matcher, of course. And we happen to have an excellent one of these — a world-class model, an inspiration for all the others — in the Perl regular expression engine.

So what we do here is construct a string from the array of remainders. Then because the first fibonacci number is 0, the first character in this concatenated string will always be 0, and as such the first character of any repeated segment will likewise also be 0.

This is good so far, but we can’t just search spans from zero to zero though, as there may be other incidences of zero digits interspersed within the sequence of remainders before the repeat cycle. We cannot, unfortunately, make the presumption that there are not.

So what we will need to do then is to match a group: an incidence of a 0 followed by some minimal positive number of characters, with this match captured and followed immediately by the same matched group. In the absence of any larger, epicyclic structure — sets of cycling groups that themselves vary in a larger pattern — this will find our repeated sections.

We can then record the length of the captured sub-expression to an array of Pisano periods for output.

So what can go wrong?

If the recorded period is 0, that’s not a possible outcome as sequential differences in a modulo operation cannot be the same outside of some trivial edge-cases that are easily discounted here. What we’re really recording, then, must be the failure of a match. As we’re assured the cycle will eventually repeat, this requires the list of Fibonacci numbers to be extended to provide enough values to match two complete cycles.

As the Fibonacci list is extended, though, the values get large quickly. Fortunately the simplicity of the underlying math in constructing the sequence is not complex, and so adding the directive use bigint does not cause undue burden to the processing time. Everything still moves along at a rapid pace.

Well, except when everything breaks after 10 values. That is… unfortunate.

The Pisanos for 2 through 9 check out just fine, but after that the values start to stray — a little at the start and then more and more. The problem here is that our concatenation worked fine for single-digit remainders, but gets thrown off starting at modulo 11, when 10 becomes a valid result. We can no longer simply count characters, as a single instance of 10 will count as 2 instead of 1 and there we have it.

I see two ways to resolve this. One way would be to extend the concatenation to make the number of characters allocated to each remainder consistent, say by left-padding with some arbitrary null (we’d use 0 but that value is already kind of busy). This would deliver a character count in some multiple of the actual period, and we could divide the count by our fixed remainder length to arrive at the final value. This is a perfectly good strategy, albeit both a little complicated and producing very long strings. Peeking ahead we see one of the distant results is 120.

Doubling the characters could be done with a mapping operation of some sort and allow us to look for Pisanos up to 99. The strings would however get… big.

On the other hand we could quickly map the values 0 through 35 to an alphanumeric character set. Each value gets one character again. We don’t care what the numerical representation is, after all, only that each symbol be unique so we can match a pattern. This would allow us access to he Pisanos up to 35 which seems like a reasonable ask. Actually there’s no reason not to tack on a lowercase alphabet, extending our reach another 26 places, as again we don’t care what characters we’re using. As long as we can produce more tokens we can continue this concept as far as we wish.

It appears that 256 Fibonaccis are enough to compute the Pisanos up to 61. I think that’s enough and we’ll stop there.

PERL 5 SOLUTION

use bigint;

sub fibonaccis ( $count ) {
## generates sequence of Fibonacci numbers up to and not greater than limit
    state @fs = (0,1);
    push  @fs, $fs[-1] + $fs[-2] while @fs <= $count;
    return @fs;
}


my @fs = fibonaccis(256);
my @pisas;

for my $mod (2..61) {
    my $modstr = join '', 
                 map { (0..9, "A".."Z", "a".."z")[$_] } 
                 map { $_ % $mod } 
                 @fs;

    $modstr =~ /(0.+?)\1/;
    push @pisas, length $1;
}

say join ', ', @pisas;

Raku Solution

unit sub MAIN ($fibs = 256) ;

my @fs = ( 0, 1, * + * ... * )[^$fibs];
my @pisas = gather {
    for 2..35 -> $mod {
        $_ = @fs.map({$_ % $mod}) 
                .map({ (|(0..9), |('A'..'Z'))[$_] }) 
                .join ;
        /(0.+?){}$0/ ;
        take $0.chars;
    }
}


for @pisas.kv -> $p, $q {
    say ($p+2, $q).fmt("%3d", ' → ');
}

For anyone curious, here’s the Pisano numbers up to 35:

  2 →   3
  3 →   8
  4 →   6
  5 →  20
  6 →  24
  7 →  16
  8 →  12
  9 →  24
 10 →  60
 11 →  10
 12 →  24
 13 →  28
 14 →  48
 15 →  40
 16 →  24
 17 →  36
 18 →  24
 19 →  18
 20 →  60
 21 →  16
 22 →  30
 23 →  48
 24 →  24
 25 → 100
 26 →  84
 27 →  72
 28 →  48
 29 →  14
 30 → 120
 31 →  30
 32 →  48
 33 →  40
 34 →  36
 35 →  80