# 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)

for k in (1..Inf) {
(a, b) = (b, (a+b) % n)

if ([a,b] == [0,1]) {
return k
}
}
}

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 2 to 180:"
say pisano_period.map(2..180)
``````

#### Output:

``````Pisano periods for squares of primes p <= 15:
[6, 24, 100, 112, 110, 364]

Pisano periods for primes p <= 180:
[3, 8, 20, 16, 10, 28, 36, 18, 48, 14, 30, 76, 40, 88, 32, 108, 58, 60, 136, 70, 148, 78, 168, 44, 196, 50, 208, 72, 108, 76, 256, 130, 276, 46, 148, 50, 316, 328, 336, 348, 178]

Pisano periods for integers n from 2 to 180:
[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, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120]
``````

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:

``````func pisano_period_pp(p, k=1) {
(p - kronecker(5, p)).divisors.first_by {|d| fibmod(d, p) == 0 } * p**(k-1)
}

func pisano_period(n) {

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

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

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

for k in (1..8) {
say ("Pisano(F_#{k}) = ", pisano_period(2**(2**k) + 1))
}
``````

#### Output:

``````Pisano(F_1) = 20
Pisano(F_2) = 36
Pisano(F_3) = 516
Pisano(F_4) = 14564
Pisano(F_5) = 2144133760
Pisano(F_6) = 4611702838532647040
Pisano(F_7) = 28356863910078205764000346543980814080
Pisano(F_8) = 3859736307910542962840356678888855900560939475751238269689837480239178278912
``````