Anonymous user
Powerful numbers: Difference between revisions
→{{header|Raku}}
(→{{header|Lua}}: added Lua solution) |
|||
Line 988:
"0.8s"
</pre>
=={{header|Python}}==
Simple minded generation method.
<lang python>from primesieve import primes # any prime generation routine will do; don't need large primes
import math
def primepowers(k, upper_bound):
ub = int(math.pow(upper_bound, 1/k) + .5)
res = [(1,)]
for p in primes(ub):
a = [p**k]
u = upper_bound // a[-1]
while u >= p:
a.append(a[-1]*p)
u //= p
res.append(tuple(a))
return res
def kpowerful(k, upper_bound, count_only=True):
ps = primepowers(k, upper_bound)
def accu(i, ub):
c = 0 if count_only else []
for p in ps[i]:
u = ub//p
if not u: break
c += 1 if count_only else [p]
for j in range(i + 1, len(ps)):
if u < ps[j][0]:
break
c += accu(j, u) if count_only else [p*x for x in accu(j, u)]
return c
res = accu(0, upper_bound)
return res if count_only else sorted(res)
for k in range(2, 11):
res = kpowerful(k, 10**k, count_only=False)
print(f'{len(res)} {k}-powerfuls up to 10^{k}:',
' '.join(str(x) for x in res[:5]),
'...',
' '.join(str(x) for x in res[-5:])
)
for k in range(2, 11):
res = [kpowerful(k, 10**n) for n in range(k+10)]
print(f'{k}-powerful up to 10^{k+10}:',
' '.join(str(x) for x in res))</lang>
{{out}}
<pre>14 2-powerfuls up to 10^2: 1 4 8 9 16 ... 49 64 72 81 100
20 3-powerfuls up to 10^3: 1 8 16 27 32 ... 625 648 729 864 1000
25 4-powerfuls up to 10^4: 1 16 32 64 81 ... 5184 6561 7776 8192 10000
32 5-powerfuls up to 10^5: 1 32 64 128 243 ... 65536 69984 78125 93312 100000
38 6-powerfuls up to 10^6: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000
46 7-powerfuls up to 10^7: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000
52 8-powerfuls up to 10^8: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000
59 9-powerfuls up to 10^9: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000
68 10-powerfuls up to 10^10: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
2-powerful up to 10^12: 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330
3-powerful up to 10^13: 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136
4-powerful up to 10^14: 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654
5-powerful up to 10^15: 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770
6-powerful up to 10^16: 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706
7-powerful up to 10^17: 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740
8-powerful up to 10^18: 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191
9-powerful up to 10^19: 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868
10-powerful up to 10^20: 1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651</pre>
=={{header|Raku}}==
| |||