Powerful numbers

From Rosetta Code
Powerful numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

Translation of: Python
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++

Translation of: Go
Translation of: Perl
#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

Translation of: 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!

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

Translation of: Perl
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

Translation of: Perl

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

Translation of: C++
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

Library: Phix/mpfr

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

Translation of: Go
Translation of: 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.

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)

Works with: Rakudo version 2020.01
Translation of: Perl

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

Translation of: Java
Library: Wren-big
Library: Wren-set
Library: Wren-sort
Library: Wren-fmt
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

Translation of: Go
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
Translation of: Perl

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