Powerful numbers

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

• 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

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! <lang go>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)
   }

}</lang>

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]

Julia

Translation of: Perl

<lang julia>using Primes

is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here

is_squarefree(n) = all(x -> x[2] == 1, factor(n)) rootdiv(n, m, r) = Int128(floor(div(n, m)^(1/r) + 0.0000001))

function genkpowerful(n, k)

   ret = Int128[]
   function inner(m, r)
       if r < k
           push!(ret, m)
           return
       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

</lang>

Output:

The set of k-powerful numbers between 1 and 10^2 has 14 members:
[1, 4, 8, 9, 16 ... 36, 49, 64, 72, 81, 100]
The set of k-powerful numbers between 1 and 10^3 has 20 members:
[1, 8, 16, 27, 32 ... 512, 625, 648, 729, 864, 1000]
The set of k-powerful numbers between 1 and 10^4 has 25 members:
[1, 16, 32, 64, 81 ... 4096, 5184, 6561, 7776, 8192, 10000]
The set of k-powerful numbers between 1 and 10^5 has 32 members:
[1, 32, 64, 128, 243 ... 62208, 65536, 69984, 78125, 93312, 100000]
The set of k-powerful numbers between 1 and 10^6 has 38 members:
[1, 64, 128, 256, 512 ... 531441, 559872, 746496, 823543, 839808, 1000000]
The set of k-powerful numbers between 1 and 10^7 has 46 members:
[1, 128, 256, 512, 1024 ... 6718464, 7558272, 8388608, 8957952, 9765625, 10000000]
The set of k-powerful numbers between 1 and 10^8 has 52 members:
[1, 256, 512, 1024, 2048 ... 53747712, 60466176, 67108864, 80621568, 90699264, 100000000]
The set of k-powerful numbers between 1 and 10^9 has 59 members:
[1, 512, 1024, 2048, 4096 ... 544195584, 644972544, 725594112, 816293376, 967458816, 1000000000]
The set of k-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]

Perl

Generation

<lang perl>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);

}</lang>

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

<lang perl>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)));

}</lang>

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}

Perl 6

Works with: Rakudo version 2020.01

Translation of: Perl

Perl 6 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.

<lang perl6>sub super ($e) { $e.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }

sub is-square-free (Int $n) {

   constant @p = ^100 .map: { next unless .is-prime; .² };
   return False if $n %% $_ for @p;
   True

}

my $fudge-factor = .0001;

sub powerfuls ($n, $k) {

   my @powerful;
   p(1, 2*$k - 1);
   sub p ($m, $r) {
       @powerful.push($m), return if $r < $k;
       for 1 .. (($n / $m) ** (1/$r) + $fudge-factor).floor -> $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);
   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 = 10; for 2..10 -> \k {

   my @powerfuls = powerfuls(10**($top + k - 1), k);
   printf "%2s-powerful numbers <= 10ⁿ (where n == 0 through %d): ", k, $top+k-1;
   say join ", ", (0 ..^ ($top+k)).hyper(:2batch).map: -> \j { +@powerfuls.race.grep: * <= 10**j }

}</lang>

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 n == 0 through 11): 1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330
 3-powerful numbers <= 10ⁿ (where n == 0 through 12): 1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136
 4-powerful numbers <= 10ⁿ (where n == 0 through 13): 1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654
 5-powerful numbers <= 10ⁿ (where n == 0 through 14): 1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770
 6-powerful numbers <= 10ⁿ (where n == 0 through 15): 1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706
 7-powerful numbers <= 10ⁿ (where n == 0 through 16): 1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740
 8-powerful numbers <= 10ⁿ (where n == 0 through 17): 1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191
 9-powerful numbers <= 10ⁿ (where n == 0 through 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 n == 0 through 19): 1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651

Sidef

Generation

<lang ruby>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)

}</lang>

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

<lang ruby>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)

}</lang>

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]