1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where did the word "Factors" come in? $\endgroup$ – Thomas Andrews Jun 24 '13 at 15:25
  • $\begingroup$ My bad. Edit done. $\endgroup$ – divanshu Jun 24 '13 at 17:26
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ And what for non-prime 'p' ? How's the inclusion exclusion working in this case? $\endgroup$ – divanshu Jun 24 '13 at 15:13
  • $\begingroup$ @divanshu Okay, I'll elaborate. $\endgroup$ – Daniel Fischer Jun 24 '13 at 15:16
  • $\begingroup$ Thanks alot. Lastly, can you please explain me this one line: "then a is counted in the terms for all divisors of m and no other terms" ? $\endgroup$ – divanshu Jun 24 '13 at 19:13
  • $\begingroup$ @divanshu If a is an m-th power, it is also a d-th power for each divisor d of m [a 12-th power is also a 6-th power, a 4-th power, a cube, and a square; and of course every number is a 1-st power]. And if a = b^m where b is not a perfect power (that is, m is the largest exponent e such that a is an e-th power), then a is a k-th power if and only if k is a divisor of m. $\endgroup$ – Daniel Fischer Jun 24 '13 at 19:56
  • $\begingroup$ Thank you. I finally understood it completely. $\endgroup$ – divanshu Jun 24 '13 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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