Pisano period

func pisano_period_pp(p,k) is cached {
 
    assert(k.is_pos,   "k = #{k} must be positive")
    assert(p.is_prime, "p = #{p} must be prime")
 
    var (a, b, n) = (0, 1, p**k)
 
    1..Inf -> first_by {
        (a, b) = (b, (a+b) % n)
        (a == 0) && (b == 1)
    }
}
 
func pisano_period(n) {
    n.factor_map {|p,k| pisano_period_pp(p, k) }.lcm
}
 
say "Pisano periods for squares of primes p <= 15:"
say  15.primes.map {|p| pisano_period_pp(p, 2) }
 
say "\nPisano periods for primes p <= 180:"
say 180.primes.map {|p| pisano_period_pp(p, 1) }

say "\nPisano periods for integers n from 1 to 180:"
say pisano_period.map(1..180)

Output:

By assuming that Wall-Sun-Sun primes do not exist, we can compute the Pisano period more efficiently, as illustrated below on Fermat numbers F_n = 2^(2^n) + 1:

Output:

PreviousPiprimesNextPlasma effect

Last updated

Was this helpful?