Anonymous user
Powerful numbers: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|Sidef}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 694:
=={{header|zkl}}==
{{trans|Go}}
<lang zkl></lang>▼
<lang zkl>
var [const] primes2=T(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,) // seems to be enough
.apply("pow",2);
foreach p2 in (primes2){
if(p2>n) break;
if(n%p2 == 0) return(False);
}
True
}
const adj=0.0001; // adjustment to ensure f/r square root exact for perfect integer squares
fcn iroot(n,r){ (n.toFloat().pow(1.0/r) + adj).toInt() }
fcn powerfuls(n,k){
fcn(m,r, n,k,powerful){ // recursive closure
if(r<k){ powerful[m]=True; return(); }
foreach v in ([1..iroot(n/m, r)]){
if(r>k){ if(not isSquareFree(v) or m.gcd(v)!=1) continue; }
self.fcn(m*v.pow(r), r-1, n,k,powerful)
}
}(1,(2).pow(k)-1, n,k, powerful:=Dictionary());
powerful.keys.apply("toInt").sort();
<lang zkl>println("Count, first and last five enumerated n-powerful numbers in 10\u207f:");
foreach k in ([2..10]){
ps:=powerfuls((10).pow(k),k);
println("%2d: %s ... %s".fmt(ps.len(),ps[0,5].concat(" "),ps.tail(5).concat(" ")));
}</lang>
{{out}}
<pre>
Count, first and last five enumerated n-powerful numbers in 10ⁿ:
14: 1 4 8 9 16 ... 49 64 72 81 100
20: 1 8 16 27 32 ... 625 648 729 864 1000
25: 1 16 32 64 81 ... 5184 6561 7776 8192 10000
32: 1 32 64 128 243 ... 65536 69984 78125 93312 100000
38: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000
46: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000
52: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000
59: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000
68: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
</pre>
{{trans|Perl}}
Overflows a 64 bit int at the very end, which results in a count of zero.
<lang zkl>fcn powerfulsN(n,k){ // count
fcn(m,r, n,k,count){ // recursive closure
if(r<=k){ count.incN(iroot(n/m, r)); return() }
foreach v in ([1..iroot(n/m, r)]){
if(not isSquareFree(v) or m.gcd(v)!=1) continue;
self.fcn(m*v.pow(r), r-1, n,k,count)
}
}(1,2*k - 1, n,k, count:=Ref(0));
count.value
}</lang>
<lang zkl>println("Counts in each order of magnitude:");
foreach k in ([2..10]){
print("%2s-powerful numbers <= 10\u207f (n in [0..%d)): ".fmt(k, 10+k));
ps:=[0 .. k+10 -1].apply('wrap(n){ powerfulsN((10).pow(n), k) });
println(ps.concat(" "));
}</lang>
{{out}}
<pre>
Counts in each order of magnitude:
2-powerful numbers <= 10ⁿ (n in [0..12)): 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330
3-powerful numbers <= 10ⁿ (n in [0..13)): 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136
4-powerful numbers <= 10ⁿ (n in [0..14)): 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654
5-powerful numbers <= 10ⁿ (n in [0..15)): 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770
6-powerful numbers <= 10ⁿ (n in [0..16)): 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706
7-powerful numbers <= 10ⁿ (n in [0..17)): 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740
8-powerful numbers <= 10ⁿ (n in [0..18)): 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191
9-powerful numbers <= 10ⁿ (n in [0..19)): 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868
10-powerful numbers <= 10ⁿ (n in [0..20)): 1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 0
</pre>
| |||