Powerful numbers
A k-powerful (or k-full) number is a positive integer n such that for every prime number p dividing n, p^k also divides n.
These are numbers of the form:
2-powerful = a^2 * b^3, for a,b >= 1 3-powerful = a^3 * b^4 * c^5, for a,b,c >= 1 4-powerful = a^4 * b^5 * c^6 * d^7, for a,b,c,d >= 1 ... k-powerful = a^k * b^(k+1) * c^(k+2) *...* ω^(2*k-1), for a,b,c,...,ω >= 1
- Task
Write a function that generates all the k-powerful numbers less than or equal to n.
- For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set.
Write a function that counts the number of k-powerful numbers less than or equal to n. (optional)
- For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10.
- See also
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(‘ ’))
- Output:
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
C++
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
bool is_square_free(uint64_t n) {
if (n % 4 == 0)
return false;
for (uint64_t p = 3; p * p <= n; p += 2) {
uint64_t count = 0;
for (; n % p == 0; n /= p) {
if (++count > 1)
return false;
}
}
return true;
}
uint64_t iroot(uint64_t n, uint64_t r) {
// adjustment to ensure f/p square root exact for perfect integer squares
static constexpr double adj = 1e-6;
return static_cast<uint64_t>(std::pow(n, 1.0/r) + adj);
}
uint64_t ipow(uint64_t n, uint64_t p) {
uint64_t prod = 1;
for (; p > 0; p >>= 1) {
if (p & 1)
prod *= n;
n *= n;
}
return prod;
}
std::vector<uint64_t> powerful(uint64_t n, uint64_t k) {
std::vector<uint64_t> result;
std::function<void(uint64_t, uint64_t)> f = [&](uint64_t m, uint64_t r) {
if (r < k) {
result.push_back(m);
return;
}
uint64_t root = iroot(n/m, r);
for (uint64_t v = 1; v <= root; ++v) {
if (r > k && (!is_square_free(v) || std::gcd(m, v) != 1))
continue;
f(m * ipow(v, r), r - 1);
}
};
f(1, 2*k - 1);
std::sort(result.begin(), result.end());
return result;
}
uint64_t powerful_count(uint64_t n, uint64_t k) {
uint64_t count = 0;
std::function<void(uint64_t, uint64_t)> f = [&](uint64_t m, uint64_t r) {
if (r <= k) {
count += iroot(n/m, r);
return;
}
uint64_t root = iroot(n/m, r);
for (uint64_t v = 1; v <= root; ++v) {
if (is_square_free(v) && std::gcd(m, v) == 1)
f(m * ipow(v, r), r - 1);
}
};
f(1, 2*k - 1);
return count;
}
int main() {
const size_t max = 5;
for (uint64_t k = 2, p = 100; k <= 10; ++k, p *= 10) {
auto result = powerful(p, k);
std::cout << result.size() << " " << k
<< "-powerful numbers <= 10^" << k << ":";
for (size_t i = 0; i < result.size(); ++i) {
if (i == max)
std::cout << " ...";
else if (i < max || i + max >= result.size())
std::cout << ' ' << result[i];
}
std::cout << '\n';
}
std::cout << '\n';
for (uint64_t k = 2; k <= 10; ++k) {
std::cout << "Count of " << k << "-powerful numbers <= 10^j for 0 <= j < "
<< k + 10 << ":";
for (uint64_t j = 0, p = 1; j < k + 10; ++j, p *= 10)
std::cout << ' ' << powerful_count(p, k);
std::cout << '\n';
}
}
- Output:
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 for 0 <= j < 12: 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330 Count of 3-powerful numbers <= 10^j for 0 <= j < 13: 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136 Count of 4-powerful numbers <= 10^j for 0 <= j < 14: 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654 Count of 5-powerful numbers <= 10^j for 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 for 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 for 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 for 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 for 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 for 0 <= j < 20: 1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651
Go
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!
package main
import (
"fmt"
"math"
"sort"
)
const adj = 0.0001 // adjustment to ensure f/p square root exact for perfect integer squares
var 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,
} // seems to be enough
func gcd(x, y uint64) uint64 {
for y != 0 {
x, y = y, x%y
}
return x
}
func isSquareFree(x uint64) bool {
for _, p := range primes {
p2 := p * p
if p2 > x {
break
}
if x%p2 == 0 {
return false
}
}
return true
}
func iroot(x, p uint64) uint64 {
return uint64(math.Pow(float64(x), 1.0/float64(p)) + adj)
}
func ipow(x, p uint64) uint64 {
prod := uint64(1)
for p > 0 {
if p&1 != 0 {
prod *= x
}
p >>= 1
x *= x
}
return prod
}
func powerful(n, k uint64) []uint64 {
set := make(map[uint64]bool)
var f func(m, r uint64) // recursive closure
f = func(m, r uint64) {
if r < k {
set[m] = true
return
}
for v := uint64(1); v <= iroot(n/m, r); v++ {
if r > k {
if !isSquareFree(v) || gcd(m, v) != 1 {
continue
}
}
f(m*ipow(v, r), r-1)
}
}
f(1, (1<<k)-1)
list := make([]uint64, 0, len(set))
for key := range set {
list = append(list, key)
}
sort.Slice(list, func(i, j int) bool {
return list[i] < list[j]
})
return list
}
func main() {
power := uint64(10)
for k := uint64(2); k <= 10; k++ {
power *= 10
a := powerful(power, k)
le := len(a)
h, t := a[0:5], a[le-5:]
fmt.Printf("%d %2d-powerful numbers <= 10^%-2d: %v ... %v\n", le, k, k, h, t)
}
fmt.Println()
for k := uint64(2); k <= 10; k++ {
power := uint64(1)
var counts []int
for j := uint64(0); j < k+10; j++ {
a := powerful(power, k)
counts = append(counts, len(a))
power *= 10
}
j := k + 10
fmt.Printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d): %v\n", k, j, counts)
}
}
- Output:
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, 12): [1 4 14 54 185 619 2027 6553 21044 67231 214122 680330] Count of 3-powerful numbers <= 10^j, j in [0, 13): [1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136] Count of 4-powerful numbers <= 10^j, j in [0, 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, 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, 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, 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, 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, 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, 20): [1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651]
Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PowerfulNumbers {
public static void main(String[] args) {
System.out.printf("Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set%n");
for ( int k = 2 ; k <= 10 ; k++ ) {
BigInteger max = BigInteger.valueOf(10).pow(k);
List<BigInteger> powerfulNumbers = getPowerFulNumbers(max, k);
System.out.printf("There are %d %d-powerful numbers between 1 and %d. %nList: %s%n", powerfulNumbers.size(), k, max, getList(powerfulNumbers));
}
System.out.printf("%nTask: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10%n");
for ( int k = 2 ; k <= 10 ; k++ ) {
List<Integer> powCount = new ArrayList<>();
for ( int j = 0 ; j < k+10 ; j++ ) {
BigInteger max = BigInteger.valueOf(10).pow(j);
powCount.add(countPowerFulNumbers(max, k));
}
System.out.printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d]: %s%n", k, k+9, powCount);
}
}
private static String getList(List<BigInteger> list) {
StringBuilder sb = new StringBuilder();
sb.append(list.subList(0, 5).toString().replace("]", ""));
sb.append(" ... ");
sb.append(list.subList(list.size()-5, list.size()).toString().replace("[", ""));
return sb.toString();
}
private static int countPowerFulNumbers(BigInteger max, int k) {
return potentialPowerful(max, k).size();
}
private static List<BigInteger> getPowerFulNumbers(BigInteger max, int k) {
List<BigInteger> powerfulNumbers = new ArrayList<>(potentialPowerful(max, k));
Collections.sort(powerfulNumbers);
return powerfulNumbers;
}
private static Set<BigInteger> potentialPowerful(BigInteger max, int k) {
// Setup
int[] indexes = new int[k];
for ( int i = 0 ; i < k ; i++ ) {
indexes[i] = 1;
}
Set<BigInteger> powerful = new HashSet<>();
boolean foundPower = true;
while ( foundPower ) {
boolean genPowerful = false;
for ( int index = 0 ; index < k ; index++ ) {
BigInteger power = BigInteger.ONE;
for ( int i = 0 ; i < k ; i++ ) {
power = power.multiply(BigInteger.valueOf(indexes[i]).pow(k+i));
}
if ( power.compareTo(max) <= 0 ) {
powerful.add(power);
indexes[0] += 1;
genPowerful = true;
break;
}
else {
indexes[index] = 1;
if ( index < k-1 ) {
indexes[index+1] += 1;
}
}
}
if ( ! genPowerful ) {
foundPower = false;
}
}
return powerful;
}
}
- Output:
Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set There are 14 2-powerful numbers between 1 and 100. List: [1, 4, 8, 9, 16 ... 49, 64, 72, 81, 100] There are 20 3-powerful numbers between 1 and 1000. List: [1, 8, 16, 27, 32 ... 625, 648, 729, 864, 1000] There are 25 4-powerful numbers between 1 and 10000. List: [1, 16, 32, 64, 81 ... 5184, 6561, 7776, 8192, 10000] There are 32 5-powerful numbers between 1 and 100000. List: [1, 32, 64, 128, 243 ... 65536, 69984, 78125, 93312, 100000] There are 38 6-powerful numbers between 1 and 1000000. List: [1, 64, 128, 256, 512 ... 559872, 746496, 823543, 839808, 1000000] There are 46 7-powerful numbers between 1 and 10000000. List: [1, 128, 256, 512, 1024 ... 7558272, 8388608, 8957952, 9765625, 10000000] There are 52 8-powerful numbers between 1 and 100000000. List: [1, 256, 512, 1024, 2048 ... 60466176, 67108864, 80621568, 90699264, 100000000] There are 59 9-powerful numbers between 1 and 1000000000. List: [1, 512, 1024, 2048, 4096 ... 644972544, 725594112, 816293376, 967458816, 1000000000] There are 68 10-powerful numbers between 1 and 10000000000. List: [1, 1024, 2048, 4096, 8192 ... 7739670528, 8589934592, 8707129344, 9795520512, 10000000000] Task: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10 Count of 2-powerful numbers <= 10^j, j in [0, 11]: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Count of 3-powerful numbers <= 10^j, j in [0, 12]: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Count of 4-powerful numbers <= 10^j, j in [0, 13]: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Count of 5-powerful numbers <= 10^j, j in [0, 14]: [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, 15]: [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, 16]: [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, 17]: [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, 18]: [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, 19]: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
Julia
using Primes
is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here
is_squarefree(n) = all(x -> x[2] == 1, factor(n))
rootdiv(n, m, r) = Int128(floor(div(n, m)^(1/r) + 0.0000001))
function genkpowerful(n, k)
ret = Int128[]
function inner(m, r)
if r < k
push!(ret, m)
else
for a in 1:rootdiv(n, m, r)
if r <= k || (gcd(a, m) == 1 && is_squarefree(a))
inner(m * Int128(a)^r, r - 1)
end
end
end
end
inner(1, 2 * k - 1)
return unique(sort(Int.(ret)))
end
function kpowerfulcount(n, k)
count = Int128(0)
function inner(m, r)
if r <= k
count += rootdiv(n, m, r)
else
for a in 1:rootdiv(n, m, r)
if gcd(a, m) == 1 && is_squarefree(a)
inner(m * a^r, r - 1)
end
end
end
end
inner(1, 2*k - 1)
return Int(count)
end
for k in 2:10
a = genkpowerful(10^k, k)
len = length(a)
print("The set of $k-powerful numbers between 1 and 10^$k has $len members:\n[")
for i in [1:5 ; len-5:len]
print(a[i], i == 5 ? " ... " : i == len ? "]\n" : ", ")
end
end
for k in 2:10
print("The count of $k-powerful numbers from 1 to 10^j for j in 0:$(k+9) is: ",
[kpowerfulcount(Int128(10)^j, k) for j in 0:(k+9)], "\n")
end
- Output:
The set of 2-powerful numbers between 1 and 10^2 has 14 members: [1, 4, 8, 9, 16 ... 36, 49, 64, 72, 81, 100] The set of 3-powerful numbers between 1 and 10^3 has 20 members: [1, 8, 16, 27, 32 ... 512, 625, 648, 729, 864, 1000] The set of 4-powerful numbers between 1 and 10^4 has 25 members: [1, 16, 32, 64, 81 ... 4096, 5184, 6561, 7776, 8192, 10000] The set of 5-powerful numbers between 1 and 10^5 has 32 members: [1, 32, 64, 128, 243 ... 62208, 65536, 69984, 78125, 93312, 100000] The set of 6-powerful numbers between 1 and 10^6 has 38 members: [1, 64, 128, 256, 512 ... 531441, 559872, 746496, 823543, 839808, 1000000] The set of 7-powerful numbers between 1 and 10^7 has 46 members: [1, 128, 256, 512, 1024 ... 6718464, 7558272, 8388608, 8957952, 9765625, 10000000] The set of 8-powerful numbers between 1 and 10^8 has 52 members: [1, 256, 512, 1024, 2048 ... 53747712, 60466176, 67108864, 80621568, 90699264, 100000000] The set of 9-powerful numbers between 1 and 10^9 has 59 members: [1, 512, 1024, 2048, 4096 ... 544195584, 644972544, 725594112, 816293376, 967458816, 1000000000] The set of 10-powerful numbers between 1 and 10^10 has 68 members: [1, 1024, 2048, 4096, 8192 ... 6530347008, 7739670528, 8589934592, 8707129344, 9795520512, 10000000000] The count of 2-powerful numbers from 1 to 10^j for j in 0:11 is: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] The count of 3-powerful numbers from 1 to 10^j for j in 0:12 is: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] The count of 4-powerful numbers from 1 to 10^j for j in 0:13 is: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] The count of 5-powerful numbers from 1 to 10^j for j in 0:14 is: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770] The count of 6-powerful numbers from 1 to 10^j for j in 0:15 is: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706] The count of 7-powerful numbers from 1 to 10^j for j in 0:16 is: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740] The count of 8-powerful numbers from 1 to 10^j for j in 0:17 is: [1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191] The count of 9-powerful numbers from 1 to 10^j for j in 0:18 is: [1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868] 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]
Lua
A nearly literal translation from Perl, though did reverse the if-next logic to make control flow more idiomatic.
Support
Similar need for epsilon in iroot
as with other double-precision examples.
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
Generation
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
- Output:
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]
Counting
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
- Output:
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}
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(\" \")}"
- Output:
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
Perl
Generation
use 5.020;
use ntheory qw(is_square_free);
use experimental qw(signatures);
use Math::AnyNum qw(:overload idiv iroot ipow is_coprime);
sub powerful_numbers ($n, $k = 2) {
my @powerful;
sub ($m, $r) {
if ($r < $k) {
push @powerful, $m;
return;
}
for my $v (1 .. iroot(idiv($n, $m), $r)) {
if ($r > $k) {
is_square_free($v) || next;
is_coprime($m, $v) || next;
}
__SUB__->($m * ipow($v, $r), $r - 1);
}
}->(1, 2*$k - 1);
sort { $a <=> $b } @powerful;
}
foreach my $k (2 .. 10) {
my @a = powerful_numbers(10**$k, $k);
my $h = join(', ', @a[0..4]);
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);
}
- Output:
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]
Counting
use 5.020;
use ntheory qw(is_square_free);
use experimental qw(signatures);
use Math::AnyNum qw(:overload idiv iroot ipow is_coprime);
sub powerful_count ($n, $k = 2) {
my $count = 0;
sub ($m, $r) {
if ($r <= $k) {
$count += iroot(idiv($n, $m), $r);
return;
}
for my $v (1 .. iroot(idiv($n, $m), $r)) {
is_square_free($v) || next;
is_coprime($m, $v) || next;
__SUB__->($m * ipow($v, $r), $r - 1);
}
}->(1, 2*$k - 1);
return $count;
}
foreach my $k (2 .. 10) {
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)));
}
- Output:
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}
Phix
priority queue
Tried a slightly different approach, but it gets 7/10 at best on performance, and simply not worth attempting under pwa/p2js
without javascript_semantics include mpfr.e integer pq = NULL -- data is the prime powers, eg {2,2} for 2^2*3^2 -- priority is the mpz of that, eg/ie 36 procedure padd(mpz n, np, sequence s) if pq=NULL then pq = pq_new(MIN_HEAP,routine_id("mpz_cmp")) end if if mpz_cmp(np,n)<=0 then pq_add({s,mpz_init_set(np)},pq) end if end procedure procedure add_next(integer k, mpz n, p, sequence s) mpz np = mpz_init() integer l = length(s) for i=1 to l do integer ki = iff(s[i]=0?k:1) mpz_ui_pow_ui(np,get_prime(i),ki) mpz_mul(np,np,p) s[i] += ki padd(n,np,s) s[i] -= ki end for mpz_ui_pow_ui(np,get_prime(l+1),k) if l>0 and s[l]=k and s[1..l-1]==repeat(0,l-1) then padd(n,np,0&s) elsif s={} then mpz_mul(np,np,p) padd(n,np,s&k) end if end procedure function powerful(integer k, mpz n) mpz prevp = mpz_init(1) sequence res = {prevp} add_next(k,n,prevp,{}) while pq_size(pq) do {sequence s, mpz p} = pq_pop(pq) if mpz_cmp(p,prevp)!=0 then res &= p add_next(k,n,p,s) prevp = p end if end while return res end function mpz p = mpz_init(10) for k=2 to 10 do mpz_mul_si(p,p,10) sequence s = powerful(k,p) integer l = length(s) for i=1 to 5 do s[i] = mpz_get_str(s[i]) s[-i] = mpz_get_str(s[-i]) end for s[6..-6] = {"..."} s = join(s,",") printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s}) end for puts(1,"\n") --Not really fast enough, so only doing to k+5..k+8 for the first 4, but k+9 for last 5 for k=2 to 10 do sequence counts = {} integer lim = k+min(k+3,9) mpz_set_si(p,1) for j=0 to lim do printf(1,"counting (%d/%d)...\r",{j,lim}) counts &= length(powerful(k,p)) mpz_mul_si(p,p,10) end for printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %v\n",{k,lim,counts}) end for
- Output:
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 Counts of 2-powerful numbers <= 10^(0..7) : {1,4,14,54,185,619,2027,6553} Counts of 3-powerful numbers <= 10^(0..9) : {1,2,7,20,51,129,307,713,1645,3721} Counts of 4-powerful numbers <= 10^(0..11) : {1,1,5,11,25,57,117,235,464,906,1741,3312} Counts of 5-powerful numbers <= 10^(0..13) : {1,1,3,8,16,32,63,117,211,375,659,1153,2000,3402} Counts of 6-powerful numbers <= 10^(0..15) : {1,1,2,6,12,21,38,70,121,206,335,551,900,1451,2326,3706} Counts of 7-powerful numbers <= 10^(0..16) : {1,1,1,4,10,16,26,46,77,129,204,318,495,761,1172,1799,2740} Counts of 8-powerful numbers <= 10^(0..17) : {1,1,1,3,8,13,19,32,52,85,135,211,315,467,689,1016,1496,2191} Counts of 9-powerful numbers <= 10^(0..18) : {1,1,1,2,6,11,16,24,38,59,94,145,217,317,453,644,919,1308,1868} Counts of 10-powerful numbers <= 10^(0..19) : {1,1,1,1,5,9,14,21,28,43,68,104,155,227,322,447,621,858,1192,1651}
translation
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.
with javascript_semantics include mpfr.e function powerful(mpz n, integer k, sequence res={}, mpz m=NULL, integer r=0) if m=NULL then m = mpz_init(1) r = 2*k-1 end if if r<k then res = append(res,iff(mpz_fits_atom(m)?mpz_get_atom(m):mpz_get_str(m))) else mpz t = mpz_init() mpz_fdiv_q(t, n, m) -- t := floor(n/m) mpz_nthroot(t,t,r) -- t = floor(rth root of t) if not mpz_fits_integer(t) then ?9/0 end if integer lim = mpz_get_integer(t) for v=1 to lim do if r<=k or (square_free(v) and mpz_gcd_ui(NULL,m,v)=1) then mpz_ui_pow_ui(t,v,r) -- t:= v^r mpz_mul(t,t,m) -- t*= m res = powerful(n, k, res, t, r-1) end if end for end if return res end function function powercount(mpz n, integer k, mpz m=NULL, integer r=0) atom res = 0 if m=NULL then m = mpz_init(1) r = 2*k-1 end if mpz t = mpz_init() mpz_fdiv_q(t, n, m) -- t := floor(n/m) mpz_nthroot(t,t,r) -- t = floor(rth root of t) if not mpz_fits_integer(t) then ?9/0 end if integer lim = mpz_get_integer(t) if r<=k then res += lim else for v=1 to lim do if square_free(v) and mpz_gcd_ui(NULL,m,v)=1 then mpz_ui_pow_ui(t,v,r) -- t:= v^r mpz_mul(t,t,m) -- t*= m res += powercount(n, k, t, r-1) end if end for end if return res end function atom t0 = time() mpz p = mpz_init(10) for k=2 to 10 do mpz_mul_si(p,p,10) sequence s = sort(powerful(p, k)) integer l = length(s) s[6..-6] = {"..."} s = ppf(s,{pp_FltFmt,"%d",pp_StrFmt,-1,pp_IntCh,false,pp_Maxlen,100}) printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s}) end for puts(1,"\n") for k=2 to 10 do mpz_set_si(p,1) sequence counts = {} for j=0 to k+9 do counts = append(counts, powercount(p, k)) mpz_mul_si(p,p,10) end for printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %V\n",{k,k+9,counts}) end for ?elapsed(time()-t0)
- Output:
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} Counts of 2-powerful numbers <= 10^(0..11) : {1,4,14,54,185,619,2027,6553,21044,67231,214122,680330} Counts of 3-powerful numbers <= 10^(0..12) : {1,2,7,20,51,129,307,713,1645,3721,8348,18589,41136} Counts of 4-powerful numbers <= 10^(0..13) : {1,1,5,11,25,57,117,235,464,906,1741,3312,6236,11654} Counts of 5-powerful numbers <= 10^(0..14) : {1,1,3,8,16,32,63,117,211,375,659,1153,2000,3402,5770} Counts of 6-powerful numbers <= 10^(0..15) : {1,1,2,6,12,21,38,70,121,206,335,551,900,1451,2326,3706} Counts of 7-powerful numbers <= 10^(0..16) : {1,1,1,4,10,16,26,46,77,129,204,318,495,761,1172,1799,2740} Counts of 8-powerful numbers <= 10^(0..17) : {1,1,1,3,8,13,19,32,52,85,135,211,315,467,689,1016,1496,2191} Counts of 9-powerful numbers <= 10^(0..18) : {1,1,1,2,6,11,16,24,38,59,94,145,217,317,453,644,919,1308,1868} Counts of 10-powerful numbers <= 10^(0..19) : {1,1,1,1,5,9,14,21,28,43,68,104,155,227,322,447,621,858,1192,1651} "0.8s"
Python
Simple minded generation method.
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))
- Output:
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
Raku
(formerly Perl 6)
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.
sub super (\x) { x.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }
sub is-square-free (Int \n) {
constant @p = ^100 .map: { next unless .is-prime; .² };
for @p -> \p { return False if n %% p }
True
}
sub powerfuls (\n, \k, \enumerate = False) {
my @powerful;
p(1, 2*k - 1);
sub p (\m, \r) {
if r < k {
enumerate ?? @powerful.push(m) !! ++@powerful[m - 1 ?? (m - 1).chars !! 0];
return
}
for 1 .. ((n / m) ** (1/r) + .0001).Int -> \v {
if r > k {
next unless is-square-free(v);
next unless m gcd v == 1;
}
p(m * v ** r, r - 1)
}
}
@powerful;
}
put "Count and first and last five enumerated n-powerful numbers in 10ⁿ:";
for 2..10 -> \k {
my @powerful = sort powerfuls(10**k, k, True);
printf "%2d %2s-powerful numbers <= 10%-2s: %s ... %s\n", +@powerful, k, super(k),
@powerful.head(5).join(", "), @powerful.tail(5).join(", ");
}
put "\nCounts in each order of magnitude:";
my $top = 9;
for 2..10 -> \k {
printf "%2s-powerful numbers <= 10ⁿ (where 0 <= n <= %d): ", k, $top+k;
quietly say join ', ', [\+] powerfuls(10**($top + k), k);
}
- Output:
Count and first and last five enumerated n-powerful numbers in 10ⁿ: 14 2-powerful numbers <= 10² : 1, 4, 8, 9, 16 ... 49, 64, 72, 81, 100 20 3-powerful numbers <= 10³ : 1, 8, 16, 27, 32 ... 625, 648, 729, 864, 1000 25 4-powerful numbers <= 10⁴ : 1, 16, 32, 64, 81 ... 5184, 6561, 7776, 8192, 10000 32 5-powerful numbers <= 10⁵ : 1, 32, 64, 128, 243 ... 65536, 69984, 78125, 93312, 100000 38 6-powerful numbers <= 10⁶ : 1, 64, 128, 256, 512 ... 559872, 746496, 823543, 839808, 1000000 46 7-powerful numbers <= 10⁷ : 1, 128, 256, 512, 1024 ... 7558272, 8388608, 8957952, 9765625, 10000000 52 8-powerful numbers <= 10⁸ : 1, 256, 512, 1024, 2048 ... 60466176, 67108864, 80621568, 90699264, 100000000 59 9-powerful numbers <= 10⁹ : 1, 512, 1024, 2048, 4096 ... 644972544, 725594112, 816293376, 967458816, 1000000000 68 10-powerful numbers <= 10¹⁰: 1, 1024, 2048, 4096, 8192 ... 7739670528, 8589934592, 8707129344, 9795520512, 10000000000 Counts in each order of magnitude: 2-powerful numbers <= 10ⁿ (where 0 <= n <= 11): 1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330 3-powerful numbers <= 10ⁿ (where 0 <= n <= 12): 1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136 4-powerful numbers <= 10ⁿ (where 0 <= n <= 13): 1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654 5-powerful numbers <= 10ⁿ (where 0 <= n <= 14): 1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770 6-powerful numbers <= 10ⁿ (where 0 <= n <= 15): 1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706 7-powerful numbers <= 10ⁿ (where 0 <= n <= 16): 1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740 8-powerful numbers <= 10ⁿ (where 0 <= n <= 17): 1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191 9-powerful numbers <= 10ⁿ (where 0 <= n <= 18): 1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868 10-powerful numbers <= 10ⁿ (where 0 <= n <= 19): 1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651
Sidef
Generation
func powerful(n, k=2) {
var list = []
func (m,r) {
if (r < k) {
list << m
return nil
}
for a in (1 .. iroot(idiv(n,m), r)) {
if (r > k) {
a.is_coprime(m) || next
a.is_squarefree || next
}
__FUNC__(m * a**r, r-1)
}
}(1, 2*k - 1)
return list.sort
}
for k in (2..10) {
var a = powerful(10**k, k)
var h = a.head(5).join(', ')
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)
}
- Output:
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]
Counting
func powerful_count(n, k=2) {
var count = 0
func (m,r) {
if (r <= k) {
count += iroot(idiv(n,m), r)
return nil
}
for a in (1 .. iroot(idiv(n,m), r)) {
a.is_coprime(m) || next
a.is_squarefree || next
__FUNC__(m * a**r, r-1)
}
}(1, 2*k - 1)
return count
}
for k in (2..10) {
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)
}
- Output:
Number of 2-powerful numbers <= 10^j, for 0 <= j < 12: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Number of 3-powerful numbers <= 10^j, for 0 <= j < 13: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Number of 4-powerful numbers <= 10^j, for 0 <= j < 14: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Number of 5-powerful numbers <= 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 numbers <= 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 numbers <= 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 numbers <= 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 numbers <= 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 numbers <= 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]
Wren
import "/big" for BigInt
import "/set" for Set
import "/sort" for Sort
import "/fmt" for Fmt
var potentialPowerful = Fn.new { |max, k|
var indexes = List.filled(k, 1)
var powerful = Set.new()
var foundPower = true
while (foundPower) {
var genPowerful = false
for (index in 0...k) {
var power = BigInt.one
for (i in 0...k) power = power * BigInt.new(indexes[i]).pow(k+i)
if (power <= max) {
powerful.add(power.toString) // can't add BigInts directly as not value type
indexes[0] = indexes[0] + 1
genPowerful = true
break
}
indexes[index] = 1
if (index < k - 1) indexes[index+1] = indexes[index+1] + 1
}
if (!genPowerful) foundPower = false
}
return powerful.map { |p| BigInt.new(p) }.toList
}
var countPowerfulNumbers = Fn.new{ |max, k| potentialPowerful.call(max, k).count }
var getPowerfulNumbers = Fn.new { |max, k|
var powerfulNumbers = potentialPowerful.call(max, k)
Sort.quick(powerfulNumbers)
return powerfulNumbers
}
for (k in 2..10) {
var max = BigInt.ten.pow(k)
var powerfulNumbers = getPowerfulNumbers.call(max, k)
var count = powerfulNumbers.count
Fmt.print("There are $d $d-powerful numbers between 1 and $i", count, k, max)
Fmt.print("List: [$i ... $i]", powerfulNumbers[0..4], powerfulNumbers[-5..-1])
}
System.print()
for (k in 2..10) {
var powCount = []
for (j in 0...k+10) {
var max = BigInt.ten.pow(j)
powCount.add(countPowerfulNumbers.call(max, k))
}
Fmt.print("Count of $2d-powerful numbers <= 10^j, j in [0, $d]: $n", k, k + 9, powCount)
}
- Output:
There are 14 2-powerful numbers between 1 and 100 List: [1 4 8 9 16 ... 49 64 72 81 100] There are 20 3-powerful numbers between 1 and 1000 List: [1 8 16 27 32 ... 625 648 729 864 1000] There are 25 4-powerful numbers between 1 and 10000 List: [1 16 32 64 81 ... 5184 6561 7776 8192 10000] There are 32 5-powerful numbers between 1 and 100000 List: [1 32 64 128 243 ... 65536 69984 78125 93312 100000] There are 38 6-powerful numbers between 1 and 1000000 List: [1 64 128 256 512 ... 559872 746496 823543 839808 1000000] There are 46 7-powerful numbers between 1 and 10000000 List: [1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000] There are 52 8-powerful numbers between 1 and 100000000 List: [1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000] There are 59 9-powerful numbers between 1 and 1000000000 List: [1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000] There are 68 10-powerful numbers between 1 and 10000000000 List: [1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000] Count of 2-powerful numbers <= 10^j, j in [0, 11]: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Count of 3-powerful numbers <= 10^j, j in [0, 12]: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Count of 4-powerful numbers <= 10^j, j in [0, 13]: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Count of 5-powerful numbers <= 10^j, j in [0, 14]: [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, 15]: [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, 16]: [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, 17]: [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, 18]: [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, 19]: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
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);
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();
}
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(" ")));
}
- Output:
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
Overflows a 64 bit int at the very end, which results in a count of zero.
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
}
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(" "));
}
- Output:
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