#!/usr/bin/perl

use strict;
use warnings;
use v5.12;

use Math::BigInt "blcm";

my $verbose = q/TRUE/;

sub test {

    my $p = shift;

    # Period of this sequence according to our hypothesis.
    my $Hperiod = blcm(1 .. ($p - 1));

    # Generate the first N terms of the sequence.
    my $N = 4 * $Hperiod;

    my @x = (1);

    for my $i (0 .. ($N)) {
        $x[ $i + 1 ] = $p - 1 - (($p * $i - 1) % $x[$i]);
    }

    # Stringize.
    my $xstr = join ',', @x;

    # Use regular expressions to check that the sequence has a periodicity.
    my $term = qr/\d+,/;

    my $pattern = qr/(?<subsequence>${term}{$Hperiod}) 
                    \g{subsequence}\g{subsequence}/x;

    return 0 unless $xstr =~ /$pattern/;

    # Success!
    my $subseq = $+{'subsequence'};

    # Find out the index from where the periodicity begins.
    my $non_periodic = substr $xstr, 0, $-[0];
    my $index = () = $non_periodic =~ /,/g;

    # Print these details.
    if ($verbose =~ /TRUE/) {
        say "-" x 65;
        say "prime = $p; lcm(" . ($p - 1) . " .. 1) = $Hperiod";
        say "";
        say "First $N terms: {x_i} = $xstr";
        say "";
        say "Repeating sub-sequence: $subseq start\@index $index";
    }

    return 1;
}

for my $p (2, 3, 5, 7, 11) {
    my $result = (test($p) ? q/pass/ : q/FAIL/);
    say "$result for p = $p";
}