Pisano period
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 period is called the Pisano period.
Let call Pisano, the Pisano period (Pisano(2) = 3). If m and n are coprime, Pisano(m*n) = lcm(Pisano(m),Pisano(n)).
Therefore calculate the Pisano period of an integer m is accomplished by calculating the Pisano periods of the prime powers in the prime decomposition of m.
- Task
Write 2 functions: pisanoPrime(p,k) and pisano(m).
pisanoPrime(p,k) return the Pisano period of pk where p is prime and k is a positive integer.
pisano(m) uses pisanoPrime to return the Pisano period of m where m is a positive integer.
Print pisanoPrime(p,1) and pisanoPrime(p,2) for every prime lower than 100.
Print pisano(m) for every integer from 2 to 200.
- Related tasks