Powerful numbers: Difference between revisions
no edit summary
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Don't generate unnecessary excess powerfuls) |
No edit summary |
||
Line 168:
Count of 10-powerful numbers <= 10^j, j in [0, 20): [1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651]
</pre>
=={{header|Julia}}==
{{trans|Perl}}
<lang julia>using Primes
is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here
is_squarefree(n) = all(x -> x[2] == 1, factor(n))
rootdiv(n, m, r) = Int128(floor(div(n, m)^(1/r) + 0.0000001))
function genkpowerful(n, k)
ret = Int128[]
function inner(m, r)
if r < k
push!(ret, m)
return
else
for a in 1:rootdiv(n, m, r)
if r <= k || (gcd(a, m) == 1 && is_squarefree(a))
inner(m * Int128(a)^r, r - 1)
end
end
end
end
inner(1, 2 * k - 1)
return unique(sort(Int.(ret)))
end
function kpowerfulcount(n, k)
count = Int128(0)
function inner(m, r)
if r <= k
count += rootdiv(n, m, r)
else
for a in 1:rootdiv(n, m, r)
if gcd(a, m) == 1 && is_squarefree(a)
inner(m * a^r, r - 1)
end
end
end
end
inner(1, 2*k - 1)
return Int(count)
end
for k in 2:10
a = genkpowerful(10^k, k)
len = length(a)
print("The set of k-powerful numbers between 1 and 10^$k has $len members:\n[")
for i in [1:5 ; len-5:len]
print(a[i], i == 5 ? " ... " : i == len ? "]\n" : ", ")
end
end
for k in 2:10
print("The count of $k-powerful numbers from 1 to 10^j for j in 0:$(k+9) is: ",
[kpowerfulcount(Int128(10)^j, k) for j in 0:(k+9)], "\n")
end
</lang>{{out}}
<pre>
The set of k-powerful numbers between 1 and 10^2 has 14 members:
[1, 4, 8, 9, 16 ... 36, 49, 64, 72, 81, 100]
The set of k-powerful numbers between 1 and 10^3 has 20 members:
[1, 8, 16, 27, 32 ... 512, 625, 648, 729, 864, 1000]
The set of k-powerful numbers between 1 and 10^4 has 25 members:
[1, 16, 32, 64, 81 ... 4096, 5184, 6561, 7776, 8192, 10000]
The set of k-powerful numbers between 1 and 10^5 has 32 members:
[1, 32, 64, 128, 243 ... 62208, 65536, 69984, 78125, 93312, 100000]
The set of k-powerful numbers between 1 and 10^6 has 38 members:
[1, 64, 128, 256, 512 ... 531441, 559872, 746496, 823543, 839808, 1000000]
The set of k-powerful numbers between 1 and 10^7 has 46 members:
[1, 128, 256, 512, 1024 ... 6718464, 7558272, 8388608, 8957952, 9765625, 10000000]
The set of k-powerful numbers between 1 and 10^8 has 52 members:
[1, 256, 512, 1024, 2048 ... 53747712, 60466176, 67108864, 80621568, 90699264, 100000000]
The set of k-powerful numbers between 1 and 10^9 has 59 members:
[1, 512, 1024, 2048, 4096 ... 544195584, 644972544, 725594112, 816293376, 967458816, 1000000000]
The set of k-powerful numbers between 1 and 10^10 has 68 members:
[1, 1024, 2048, 4096, 8192 ... 6530347008, 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
The count of 2-powerful numbers from 1 to 10^j for j in 0:11 is: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330]
The count of 3-powerful numbers from 1 to 10^j for j in 0:12 is: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136]
The count of 4-powerful numbers from 1 to 10^j for j in 0:13 is: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654]
The count of 5-powerful numbers from 1 to 10^j for j in 0:14 is: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770]
The count of 6-powerful numbers from 1 to 10^j for j in 0:15 is: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706]
The count of 7-powerful numbers from 1 to 10^j for j in 0:16 is: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740]
The count of 8-powerful numbers from 1 to 10^j for j in 0:17 is: [1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191]
The count of 9-powerful numbers from 1 to 10^j for j in 0:18 is: [1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868]
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|Perl}}==
| |||