0
$\begingroup$

The perfect powers are numbers of the form $x^y$ with $x \geq 1$ and $y>1$. I'm interested in counting the exact number of perfect powers not greater than $N$. I'd like to ask if there's some method much better than enumerating all perfect powers in $O(\sqrt{N})$?

$\endgroup$

closed as off-topic by user21820, Saad, Xander Henderson, José Carlos Santos, Alexander Gruber Apr 29 at 1:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Saad, Xander Henderson, José Carlos Santos, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.

4
$\begingroup$

There's an obvious approach we can do - count the squares, the cubes, the fourth powers, and so on.

But then, we look closer. If we count $2^4$ and $4^2$, we've just counted $16$ twice. All of the fourth powers are already squares; we've already counted them, so we should put zero weight on those fourth powers.
Then, the next place we run into trouble is the sixth powers. We can write $2^6=4^3=8^2$; each sixth power is a square and a cube, already double-counted. We have to subtract the number of sixth powers to balance this.

Is there a pattern to the weights we need here? Why, yes. Let $\mu$ be the Möbius function of number theory. The count we seek is $$\text{# perf. powers}\in \{2,3,\dots,N\} = \sum_{k\ge 2}-\mu(k)\cdot(\text{# perf. kth powers}\in \{2,3,,\dots,N\})$$ This works because, for any $m>1$, the sum $\sum_{d|m}\mu(d)$ is zero. So then, if $n$ is a "primitive" $m$th power, it's also a $d$th power for each $d$ dividing $n$ and no others. We get $-\mu(d)$ for each of these, except we leave off the last $-\mu(1)=-1$ term since we don't count first powers. Excluding that $-1$ leaves us with a sum of $1$, and we've counted each perfect power exactly once.

Now, how many perfect $k$th powers are there in $\{2,3,\dots,N\}$? There are $\left\lfloor N^{1/k}\right\rfloor - 1$, which is positive as long as $2^k\le N$. From that, we get a formula: $$\text{# perf. powers}\in \{2,3,\dots,N\} = \sum_{k=2}^{\lfloor\log_2 N\rfloor}-\mu(k)\left(\left\lfloor N^{1/k}\right\rfloor - 1\right)$$ That method is $O(\log N)$. Much better.

Addendum: The original statement $x^y$ with $x\ge 1$ includes $1$ as a perfect power. To include that, just add $1$ to the count.

$\endgroup$
1
$\begingroup$

Using inclusion-exclusion, the number of perfect powers up to $N$ is $$ 1 -\sum_{k = 2}^{\lfloor \log_2 N\rfloor} \mu(k)\lfloor N^{1/k} - 1 \rfloor, $$ where $\mu$ is the Möbius function. (Note that the restriction of the upper limit of the sum to $\lfloor \log_2 N\rfloor$ requires that some care be taken to ensure that $1$ is counted exactly once.)

Here's a worked example for $N=1000$: $$ \begin{array}{c|c|c} k&\mu(k)&\lfloor N^{1/k} - 1\rfloor\\ \hline 2&-1&30\\ 3&-1&9\\ 4&0&4\\ 5&-1&2\\ 6&1&2\\ 7&-1&1\\ 8&0&1\\ 9&0&1\\ \end{array} $$ Thus the number of perfect powers up to $1000$ is $1 - ((-30) + (-9) + (-2) + 2 + (-1)) = 41$.

To check your results, you can compare with sequence A089579, which gives the number of perfect powers, excluding $1$, less than $10^n$. Thus its third entry is $39$, as both $1$ and $1000$ are not counted.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.