Pisano period: Difference between revisions
Content deleted Content added
rewording for clarity. |
Thundergnat (talk | contribs) Attempt at rephrasing the task header to be clearer. |
||
Line 2: | Line 2: | ||
The [[wp:Fibonacci_Number|Fibonacci sequence]] taken modulo 2 is a periodic sequence of period 3 : 0, 1, 1, 0, 1, 1, ... |
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 |
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 |
;Task |
||
Write 2 functions: pisanoPrime(p,k) and pisano(m). |
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) |
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. |
Print pisanoPrime(p,2) for every prime lower than 15. |