View source for Powerful numbers

{{draft task|Mathematics}}

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

* [https://en.wikipedia.org/wiki/Powerful_number Wikipedia, Powerful number]

* [https://oeis.org/A001694 OEIS A001694: 2-powerful numbers]

* [https://oeis.org/A036966 OEIS A036966: 3-powerful numbers]

* [https://oeis.org/A036967 OEIS A036967: 4-powerful numbers]

* [https://oeis.org/A069492 OEIS A069492: 5-powerful numbers]

* [https://oeis.org/A069493 OEIS A069493: 6-powerful numbers]

* [https://oeis.org/A062762 OEIS A062762: number of powerful numbers <= 2^n]

* [https://oeis.org/A118896 OEIS A118896: number of powerful numbers <= 10^n]

<br><br>
=={{header|Go}}==
{{trans|Perl}}
Curiously, the 'powerful' function is producing duplicates which the other existing solutions don't seem to suffer from. It's easily dealt with by using a set (rather than a slice) but means that we're unable to take advantage of the counting shortcut - not that it matters as the whole thing still runs in less than 0.4 seconds! 
<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>

{{out}}
<pre>
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]
</pre>


=={{header|Julia}}==
{{trans|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)
        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>{{out}}
<pre>
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]
</pre>

=={{header|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>
{{out}}
<pre>
For k=2  there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]
For k=3  there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000]
For k=4  there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000]
For k=5  there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000]
For k=6  there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000]
For k=7  there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000]
For k=8  there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000]
For k=9  there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000]
For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
</pre>

===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>
{{out}}
<pre>
Number of  2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330}
Number of  3-powerful <= 10^j for 0 <= j < 13: {1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136}
Number of  4-powerful <= 10^j for 0 <= j < 14: {1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654}
Number of  5-powerful <= 10^j for 0 <= j < 15: {1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770}
Number of  6-powerful <= 10^j for 0 <= j < 16: {1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706}
Number of  7-powerful <= 10^j for 0 <= j < 17: {1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740}
Number of  8-powerful <= 10^j for 0 <= j < 18: {1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191}
Number of  9-powerful <= 10^j for 0 <= j < 19: {1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868}
Number of 10-powerful <= 10^j for 0 <= j < 20: {1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651}
</pre>

=={{header|Perl 6}}==
{{works with|Rakudo|2020.01}}
{{trans|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>
{{out}}
<pre>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</pre>

=={{header|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>
{{out}}
<pre>
For k=2  there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]
For k=3  there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000]
For k=4  there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000]
For k=5  there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000]
For k=6  there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000]
For k=7  there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000]
For k=8  there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000]
For k=9  there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000]
For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
</pre>
===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>
{{out}}
<pre>
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]
</pre>