Counting Perfect Powers 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})$?
 A: 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.
A: 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.
