Pisano period: Difference between revisions

m
→‎{{header|Phix}}: syntax coloured
(Added 11l)
m (→‎{{header|Phix}}: syntax coloured)
Line 1,279:
 
=={{header|Phix}}==
<!--<lang Phix>function pisano_period(integer mphixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- Calculates the Pisano period of 'm' from first principles. (copied from Go)
<span style="color: #008080;">function</span> <span style="color: #000000;">pisano_period</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
integer p = 0, c = 1
<span style="color: #000080;font-style:italic;">-- Calculates the Pisano period of 'm' from first principles. (copied from Go)</span>
for i=0 to m*m-1 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
{p, c} = {c, mod(p+c,m)}
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">*</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
if p == 0 and c == 1 then
<span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)}</span>
return i + 1
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return 1
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function pisanoPrime(integer p, k)
if not is_prime(p) or k=0 then ?9/0 end if
<span style="color: #008080;">function</span> <span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
return power(p,k-1)*pisano_period(p)
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">pisano_period</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function pisano(integer m)
-- Calculates the Pisano period of 'm' using pisanoPrime.
<span style="color: #008080;">function</span> <span style="color: #000000;">pisano</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
if m=1 then return 1 end if
<span style="color: #000080;font-style:italic;">-- Calculates the Pisano period of 'm' using pisanoPrime.</span>
sequence s = prime_factors(m, true, get_maxprime(m))&0,
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
pps = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">get_maxprime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">))&</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
integer k = 1, p = s[1]
<span style="color: #000000;">pps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for i=2 to length(s) do
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
integer n = s[i]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if n!=p then
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
pps = append(pps,pisanoPrime(p,k))
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">p</span> <span style="color: #008080;">then</span>
{k,p} = {1,n}
<span style="color: #000000;">pps</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">))</span>
else
<span style="color: #0000FF;">{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
k += 1
<span style="color: #008080;">else</span>
end if
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return lcm(pps)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure p(integer k, lim)
-- test harness
<span style="color: #008080;">procedure</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
printf(1,"pisanoPrimes")
<span style="color: #000080;font-style:italic;">-- test harness</span>
integer pdx = 1, c = 0
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pisanoPrimes"</span><span style="color: #0000FF;">)</span>
while true do
<span style="color: #004080;">integer</span> <span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer p = get_prime(pdx)
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if p>=lim then exit end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pdx</span><span style="color: #0000FF;">)</span>
c += 1
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if c=7 then puts(1,"\n ") c = 1
<span style="color: #000000;">c</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
elsif pdx>1 then puts(1,", ") end if
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">7</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n "</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
printf(1,"(%3d,%d)=%3d",{p,k,pisanoPrime(p,k)})
<span style="color: #008080;">elsif</span> <span style="color: #000000;">pdx</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
pdx += 1
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(%3d,%d)=%3d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pisanoPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)})</span>
end while
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
printf(1,"\n")
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end procedure
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
p(2,15)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
p(1,180)
<span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">180</span><span style="color: #0000FF;">)</span>
sequence p180 = {}
for n=1 to 180 do p180 &= pisano(n) end for
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p180</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
printf(1,"pisano(1..180):\n")
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">180</span> <span style="color: #008080;">do</span> <span style="color: #000000;">p180</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">pisano</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
pp(p180,{pp_IntFmt,"%4d",pp_IntCh,false})</lang>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pisano(1..180):\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p180</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
<!--</lang>-->
{{out}}
<pre>
7,805

edits