Task — 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.

Examples

Example 1:
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

Perl is really good at patterns, so I approached this as follows:

• Create the Fibonacci series up to a big number (big)
• Create a string by concatenating the members of the series, modulo n
• Loop over 2 to a medium-sized number - this is the length of the repeat, pp
• So the unit that (maybe) repeats comprises chars 0 to pp-1 of the string
• Make another string containing enough copies of the unit to be longer than big, and then truncate it to big characters

We have a result if 'another string' is the same as 'string'.

In order to cope with n being more than 10, all the moduli are represented as a single character, eg for n=16 the usual 0-9A-F but then running through to Z and then a-z, so that the algorithm can cope with n up to 62. Again, the larger members of the series (beyond the 94th) exceed the capacity of 64 bits, so Bigint is needed again.

And just to show that it works, I set big to be 1000, pp to go up to 40, and it runs in a few seconds up to p(62), which is 30 as per the OEIS.

And there's always a however. If the modulo sequence for some number, say, goes 01234012340123401234 ... 44 with the 5 character sequence repeating 200 times followed by 44, my algorithm will not catch that. It could be that the repeat is 1001 characters long. But perhaps someone has proved that that won't happen - ie that there is an upper bound for the length of the repeat?

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-03-09
# PWC 155 task 2

use v5.28;
use strict;
use warnings;
use utf8;
use Math::Prime::Util 'is_prime';
use Math::BigInt lib => 'GMP';
binmode STDOUT, ':utf8';

my (@fib, $last_term, $max_period, $n, @n, $pp, $string, $unit, $match, $ls);

$last_term = 5000;   # consider this number of terms in the series
$max_period = 300;    # consider periods up to this length

# velues of n to test (max = 62 - see blog)
@n = (2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 62);   # n's to test (max = 62)

make_fib();   # create Fibonacci series using BigInts

for $n (@n) {                      # testing the nth Pisano period

    # stringify the moduli of the fib series
    $string = make_string($n);
    
    # now look for repeating patterns pp characters long
    for $pp (1 .. $max_period) {
        
        # this is the repating unit
        $unit = substr($string, 0, $pp);
        
        # and this is a repetition of the repeating unit as long as the stringified moduli
        $match = substr($unit x ($last_term / $pp + 1), 0, $last_term + 1);
        
        # and if they match we have a result
        next unless $match eq $string;
        say qq[π($n) = $pp];
        last;
    }
}

sub make_fib {
    
    # this is the usual formula expresed in BigInt-ish
    $fib[0] = Math::BigInt->new(0); 
    $fib[1] = Math::BigInt->new(1); 
    
    for my $j (2 .. $last_term) {
        $fib[$j] = Math::BigInt->new($fib[$j - 1]);
        $fib[$j]->badd($fib[$j - 2]);
    }
}

sub make_string {
    
    # makes a string of symbols where the j'th symbol represents the value mod n
    # of the j'th item in the fibonacci series
    my ($item, $char, $string);
    for my $j (0 .. $last_term) {
        $item = Math::BigInt->new($fib[$j]);   # fib number
        $item->bmod($_[0]);                    # ... modulo n
        $char = substr('01234567890ABCDEFGHIJKLMONPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', $item, 1);
        $string .= $char;
    }
    return $string;
}       

Output

π(2) = 3
π(3) = 8
π(4) = 6
π(5) = 20
π(6) = 24
π(7) = 16
π(8) = 12
π(9) = 24
π(10) = 60
π(20) = 60
π(30) = 120
π(40) = 60
π(50) = 300
π(60) = 120
π(62) = 30