41 lines
1.3 KiB
Python
41 lines
1.3 KiB
Python
from sympy import isprime, lcm, factorint, primerange
|
||
from functools import reduce
|
||
|
||
|
||
def pisano1(m):
|
||
"Simple definition"
|
||
if m < 2:
|
||
return 1
|
||
lastn, n = 0, 1
|
||
for i in range(m ** 2):
|
||
lastn, n = n, (lastn + n) % m
|
||
if lastn == 0 and n == 1:
|
||
return i + 1
|
||
return 1
|
||
|
||
def pisanoprime(p, k):
|
||
"Use conjecture π(p ** k) == p ** (k − 1) * π(p) for prime p and int k > 1"
|
||
assert isprime(p) and k > 0
|
||
return p ** (k - 1) * pisano1(p)
|
||
|
||
def pisano_mult(m, n):
|
||
"pisano(m*n) where m and n assumed coprime integers"
|
||
return lcm(pisano1(m), pisano1(n))
|
||
|
||
def pisano2(m):
|
||
"Uses prime factorization of m"
|
||
return reduce(lcm, (pisanoprime(prime, mult)
|
||
for prime, mult in factorint(m).items()), 1)
|
||
|
||
|
||
if __name__ == '__main__':
|
||
for n in range(1, 181):
|
||
assert pisano1(n) == pisano2(n), "Wall-Sun-Sun prime exists??!!"
|
||
print("\nPisano period (p, 2) for primes less than 50\n ",
|
||
[pisanoprime(prime, 2) for prime in primerange(1, 50)])
|
||
print("\nPisano period (p, 1) for primes less than 180\n ",
|
||
[pisanoprime(prime, 1) for prime in primerange(1, 180)])
|
||
print("\nPisano period (p) for integers 1 to 180")
|
||
for i in range(1, 181):
|
||
print(" %3d" % pisano2(i), end="" if i % 10 else "\n")
|