pisano_periods_of_lucas_U_sequence.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 08 August 2018
# https://github.com/trizen

# Efficient algorithm for computing the Pisano period: period of Fibonacci
# numbers mod `n`, assuming that the factorization of `n` can be computed.

# This algorithm assumes that Wall-Sun-Sun primes do not exist.

# See also:
#   https://oeis.org/A001175
#   https://oeis.org/A053031
#   https://en.wikipedia.org/wiki/Pisano_period
#   https://en.wikipedia.org/wiki/Wall%E2%80%93Sun%E2%80%93Sun_prime

func pisano_period_pp(P, Q, p, k=1) {
    (p - kronecker(P*P - 4*Q, p)).divisors.first_by {|d| lucasUmod(P, Q, d, p) == 0 } * p**(k-1)
}

func pisano_period(n, P=1, Q=-1) {

    return 0 if (n <= 0)
    return 1 if (n == 1)

    var d = n.factor_map {|p,k| pisano_period_pp(P, Q, p, k) }.lcm

    3.times {|k|
        var t = d<<k
        if ((lucasUmod(P, Q, t, n) == 0) && (lucasUmod(P, Q, t+1, n) == 1)) {
            return t
        }
    }

    die "Error for n = #{n} with P = #{P} and Q = #{Q}"
}

say {|n| pisano_period(n, 1, -1) }.map(1..30)       # Periods of Fibonacci numbers
say {|n| pisano_period(n, 2, -1) }.map(1..30)       # Periods of Pell numbers
say {|n| pisano_period(n, 3, -1) }.map(1..30)       # Periods of 3-Fibonacci numbers

__END__
[1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120]
[1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24]
[1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12]