Anonymous user
Powerful numbers: Difference between revisions
→{{header|Nim}}
(Added C++ 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|Nim}}==
{{trans|C++}}
<lang Nim>import algorithm, math, strformat, strutils
func isSquareFree(n: uint64): bool =
const Primes = [uint64 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]
for p in Primes:
let p2 = p * p
if p2 > n: break
if n mod p2 == 0: return false
result = true
func iroot(n: uint64; r: Natural): uint64 =
const Adj = 1e-6
result = uint64(pow(float(n), 1 / r) + Adj)
func powerful(n: uint64; k: Natural): seq[uint64] =
var res: seq[uint64]
func f(m: uint64; r: Natural) =
if r < k:
res.add m
return
let root = iroot(n div m, r)
for v in 1..root:
if r > k and (not v.isSquareFree or gcd(m, v) != 1):
continue
f(m * v^r, r - 1)
f(1, 2 * k - 1)
res.sort()
return res
func powerfulCount(n: uint64; k: Natural): uint64 =
var count = 0u64
func f(m: uint64; r: Natural) =
let root = iroot(n div m, r)
if r <= k:
count += root
return
for v in 1..root:
if v.isSquareFree and gcd(m, v) == 1:
f(m * v^r, r - 1)
f(1, 2 * k - 1)
return count
var p: uint64 = 10
for k in 2..10:
p *= 10
let result = powerful(p, k)
let head = result[0..4].join(" ")
let tail = result[^5..^1].join(" ")
echo &"{result.len} {k:2}-powerful numbers <= 10^{k}: {head} ... {tail}"
echo()
for k in 2..10:
p = 1
var counts: seq[uint64]
for j in 0..k+9:
counts.add powerfulcount(p, k)
p *= 10
echo &"Count of {k:2}-powerful numbers <= 10^j, j in 0 ≤ j < {k+10}: {counts.join(\" \")}"</lang>
{{out}}
<pre>14 2-powerful numbers <= 10^2: 1 4 8 9 16 ... 49 64 72 81 100
20 3-powerful numbers <= 10^3: 1 8 16 27 32 ... 625 648 729 864 1000
25 4-powerful numbers <= 10^4: 1 16 32 64 81 ... 5184 6561 7776 8192 10000
32 5-powerful numbers <= 10^5: 1 32 64 128 243 ... 65536 69984 78125 93312 100000
38 6-powerful numbers <= 10^6: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000
46 7-powerful numbers <= 10^7: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000
52 8-powerful numbers <= 10^8: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000
59 9-powerful numbers <= 10^9: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000
68 10-powerful numbers <= 10^10: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
Count of 2-powerful numbers <= 10^j, j in 0 ≤ j < 12: 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330
Count of 3-powerful numbers <= 10^j, j in 0 ≤ j < 13: 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136
Count of 4-powerful numbers <= 10^j, j in 0 ≤ j < 14: 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654
Count of 5-powerful numbers <= 10^j, j in 0 ≤ j < 15: 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770
Count of 6-powerful numbers <= 10^j, j in 0 ≤ j < 16: 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706
Count of 7-powerful numbers <= 10^j, j in 0 ≤ j < 17: 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740
Count of 8-powerful numbers <= 10^j, j in 0 ≤ j < 18: 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191
Count of 9-powerful numbers <= 10^j, j in 0 ≤ j < 19: 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868
Count of 10-powerful numbers <= 10^j, j in 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|Perl}}==
| |||