# Counting Perfect Powers [closed]

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})$$?

## 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.

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.

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.