Pisano period: Difference between revisions

Line 2:

The [[wp:Fibonacci_Number|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 [[wp:Pisano_period|Pisano period]].

For any integer n, the Fibonacci sequence taken modulo n is periodic and the length of the periodic cycle is referred to as the [[wp:Pisano_period|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 [[wp:Least common multiple|least common multiple]] of the Pisano periods of each composite component.

if we have the function pisano(x) return the pisano period using modulo x, (e.g. pisano(2) = 3) and [[wp:Least common multiple|lcm]](x, y) return the least common multiple between x and y; then if m and n are [[wp:Coprime integers|coprime]], pisano(m*n) = lcm(pisano(m),pisano(n)).

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

'''pisano(c)''' is equivalent to '''lcm(pisano(m), pisano(n))''' where '''c''' == '''m × 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 p<sup>k</sup> where p is prime and k is a positive integer.

pisanoPrime(p,k) should return the Pisano period of p<sup>k</sup> 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.

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

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