Powerful numbers: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 16:59, 25 January 2024

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

Wikipedia, Powerful number

OEIS A001694: 2-powerful numbers

OEIS A036966: 3-powerful numbers

OEIS A036967: 4-powerful numbers

OEIS A069492: 5-powerful numbers

OEIS A069493: 6-powerful numbers

OEIS A062762: number of powerful numbers <= 2^n

OEIS A118896: number of powerful numbers <= 10^n

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

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