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


with javascript_semantics
function pisano_period(integer m)
-- Calculates the Pisano period of 'm' from first principles. (copied from Go)
    integer p = 0, c = 1
    for i=0 to m*m-1 do
        {p, c} = {c, mod(p+c,m)}
        if p == 0 and c == 1 then
            return i + 1
        end if
    end for
    return 1
end function
 
function pisanoPrime(integer p, k)
    if not is_prime(p) or k=0 then ?9/0 end if
    return power(p,k-1)*pisano_period(p)
end function
 
function pisano(integer m)
-- Calculates the Pisano period of 'm' using pisanoPrime.
    if m=1 then return 1 end if
    sequence s = prime_factors(m, true, get_maxprime(m))&0,
             pps = {}
    integer k = 1, p = s[1]
    for i=2 to length(s) do
        integer n = s[i]
        if n!=p then
            pps = append(pps,pisanoPrime(p,k))
            {k,p} = {1,n}
        else
            k += 1
        end if
    end for
    return lcm(pps)
end function
 
procedure p(integer k, lim)
-- test harness
    printf(1,"pisanoPrimes")
    integer pdx = 1, c = 0
    while true do
        integer p = get_prime(pdx)
        if p>=lim then exit end if
        c += 1
        if c=7 then puts(1,"\n            ") c = 1
        elsif pdx>1 then puts(1,", ") end if
        printf(1,"(%3d,%d)=%3d",{p,k,pisanoPrime(p,k)})
        pdx += 1
    end while
    printf(1,"\n")
end procedure
p(2,15)
p(1,180)
 
sequence p180 = {}
for n=1 to 180 do p180 &= pisano(n) end for
printf(1,"pisano(1..180):\n")
pp(p180,{pp_IntFmt,"%4d",pp_IntCh,false})
