[suggestion] Counting of prime powers and perfect powers

[trizen]

Hi. I would like to suggest two more functions, that may be of general interest:

• power_count(n) = number of perfect powers <= n (OEIS: A069623)
• prime_power_count(n) = number of prime powers <= n (OEIS: A025528)

An alternative name for power_count can be perfect_power_count.

Both functions can be implemented quite easily, using the following formulas:

power_count(n) = n - Sum_{k=1..floor(log_2(n))} μ(k) * (floor(n^(1/k)) - 1)
prime_power_count(n) = Sum_{k=1..floor(log_2(n))} π(floor(n^(1/k)))

Code example:

use 5.014;
use ntheory qw(:all);
use experimental qw(signatures);

sub power_count ($n) {
    subint($n, vecsum(map { mulint(moebius($_), subint(rootint($n, $_), 1)) } 1..logint($n, 2)));
}

sub prime_power_count ($n) {
    vecsum(map { prime_count(rootint($n, $_)) } 1..logint($n, 2));
}

say join(', ', map { power_count($_) } 1..50);
say join(', ', map { prime_power_count($_) } 1..50);

say '-'x80;

say join(', ', map { power_count(powint(10, $_)) } 1..30);
say join(', ', map { prime_power_count(powint(10, $_)) } 1..13);

Thanks for considering!

[danaj]

perfect_power_count(n) and prime_power_count(n) checked in, tests to follow.