Rosetta Code

Powerful numbers: Difference between revisions

Page Discussion

Powerful numbers (view source)

Revision as of 21:35, 11 June 2021

38,168 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 686:
{{libheader|Phix/mpfr}}
===priority queue===
Tried a slightly different approach, but it gets 7/10 at best on performance., and simply not worth attempting under pwa/p2js
<!--<lang Phix>include mpfr.e(notonline)-->
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>
 
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
integer pq = NULL -- data is the prime powers, eg {2,2} for 2^2*3^2
-- priority is the mpz of that, eg/ie 36
<span style="color: #004080;">integer</span> <span style="color: #000000;">pq</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span> <span style="color: #000080;font-style:italic;">-- data is the prime powers, eg {2,2} for 2^2*3^2
 
-- priority is the mpz of that, eg/ie 36</span>
procedure padd(mpz n, np, sequence s)
if pq=NULL then
<span style="color: #008080;">procedure</span> <span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">np</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
pq = pq_new(MIN_HEAP,routine_id("mpz_cmp"))
<span style="color: #008080;">if</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">pq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(</span><span style="color: #004600;">MIN_HEAP</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"mpz_cmp"</span><span style="color: #0000FF;">))</span>
if mpz_cmp(np,n)<=0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
pq_add({s,mpz_init_set(np)},pq)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)<=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
end if
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">)},</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure add_next(integer k, mpz n, p, sequence s)
mpz np = mpz_init()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">add_next</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: #004080;">mpz</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer l = length(s)
<span style="color: #004080;">mpz</span> <span style="color: #000000;">np</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
for i=1 to l do
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer ki = iff(s[i]=0?k:1)
<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;">l</span> <span style="color: #008080;">do</span>
mpz_ui_pow_ui(np,get_prime(i),ki)
<span style="color: #004080;">integer</span> <span style="color: #000000;">ki</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</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><span style="color: #000000;">0</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>
mpz_mul(np,np,p)
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ki</span><span style="color: #0000FF;">)</span>
s[i] += ki
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
padd(n,np,s)
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ki</span>
s[i] -= ki
<span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">ki</span>
mpz_ui_pow_ui(np,get_prime(l+1),k)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if l>0 and s[l]=k and s[1..l-1]==repeat(0,l-1) then
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
padd(n,np,0&s)
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">k</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</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;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
elsif s={} then
<span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">&</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
mpz_mul(np,np,p)
<span style="color: #008080;">elsif</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">={}</span> <span style="color: #008080;">then</span>
padd(n,np,s&k)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">np</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">&</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
function powerful(integer k, mpz n)
mpz prevp = mpz_init(1)
<span style="color: #008080;">function</span> <span style="color: #000000;">powerful</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: #004080;">mpz</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
sequence res = {prevp}
<span style="color: #004080;">mpz</span> <span style="color: #000000;">prevp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
add_next(k,n,prevp,{})
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">prevp</span><span style="color: #0000FF;">}</span>
while pq_size(pq) do
<span style="color: #000000;">add_next</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prevp</span><span style="color: #0000FF;">,{})</span>
{sequence s, mpz p} = pq_pop(pq)
<span style="color: #008080;">while</span> <span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if mpz_cmp(p,prevp)!=0 then
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">)</span>
res &= p
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prevp</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
add_next(k,n,p,s)
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">p</span>
prevp = p
<span style="color: #000000;">add_next</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</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>
end if
<span style="color: #000000;">prevp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
mpz p = mpz_init(10)
for k=2 to 10 do
<span style="color: #004080;">mpz</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
mpz_mul_si(p,p,10)
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
sequence s = powerful(k,p)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
integer l = length(s)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">powerful</span><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>
for i=1 to 5 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
s[i] = mpz_get_str(s[i])
<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;">5</span> <span style="color: #008080;">do</span>
s[-i] = mpz_get_str(s[-i])
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</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>
end for
<span style="color: #000000;">s</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</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>
s[6..-6] = {"..."}
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
s = join(s,",")
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">6</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"..."</span><span style="color: #0000FF;">}</span>
printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s})
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">","</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;">"%d %2d-powerful numbers &lt;= 10^%-2d : %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
puts(1,"\n")
--Not really fast enough, so only doing to k+5..k+8 for the first 4, but k+9 for last 5
<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 k=2 to 10 do
<span style="color: #000080;font-style:italic;">--Not really fast enough, so only doing to k+5..k+8 for the first 4, but k+9 for last 5</span>
sequence counts = {}
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
integer lim = k+min(k+3,9)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
mpz_set_si(p,1)
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span>
for j=0 to lim do
<span style="color: #7060A8;">mpz_set_si</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>
printf(1,"counting (%d/%d)...\r",{j,lim})
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
counts &= length(powerful(k,p))
<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;">"counting (%d/%d)...\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">})</span>
mpz_mul_si(p,p,10)
<span style="color: #000000;">counts</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerful</span><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>
end for
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %v\n",{k,lim,counts})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for</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;">"Counts of %2d-powerful numbers &lt;= 10^(0..%d) : %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 788 ⟶ 791:
{{trans|Go}} {{trans|Sidef}}
Significantly faster. The last few counts were wrong when using native ints/atoms, so I went gmp, which means it also works on 32-bit.
<!--<lang Phix>include mpfr.e(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">powerful</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">n</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: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">={},</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
function powerful(mpz n, integer k, sequence res={}, mpz m=NULL, integer r=0)
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
if m=NULL then
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
m = mpz_init(1)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
r = 2*k-1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
if r<k then
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fits_atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)?</span><span style="color: #7060A8;">mpz_get_atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">):</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)))</span>
res = append(res,iff(mpz_fits_atom(m)?mpz_get_atom(m):mpz_get_str(m)))
<span style="color: #008080;">else</span>
else
<span style="color: #004080;">mpz</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
mpz t = mpz_init()
<span style="color: #7060A8;">mpz_fdiv_q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t := floor(n/m)</span>
mpz_fdiv_q(t, n, m) -- t := floor(n/m)
<span style="color: #7060A8;">mpz_nthroot</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = floor(rth root of t)</span>
{} = mpz_root(t,t,r) -- t = floor(rth root of t)
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_fits_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</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>
if not mpz_fits_integer(t) then ?9/0 end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
integer lim = mpz_get_integer(t)
<span style="color: #008080;">for</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
for v=1 to lim do
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">k</span>
if r<=k
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">square_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_gcd_ui</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
or (square_free(v) and mpz_gcd_ui(NULL,m,v)=1) then
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t:= v^r</span>
mpz_ui_pow_ui(t,v,r) -- t:= v^r
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t*= m</span>
mpz_mul(t,t,m) -- t*= m
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">powerful</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
res = powerful(n, k, res, t, r-1)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end function
 
function powercount(mpz n, integer k, mpz m=NULL, integer r=0)
atom res = 0
if m=NULL then
m = mpz_init(1)
r = 2*k-1
end if
mpz t = mpz_init()
mpz_fdiv_q(t, n, m) -- t := floor(n/m)
{} = mpz_root(t,t,r) -- t = floor(rth root of t)
if not mpz_fits_integer(t) then ?9/0 end if
integer lim = mpz_get_integer(t)
if r<=k then
res += lim
else
for v=1 to lim do
if square_free(v) and mpz_gcd_ui(NULL,m,v)=1 then
mpz_ui_pow_ui(t,v,r) -- t:= v^r
mpz_mul(t,t,m) -- t*= m
res += powercount(n, k, t, r-1)
end if
end for
end if
return res
end function
<span style="color: #008080;">function</span> <span style="color: #000000;">powercount</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">n</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: #004080;">mpz</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
atom t0 = time()
<span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
mpz p = mpz_init(10)
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
for k=2 to 10 do
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpz_mul_si(p,p,10)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
sequence s = sort(powerful(p, k))
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer l = length(s)
<span style="color: #004080;">mpz</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
s[6..-6] = {"..."}
<span style="color: #7060A8;">mpz_fdiv_q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t := floor(n/m)</span>
s = ppf(s,{pp_FltFmt,"%d",pp_StrFmt,-1,pp_IntCh,false,pp_Maxlen,100})
<span style="color: #7060A8;">mpz_nthroot</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t = floor(rth root of t)</span>
printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s})
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_fits_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</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 for
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
puts(1,"\n")
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
for k=2 to 10 do
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">lim</span>
mpz_set_si(p,1)
<span style="color: #008080;">else</span>
sequence counts = {}
<span style="color: #008080;">for</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
for j=0 to k+9 do
<span style="color: #008080;">if</span> <span style="color: #7060A8;">square_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_gcd_ui</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
counts = append(counts, powercount(p, k))
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t:= v^r</span>
mpz_mul_si(p,p,10)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- t*= m</span>
end for
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">powercount</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %v\n",{k,k+9,counts})
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?elapsed(time()-t0)</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powerful</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: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</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: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">6</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"..."</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_FltFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_StrFmt</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</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><span style="color: #004600;">pp_Maxlen</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">})</span>
<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;">"%d %2d-powerful numbers &lt;= 10^%-2d : %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_set_si</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: #004080;">sequence</span> <span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">powercount</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: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</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;">for</span>
<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;">"Counts of %2d-powerful numbers &lt;= 10^(0..%d) : %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,805

edits

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