The Fibonacci sequence taken modulo 2 is a periodic sequence of period 3 : 0, 1, 1, 0, 1, 1, ...

For any integer n, the Fibonacci sequence taken modulo n is periodic and the length of the periodic cycle is referred to as the Pisano period.

Prime numbers are straightforward; the Pisano period of a prime number p is simply: pisano(p). The Pisano period of a composite number c may be found in different ways. It may be calculated directly: pisano(c), which works, but may be time consuming to find, especially for larger integers, or, it may be calculated by finding the least common multiple of the Pisano periods of each composite component.



E.G.

Given a Pisano period function: pisano(x), and a least common multiple function lcm(x, y):

   pisano(m × n) is equivalent to lcm(pisano(m), pisano(n)) where  m  and  n  are coprime

A formulae to calculate the pisano period for integer powers   k   of prime numbers   p   is:

   pisano(pk) == p(k-1)pisano(p) 

The equation is conjectured, no exceptions have been seen.

If a positive integer   i   is split into its prime factors,   then the second and first equations above can be applied to generate the pisano period.



Task
Write 2 functions: pisanoPrime(p,k) and pisano(m).

pisanoPrime(p,k) should return the Pisano period of pk where p is prime and k is a positive integer.

pisano(m) should use pisanoPrime to return the Pisano period of m where m is a positive integer.

Print pisanoPrime(p,2) for every prime lower than 15.

Print pisanoPrime(p,1) for every prime lower than 180.

Print pisano(m) for every integer from 1 to 180.



Related tasks
  Fibonacci sequence
  Prime decomposition
  Least common multiple


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