Counting Perfect Powers [closed]

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 24$2^4$ and 42$4^2$, we've just counted 16$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 26=43=82$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

This works because, for any m>1$m>1$, the sum ∑d|mμ(d)$\sum _{d|m}\mu (d)$ is zero. So then, if n$n$ is a "primitive" m$m$th power, it's also a d$d$th power for each d$d$ dividing n$n$ and no others. We get −μ(d)$-\mu (d)$ for each of these, except we leave off the last −μ(1)=−1$-\mu (1)=-1$ term since we don't count first powers. Excluding that −1$-1$ leaves us with a sum of 1$1$, and we've counted each perfect power exactly once.

Now, how many perfect k$k$th powers are there in {2,3,…,N}$\{2,3,\dots ,N\}$? There are ⌊N1/k⌋−1$\lfloor N^{1/k}\rfloor -1$, which is positive as long as 2k≤N$2^k\le N$. From that, we get a formula:

That method is O(logN)$O(\log N)$. Much better.

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