Pisano period: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) →{{header|Perl 6}}: efficiency twiddles, not really necessary for the task |
|||
Line 467: | Line 467: | ||
18 72 240 60 168 316 78 216 60 48 24 328 120 40 168 |
18 72 240 60 168 316 78 216 60 48 24 328 120 40 168 |
||
336 48 28 180 72 264 348 168 80 30 232 132 178 120</pre> |
336 48 28 180 72 264 348 168 80 30 232 132 178 120</pre> |
||
=={{header|Phix}}== |
|||
<lang Phix>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. |
|||
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) |
|||
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=2 to 180 do p180 &= pisano(n) end for |
|||
printf(1,"pisano(2..180):\n") |
|||
pp(p180,{pp_IntFmt,"%4d",pp_IntCh,false})</lang> |
|||
{{out}} |
|||
<pre> |
|||
pisanoPrimes( 2,2)= 6, ( 3,2)= 24, ( 5,2)=100, ( 7,2)=112, ( 11,2)=110, ( 13,2)=364 |
|||
pisanoPrimes( 2,1)= 3, ( 3,1)= 8, ( 5,1)= 20, ( 7,1)= 16, ( 11,1)= 10, ( 13,1)= 28 |
|||
( 17,1)= 36, ( 19,1)= 18, ( 23,1)= 48, ( 29,1)= 14, ( 31,1)= 30, ( 37,1)= 76 |
|||
( 41,1)= 40, ( 43,1)= 88, ( 47,1)= 32, ( 53,1)=108, ( 59,1)= 58, ( 61,1)= 60 |
|||
( 67,1)=136, ( 71,1)= 70, ( 73,1)=148, ( 79,1)= 78, ( 83,1)=168, ( 89,1)= 44 |
|||
( 97,1)=196, (101,1)= 50, (103,1)=208, (107,1)= 72, (109,1)=108, (113,1)= 76 |
|||
(127,1)=256, (131,1)=130, (137,1)=276, (139,1)= 46, (149,1)=148, (151,1)= 50 |
|||
(157,1)=316, (163,1)=328, (167,1)=336, (173,1)=348, (179,1)=178 |
|||
pisano(2..180): |
|||
{ 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, |
|||
36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, |
|||
48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88, 30, 120, 48, |
|||
32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, |
|||
30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, |
|||
80, 168, 78, 120, 216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, |
|||
48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, |
|||
72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120, 110, |
|||
60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, |
|||
276, 48, 46, 240, 32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, |
|||
36, 72, 240, 60, 168, 316, 78, 216, 240, 48, 216, 328, 120, 40, 168, |
|||
336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120} |
|||
</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |