Rosetta Code

Powerful numbers: Difference between revisions

Page Discussion

Powerful numbers (view source)

Revision as of 16:59, 25 January 2024

6,746 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(→‎{{header|Lua}}: added Lua solution)
m (→‎{{header|Wren}}: Minor tidy)
 
(4 intermediate revisions by 4 users not shown)
Line 42:
 
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">
F primes_up_to_limit(Int limit)
[Int] r
I limit >= 2
r.append(2)
 
V isprime = [1B] * ((limit - 1) I/ 2)
V sieveend = Int(sqrt(limit))
L(i) 0 .< isprime.len
I isprime[i]
Int p = i * 2 + 3
r.append(p)
I i <= sieveend
L(j) ((p * p - 3) >> 1 .< isprime.len).step(p)
isprime[j] = 0B
R r
 
F primepowers(k, upper_bound)
V ub = Int(pow(upper_bound, 1 / k) + .5)
V res = [[Int64(1)]]
 
L(p) primes_up_to_limit(ub)
V a = [Int64(p) ^ k]
V u = upper_bound I/ a.last
L u >= p
a.append(a.last * p)
u I/= p
res.append(a)
 
R res
 
F kpowerful(k, upper_bound)
V ps = primepowers(k, upper_bound)
 
F accu(Int i, Int64 ub) -> [Int64]
[Int64] c
L(p) @ps[i]
V u = ub I/ p
I !u
L.break
 
c [+]= p
 
L(j) i + 1 .< @ps.len
I u < @ps[j][0]
L.break
c [+]= @accu(j, u).map(x -> @p * x)
R c
 
R sorted(accu(0, upper_bound))
 
F kpowerful_count_only(k, upper_bound)
V ps = primepowers(k, upper_bound)
 
F accu(Int i, Int64 ub) -> Int
V c = 0
L(p) @ps[i]
V u = ub I/ p
I !u
L.break
 
c++
 
L(j) i + 1 .< @ps.len
I u < @ps[j][0]
L.break
c += @accu(j, u)
R c
 
R accu(0, upper_bound)
 
L(k) 2..10
V res = kpowerful(k, Int64(10) ^ k)
print(res.len‘ ’k‘-powerfuls up to 10^’k‘: ’(
res[0.<5].map(x -> String(x)).join(‘ ’))‘ ... ’(
res[(len)-5..].map(x -> String(x)).join(‘ ’)))
 
L(k) 2..9
V res = (0 .< k + 10).map(n -> kpowerful_count_only(@k, Int64(10) ^ n))
print(k‘-powerful up to 10^’(k + 10)‘: ’res.map(x -> String(x)).join(‘ ’))
</syntaxhighlight>
 
{{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
</pre>
 
=={{header|C++}}==
{{trans|Go}}
{{trans|Perl}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <cmath>
#include <cstdint>
Line 54 ⟶ 160:
 
bool is_square_free(uint64_t n) {
if (n % 4 == 0)
static constexpr uint64_t primes[] {
return false;
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
for (uint64_t p = 43,3; 47,p 53,* 59,p 61,<= 67,n; 71,p 73,+= 79,2) 83, 89, 97{
}; // seems to beuint64_t enoughcount = 0;
for (auto; n % p :== primes0; n /= p) {
auto p2 = p *if p;(++count > 1)
if (p2 > n) return false;
break;}
if (n % p2 == 0)
return false;
}
return true;
Line 142 ⟶ 246:
std::cout << '\n';
}
}</langsyntaxhighlight>
 
{{out}}
Line 170 ⟶ 274:
{{trans|Perl}}
Curiously, the 'powerful' function is producing duplicates which the other existing solutions don't seem to suffer from. It's easily dealt with by using a set (rather than a slice) but means that we're unable to take advantage of the counting shortcut - not that it matters as the whole thing still runs in less than 0.4 seconds!
<langsyntaxhighlight lang="go">package main
 
import (
Line 269 ⟶ 373:
fmt.Printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d): %v\n", k, j, counts)
}
}</langsyntaxhighlight>
 
{{out}}
Line 295 ⟶ 399:
 
=={{header|Java}}==
<syntaxhighlight lang="java">
<lang Java>
import java.math.BigInteger;
import java.util.ArrayList;
Line 381 ⟶ 485:
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 419 ⟶ 523:
=={{header|Julia}}==
{{trans|Perl}}
<langsyntaxhighlight lang="julia">using Primes
 
is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here
Line 472 ⟶ 576:
[kpowerfulcount(Int128(10)^j, k) for j in 0:(k+9)], "\n")
end
</langsyntaxhighlight>{{out}}
<pre>
The set of 2-powerful numbers between 1 and 10^2 has 14 members:
Line 509 ⟶ 613:
==={{header|Support}}===
Similar need for epsilon in <code>iroot</code> as with other double-precision examples.
<langsyntaxhighlight Lualang="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
Line 526 ⟶ 630:
end
return true
end</langsyntaxhighlight>
 
==={{header|Generation}}===
<langsyntaxhighlight Lualang="lua">local function powerful_numbers(n, k)
local powerful = T{}
local function inner(m, r)
Line 552 ⟶ 656:
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</langsyntaxhighlight>
{{out}}
<pre>For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]
Line 565 ⟶ 669:
 
==={{header|Counting}}===
<langsyntaxhighlight Lualang="lua">local function powerful_count(n, k)
local count = 0
local function inner(m, r)
Line 588 ⟶ 692:
end
printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", k, k+10, counts:concat(", "))
end</langsyntaxhighlight>
{{out}}
<pre>Number of 2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330}
Line 602 ⟶ 706:
=={{header|Nim}}==
{{trans|C++}}
<langsyntaxhighlight Nimlang="nim">import algorithm, math, strformat, strutils
 
func isSquareFree(n: uint64): bool =
Line 668 ⟶ 772:
counts.add powerfulcount(p, k)
p *= 10
echo &"Count of {k:2}-powerful numbers <= 10^j, j in 0 ≤ j < {k+10}: {counts.join(\" \")}"</langsyntaxhighlight>
 
{{out}}
Line 693 ⟶ 797:
=={{header|Perl}}==
===Generation===
<langsyntaxhighlight lang="perl">use 5.020;
use ntheory qw(is_square_free);
use experimental qw(signatures);
Line 724 ⟶ 828:
my $t = join(', ', @a[$#a-4..$#a]);
printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", $k, scalar(@a), $h, $t);
}</langsyntaxhighlight>
{{out}}
<pre>
Line 739 ⟶ 843:
 
===Counting===
<langsyntaxhighlight lang="perl">use 5.020;
use ntheory qw(is_square_free);
use experimental qw(signatures);
Line 766 ⟶ 870:
printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", $k, $k+10,
join(', ', map { powerful_count(ipow(10, $_), $k) } 0..($k+10-1)));
}</langsyntaxhighlight>
{{out}}
<pre>
Line 784 ⟶ 888:
===priority queue===
Tried a slightly different approach, but it gets 7/10 at best on performance, and simply not worth attempting under pwa/p2js
<!--<langsyntaxhighlight Phixlang="phix">-->
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 862 ⟶ 966:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Counts of %2d-powerful numbers &lt;= 10^(0..%d) : %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 889 ⟶ 993:
{{trans|Go}} {{trans|Sidef}}
Significantly faster. The last few counts were wrong when using native ints/atoms, so I went gmp, which means it also works on 32-bit.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 964 ⟶ 1,068:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 988 ⟶ 1,092:
"0.8s"
</pre>
 
=={{header|Python}}==
Simple minded generation method.
<syntaxhighlight 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))</syntaxhighlight>
{{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}}==
Line 995 ⟶ 1,170:
Raku has no handy pre-made nth integer root routine so has the same problem as Go with needing a slight "fudge factor" in the nth root calculation.
 
<syntaxhighlight lang="raku" perl6line>sub super (\x) { x.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }
 
sub is-square-free (Int \n) {
Line 1,034 ⟶ 1,209:
printf "%2s-powerful numbers <= 10ⁿ (where 0 <= n <= %d): ", k, $top+k;
quietly say join ', ', [\+] powerfuls(10**($top + k), k);
}</langsyntaxhighlight>
{{out}}
<pre>Count and first and last five enumerated n-powerful numbers in 10ⁿ:
Line 1,060 ⟶ 1,235:
=={{header|Sidef}}==
===Generation===
<langsyntaxhighlight lang="ruby">func powerful(n, k=2) {
 
var list = []
Line 1,086 ⟶ 1,261:
var t = a.tail(5).join(', ')
printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", k, a.len, h, t)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,100 ⟶ 1,275:
</pre>
===Counting===
<langsyntaxhighlight lang="ruby">func powerful_count(n, k=2) {
 
var count = 0
Line 1,122 ⟶ 1,297:
var a = (k+10).of {|j| powerful_count(10**j, k) }
printf("Number of %2d-powerful numbers <= 10^j, for 0 <= j < #{k+10}: %s\n", k, a)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,142 ⟶ 1,317:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
import "./set" for Set
import "./sort" for Sort
import "./fmt" for Fmt
 
var potentialPowerful = Fn.new { |max, k|
Line 1,193 ⟶ 1,368:
}
Fmt.print("Count of $2d-powerful numbers <= 10^j, j in [0, $d]: $n", k, k + 9, powCount)
}</langsyntaxhighlight>
 
{{out}}
Line 1,229 ⟶ 1,404:
=={{header|zkl}}==
{{trans|Go}}
<langsyntaxhighlight lang="zkl">fcn isSquareFree(n){
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);
Line 1,251 ⟶ 1,426:
}(1,(2).pow(k)-1, n,k, powerful:=Dictionary());
powerful.keys.apply("toInt").sort();
}</langsyntaxhighlight>
<langsyntaxhighlight 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(" ")));
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,272 ⟶ 1,447:
{{trans|Perl}}
Overflows a 64 bit int at the very end, which results in a count of zero.
<langsyntaxhighlight 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() }
Line 1,281 ⟶ 1,456:
}(1,2*k - 1, n,k, count:=Ref(0));
count.value
}</langsyntaxhighlight>
<langsyntaxhighlight 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(" "));
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/298344...354073"