Proof of formula of number of Power $\leq n$

Question

I recently came across this OEIS sequence: http://oeis.org/A069623.

A Perfect Power refers to a number which can be expressed in the form of $x^y$ where $x > 0$ and $y > 1$. The sequence lists the number of distinct Perfect Powers less than or equal to $n$. Here, The sequence depicts the formula as:

$a(n) = n - \sum_{k = 1}^{ \log_2n} (\mu(k)*[n^{(1/k)}-1])$

where $\mu(k)$ is the Möbius Function as usual.

I want to know the proof of derivation for this closed form of the sequence.

Answer 1

The sum

$\sum\limits_{k = 1}^{\lfloor \log_2 n\rfloor} \mu(k)*\lfloor n^{1/k}-1\rfloor$

gives you the number of non-perfect powers from $2$ to $n$.

For $k = 1$, the summand is $n-1$, that is the number all numbers from $2$ through $n$.

The basic fact is that for a number $k$,

$\lfloor n^{1/k} - 1\rfloor$

is the number of $k$-th powers (for a base $> 1$), as should be pretty clear.

So for the primes $p \leqslant \log_2 n$, the term $\mu(p) * \lfloor n^{1/p} - 1\rfloor$ subtracts the number of $p$-th powers from the number of $2 \leqslant a \leqslant n$.

The remainder is the inclusion-exclusion principle, if a number $a = b^m \quad (b > 1)$ is an $m$-th power for a composite $m$, it's subtracted for each of $m$'s distinct prime divisors. If $m = p^k$ is a prime power, $a$ is subtracted exactly once, and all is fine.

If m has at least two distinct prime divisors, it is subtracted too often, hence it must be added again for each pair of distinct prime divisors of m. If m has at least 3 distinct prime divisors, a has been re-added too often, hence it must be subtracted again for each triple of distinct prime divisors, ...

Altogether, for a composite $m$, the term

$\mu(m) * \lfloor n^{1/m} - 1\rfloor$

adds or subtracts the number of $m$-th powers $2 \leqslant b^m \leqslant n$.

If $1 < a = b^m \leqslant n$ is a perfect power and $b$ is not a perfect power, then $a$ is counted in the terms for all divisors of $m$ and no other terms, so it is added with a factor of

$\sum\limits_{d \mid m} \mu(d) = 0$

in the total sum. If $a$ is not a perfect power, it appears only in the term for $k = 1$, that is, it is added with a factor of $1$, hence

$n -\sum\limits_{k = 1}^{\lfloor \log_2 n\rfloor} \mu(k)*\lfloor n^{1/k}-1\rfloor = n - \#\lbrace a \colon (2 \leqslant a \leqslant n) \land (a = b^m \Rightarrow m = 1) \rbrace$
$\qquad\qquad = \#\lbrace a \colon (1 \leqslant a \leqslant n) \land \bigl(\exists m > 1, b\bigr)(a = b^m)\rbrace.$