Powerful numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→priority queue: removed errant tag) |
m (→{{header|Wren}}: Minor tidy) |
||
| (5 intermediate revisions by 5 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}}
<
#include <cmath>
#include <cstdint>
Line 54 ⟶ 160:
bool is_square_free(uint64_t n) {
if (n % 4 == 0)
return false;
for (uint64_t p =
for (
}
return true;
Line 142 ⟶ 246:
std::cout << '\n';
}
}</
{{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!
<
import (
Line 269 ⟶ 373:
fmt.Printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d): %v\n", k, j, counts)
}
}</
{{out}}
Line 295 ⟶ 399:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
Line 381 ⟶ 485:
}
</syntaxhighlight>
{{out}}
Line 419 ⟶ 523:
=={{header|Julia}}==
{{trans|Perl}}
<
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
</
<pre>
The set of 2-powerful numbers between 1 and 10^2 has 14 members:
Line 502 ⟶ 606:
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|Lua}}==
{{trans|Perl}}
A nearly literal translation from Perl, though did reverse the if-next logic to make control flow more idiomatic.
==={{header|Support}}===
Similar need for epsilon in <code>iroot</code> as with other double-precision examples.
<syntaxhighlight lang="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
local printf = function(s,...) io.write(s:format(...)) end
local function iroot(x, y) return math.floor(x^(1/y)+1e-6) end
local function is_coprime(x, y)
while y ~= 0 do x, y = y, x%y end
return x==1
end
local primes = { 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 }
local function is_square_free(x)
for _,p in ipairs(primes) do
local q = p*p
if q > x then break end
if x%q == 0 then return false end
end
return true
end</syntaxhighlight>
==={{header|Generation}}===
<syntaxhighlight lang="lua">local function powerful_numbers(n, k)
local powerful = T{}
local function inner(m, r)
if (r < k) then
powerful[#powerful+1] = m
else
for v = 1, iroot(n/m, r) do
if r <= k or is_coprime(v, m) and is_square_free(v) then
inner(m*v^r, r-1)
end
end
end
end
inner(1, 2*k-1)
powerful:sort()
return powerful
end
for k = 2, 10 do
local a = powerful_numbers(10^k, k)
local h = a:head(5):concat(", ")
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</syntaxhighlight>
{{out}}
<pre>For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]
For k=3 there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000]
For k=4 there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000]
For k=5 there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000]
For k=6 there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000]
For k=7 there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000]
For k=8 there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000]
For k=9 there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000]
For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]</pre>
==={{header|Counting}}===
<syntaxhighlight lang="lua">local function powerful_count(n, k)
local count = 0
local function inner(m, r)
if (r <= k) then
count = count + iroot(n/m, r)
else
for v = 1, iroot(n/m, r) do
if is_coprime(v, m) and is_square_free(v) then
inner(m*v^r, r-1)
end
end
end
end
inner(1, 2*k-1)
return count
end
for k = 2, 10 do
local counts = T{}
for j = 0, k+9 do
counts[j+1] = powerful_count(10^j, k)
end
printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", k, k+10, counts:concat(", "))
end</syntaxhighlight>
{{out}}
<pre>Number of 2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330}
Number of 3-powerful <= 10^j for 0 <= j < 13: {1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136}
Number of 4-powerful <= 10^j for 0 <= j < 14: {1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654}
Number of 5-powerful <= 10^j for 0 <= j < 15: {1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770}
Number of 6-powerful <= 10^j for 0 <= j < 16: {1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706}
Number of 7-powerful <= 10^j for 0 <= j < 17: {1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740}
Number of 8-powerful <= 10^j for 0 <= j < 18: {1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191}
Number of 9-powerful <= 10^j for 0 <= j < 19: {1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868}
Number of 10-powerful <= 10^j for 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|Nim}}==
{{trans|C++}}
<
func isSquareFree(n: uint64): bool =
Line 571 ⟶ 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(\" \")}"</
{{out}}
Line 596 ⟶ 797:
=={{header|Perl}}==
===Generation===
<
use ntheory qw(is_square_free);
use experimental qw(signatures);
Line 627 ⟶ 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);
}</
{{out}}
<pre>
Line 642 ⟶ 843:
===Counting===
<
use ntheory qw(is_square_free);
use experimental qw(signatures);
Line 669 ⟶ 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)));
}</
{{out}}
<pre>
Line 687 ⟶ 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
<!--<
<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 765 ⟶ 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 <= 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>
<!--</
{{out}}
<pre>
Line 792 ⟶ 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.
<!--<
<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 867 ⟶ 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>
<!--</
{{out}}
<pre>
Line 891 ⟶ 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 898 ⟶ 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"
sub is-square-free (Int \n) {
Line 937 ⟶ 1,209:
printf "%2s-powerful numbers <= 10ⁿ (where 0 <= n <= %d): ", k, $top+k;
quietly say join ', ', [\+] powerfuls(10**($top + k), k);
}</
{{out}}
<pre>Count and first and last five enumerated n-powerful numbers in 10ⁿ:
Line 963 ⟶ 1,235:
=={{header|Sidef}}==
===Generation===
<
var list = []
Line 989 ⟶ 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)
}</
{{out}}
<pre>
Line 1,003 ⟶ 1,275:
</pre>
===Counting===
<
var count = 0
Line 1,025 ⟶ 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)
}</
{{out}}
<pre>
Line 1,045 ⟶ 1,317:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<
import "./set" for Set
import "./sort" for Sort
import "./fmt" for Fmt
var potentialPowerful = Fn.new { |max, k|
Line 1,096 ⟶ 1,368:
}
Fmt.print("Count of $2d-powerful numbers <= 10^j, j in [0, $d]: $n", k, k + 9, powCount)
}</
{{out}}
Line 1,132 ⟶ 1,404:
=={{header|zkl}}==
{{trans|Go}}
<
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,154 ⟶ 1,426:
}(1,(2).pow(k)-1, n,k, powerful:=Dictionary());
powerful.keys.apply("toInt").sort();
}</
<
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(" ")));
}</
{{out}}
<pre>
Line 1,175 ⟶ 1,447:
{{trans|Perl}}
Overflows a 64 bit int at the very end, which results in a count of zero.
<
fcn(m,r, n,k,count){ // recursive closure
if(r<=k){ count.incN(iroot(n/m, r)); return() }
Line 1,184 ⟶ 1,456:
}(1,2*k - 1, n,k, count:=Ref(0));
count.value
}</
<
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(" "));
}</
{{out}}
<pre>
| |||