Rosetta Code

Cyclotomic polynomial: Difference between revisions

Page Discussion

Cyclotomic polynomial (view source)

Revision as of 17:54, 10 January 2022

28,154 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
(add fermat)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 3,810:
{{trans|Julia}}
Uses several routines from [[Polynomial_long_division#Phix]], tweaked slightly to check remainder is zero and trim the quotient.
<!--<lang Phix>(phixonline)-->
<lang Phix>-- demo\rosetta\Cyclotomic_Polynomial.exw
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Cyclotomic_Polynomial.exw</span>
function degree(sequence p)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
for i=length(p) to 1 by -1 do
<span style="color: #008080;">function</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
if p[i]!=0 then return i end if
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <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: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function poly_div(sequence n, d)
while length(d)<length(n) do d &=0 end while
<span style="color: #008080;">function</span> <span style="color: #000000;">poly_div</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
integer dn = degree(n),
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)<</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">&=</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
dd = degree(d)
<span style="color: #004080;">integer</span> <span style="color: #000000;">dn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
if dd<0 then throw("divide by zero") end if
<span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
sequence quot = repeat(0,dn)
<span style="color: #008080;">if</span> <span style="color: #000000;">dd</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">throw</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"divide by zero"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while dn>=dd do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">quot</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dn</span><span style="color: #0000FF;">)</span>
integer k = dn-dd
<span style="color: #008080;">while</span> <span style="color: #000000;">dn</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">dd</span> <span style="color: #008080;">do</span>
integer qk = n[dn]/d[dd]
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dn</span><span style="color: #0000FF;">-</span><span style="color: #000000;">dd</span>
quot[k+1] = qk
<span style="color: #004080;">integer</span> <span style="color: #000000;">qk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dn</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">]</span>
sequence d2 = d[1..length(d)-k]
<span style="color: #000000;">quot</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: #0000FF;">=</span> <span style="color: #000000;">qk</span>
for i=1 to length(d2) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
n[-i] -= d2[-i]*qk
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #004080;">integer</span> <span style="color: #000000;">mi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">i</span>
dn = degree(n)
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">qk</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- return {quot,n} -- (n is now the remainder)
<span style="color: #000000;">dn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if n!=repeat(0,length(n)) then ?9/0 end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
while quot[$]=0 do quot = quot[1..$-1] end while
<span style="color: #000080;font-style:italic;">-- return {quot,n} -- (n is now the remainder)</span>
return quot
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</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;">while</span> <span style="color: #000000;">quot</span><span style="color: #0000FF;">[$]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> <span style="color: #000000;">quot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">quot</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">quot</span>
function poly(sequence si)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- display helper
string r = ""
<span style="color: #008080;">function</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
for t=length(si) to 1 by -1 do
<span style="color: #000080;font-style:italic;">-- display helper</span>
integer sit = si[t]
<span style="color: #004080;">string</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
if sit!=0 then
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
if sit=1 and t>1 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">sit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
r &= iff(r=""? "":" + ")
<span style="color: #008080;">if</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
elsif sit=-1 and t>1 then
<span style="color: #008080;">if</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
r &= iff(r=""?"-":" - ")
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">?</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">)</span>
else
<span style="color: #008080;">elsif</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
if r!="" then
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" - "</span><span style="color: #0000FF;">)</span>
r &= iff(sit<0?" - ":" + ")
<span sit style="color: abs(sit)#008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sit</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" - "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">)</span>
r &= sprintf("%d",sit)
<span style="color: #000000;">sit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sit</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
r &= iff(t>1?"x"&iff(t>2?sprintf("^%d",t-1):""):"")
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sit</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"x"</span><span style="color: #0000FF;">&</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"^%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</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: #008000;">""</span><span style="color: #0000FF;">)</span>
if r="" then r="0" end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return r
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"0"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
--</Polynomial_long_division.exw>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
--# memoize cache for recursive calls
<span style="color: #000080;font-style:italic;">--&lt;/Polynomial_long_division.exw&gt;
constant cyclotomics = new_dict({{1,{-1,1}},{2,{1,1}}})
--# memoize cache for recursive calls</span>
function cyclotomic(integer n)
<span style="color: #008080;">constant</span> <span style="color: #000000;">cyclotomics</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}})</span>
--
-- Calculate nth cyclotomic polynomial.
<span style="color: #008080;">function</span> <span style="color: #000000;">cyclotomic</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
-- See wikipedia article at bottom of section /wiki/Cyclotomic_polynomial#Fundamental_tools
<span style="color: #000080;font-style:italic;">--
-- The algorithm is reliable but slow for large n > 1000.
-- Calculate the nth cyclotomic polynomial.
--
-- See wikipedia article at bottom of section /wiki/Cyclotomic_polynomial#Fundamental_tools
sequence c
-- The algorithm is reliable but slow for large n &gt; 1000.
if getd_index(n,cyclotomics)!=NULL then
--</span>
c = getd(n,cyclotomics)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span>
else
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cyclotomics</span><span style="color: #0000FF;">)!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
if is_prime(n) then
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cyclotomics</span><span style="color: #0000FF;">)</span>
c = repeat(1,n)
<span style="color: #008080;">else</span>
else -- recursive formula seen in wikipedia article
<span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
c = -1&repeat(0,n-1)&1
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</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>
sequence f = factors(n,-1)
<span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- recursive formula seen in wikipedia article</span>
for i=1 to length(f) do
<span style="color: #000000;">c</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: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">1</span>
c = poly_div(c,cyclotomic(f[i]))
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end if
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cyclotomic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])))</span>
setd(n,c,cyclotomics)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return c
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cyclotomics</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span>
for i=1 to 30 do
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
sequence z = cyclotomic(i)
string s = poly(z)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">30</span> <span style="color: #008080;">do</span>
printf(1,"cp(%2d) = %s\n",{i,s})
<span style="color: #004080;">sequence</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cyclotomic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
if i>1 and z!=reverse(z) then ?9/0 end if -- sanity check
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
end for
<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;">"cp(%2d) = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</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> <span style="color: #000080;font-style:italic;">-- sanity check</span>
integer found = 0, n = 1, cheat = 0
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
sequence fn = repeat(false,10),
nxt = {105,385,1365,1785,2805,3135,6545,6545,10465,10465}
<span style="color: #004080;">integer</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cheat</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
atom t1 = time()+1
<span style="color: #004080;">sequence</span> <span style="color: #000000;">fn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span>
puts(1,"\n")
<span style="color: #000000;">nxt</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">105</span><span style="color: #0000FF;">,</span><span style="color: #000000;">385</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1365</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1785</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2805</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3135</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6545</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6545</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10465</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10465</span><span style="color: #0000FF;">}</span>
while found<10 do
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
sequence z = cyclotomic(n)
<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>
for i=1 to length(z) do
<span style="color: #008080;">while</span> <span style="color: #000000;">found</span><span style="color: #0000FF;"><</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">5</span><span style="color: #0000FF;">:</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
atom azi = abs(z[i])
<span style="color: #004080;">sequence</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cyclotomic</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if azi>=1 and azi<=10 and fn[azi]=0 then
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
printf(1,"cp(%d) has a coefficient with magnitude %d\n",{n,azi})
<span style="color: #004080;">atom</span> <span style="color: #000000;">azi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
cheat = azi -- (comment this out to prevent cheating!)
<span style="color: #008080;">if</span> <span style="color: #000000;">azi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">azi</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">10</span> <span style="color: #008080;">and</span> <span style="color: #000000;">fn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">azi</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
found += 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;">"cp(%d) has a coefficient with magnitude %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">azi</span><span style="color: #0000FF;">})</span>
fn[azi] = true
<span style="color: #000000;">cheat</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">azi</span> <span style="color: #000080;font-style:italic;">-- (comment this out to prevent cheating!)</span>
t1 = time()+1
<span style="color: #000000;">found</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #000000;">fn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">azi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
end for
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
if cheat then {n,cheat} = {nxt[cheat],0} else n += iff(n=1?4:10) end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if time()>t1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
printf(1,"working (%d) ...\r",n)
<span style="color: #008080;">if</span> <span style="color: #000000;">cheat</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cheat</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nxt</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cheat</span><span style="color: #0000FF;">],</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">else</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">4</span><span style="color: #0000FF;">:</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
t1 = time()+1
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
end if
<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;">"working (%d) ...\r"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end while</lang>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</lang>-->
{{out}}
If you disable the cheating, and if in a particularly self harming mood replace it with n+=1, you will get exactly the same output, eventually.<br>
Petelomax
7,795

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/297840"