Anonymous user
Powerful numbers: Difference between revisions
→{{header|Lua}}: added Lua solution
m (→priority queue: removed errant tag) |
(→{{header|Lua}}: added Lua solution) |
||
Line 502:
The count of 10-powerful numbers from 1 to 10^j for j in 0:19 is: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
</pre>
=={{header|Lua}}==
{{trans|Perl}}
A nearly literal translation from Perl, though did reverse the if-next logic to make control flow more idiomatic.
==={{header|Support}}===
Similar need for epsilon in <code>iroot</code> as with other double-precision examples.
<lang Lua>local function T(t) return setmetatable(t, {__index=table}) end
table.head = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[i] end return s end
table.tail = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[#t-n+i] end return s end
local printf = function(s,...) io.write(s:format(...)) end
local function iroot(x, y) return math.floor(x^(1/y)+1e-6) end
local function is_coprime(x, y)
while y ~= 0 do x, y = y, x%y end
return x==1
end
local primes = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 }
local function is_square_free(x)
for _,p in ipairs(primes) do
local q = p*p
if q > x then break end
if x%q == 0 then return false end
end
return true
end</lang>
==={{header|Generation}}===
<lang Lua>local function powerful_numbers(n, k)
local powerful = T{}
local function inner(m, r)
if (r < k) then
powerful[#powerful+1] = m
else
for v = 1, iroot(n/m, r) do
if r <= k or is_coprime(v, m) and is_square_free(v) then
inner(m*v^r, r-1)
end
end
end
end
inner(1, 2*k-1)
powerful:sort()
return powerful
end
for k = 2, 10 do
local a = powerful_numbers(10^k, k)
local h = a:head(5):concat(", ")
local t = a:tail(5):concat(", ")
printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", k, #a, h, t)
end</lang>
{{out}}
<pre>For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]
For k=3 there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000]
For k=4 there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000]
For k=5 there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000]
For k=6 there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000]
For k=7 there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000]
For k=8 there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000]
For k=9 there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000]
For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]</pre>
==={{header|Counting}}===
<lang Lua>local function powerful_count(n, k)
local count = 0
local function inner(m, r)
if (r <= k) then
count = count + iroot(n/m, r)
else
for v = 1, iroot(n/m, r) do
if is_coprime(v, m) and is_square_free(v) then
inner(m*v^r, r-1)
end
end
end
end
inner(1, 2*k-1)
return count
end
for k = 2, 10 do
local counts = T{}
for j = 0, k+9 do
counts[j+1] = powerful_count(10^j, k)
end
printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", k, k+10, counts:concat(", "))
end</lang>
{{out}}
<pre>Number of 2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330}
Number of 3-powerful <= 10^j for 0 <= j < 13: {1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136}
Number of 4-powerful <= 10^j for 0 <= j < 14: {1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654}
Number of 5-powerful <= 10^j for 0 <= j < 15: {1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770}
Number of 6-powerful <= 10^j for 0 <= j < 16: {1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706}
Number of 7-powerful <= 10^j for 0 <= j < 17: {1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740}
Number of 8-powerful <= 10^j for 0 <= j < 18: {1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191}
Number of 9-powerful <= 10^j for 0 <= j < 19: {1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868}
Number of 10-powerful <= 10^j for 0 <= j < 20: {1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651}</pre>
=={{header|Nim}}==
| |||