Reference request: a formula for the prime-counting function

Question

Let $\pi(n)$ denote the prime counting function, which returns the number of primes less than or equal to $n$. When one asks WolframAlpha for $\pi(10,000)$ (or any suitably small number), it displays the result, along with several formulas it uses to calculate this result. The final listed formula caught my eye - WolframAlpha claims that $$\pi(n) = -\sum_{k=1}^{\log_2(n)}\mu(k)\sum_{l=2}^{\lfloor \sqrt[k]{n} \rfloor} \left\lfloor \frac{\sqrt[k]{n}}{l}\right\rfloor \mu(l)\Omega(l)$$ where $\mu(k)$ is the Mobius function and $\Omega(l)$ is the function that gives the number of prime factors counting multiplicities in $l$.

Question: Does this formula have a name? Where is it's correctness proven? Alternatively, I'd be interested in a proof of it's correctness.

Answer 1

I didn't find any references yet, but it looks very interesting. Instead of doing the usual inclusion/exclusion on composite numbers, it does inclusion/exclusion on prime powers.

$$\pi(n) = -\sum\limits_{k=1}^{\log_2(n)}\mu(k)\sum\limits_{l=2}^{\lfloor \sqrt[k]{n} \rfloor} \left\lfloor \frac{\sqrt[k]{n}}{l}\right\rfloor \mu(l)\Omega(l)$$

It starts with $k=1$, where we get the number of primes and primes powers less than $n$ or in other word: $\pi(n)+\pi(\sqrt[2]{n})+\pi(\sqrt[3]{n})+\pi(\sqrt[4]{n})+\pi(\sqrt[5]{n})+...+\pi(\sqrt[\log_2(n)]{n})$

With $k=2$ we start to remove power of primes that are multiple of $2$ ($2^2,2^4,2^6,...,3^2,3^4,3^6,...$)

With $k=3$ we start to remove power of primes that are multiple of $3$ ($2^3,2^6,...,3^3,3^6,...$)

With $k=6$ we start to add the power of primes that are multiple of $6$ and were removed twice above ($2^6,...,,3^6,...$)

In the end we are left with $\pi(n)$

Now, to show it, I think you can use some properties of the binomial coeficient.

Let's look at $k=1$ again:

$$-\sum\limits_{l=2}^{n} \left\lfloor \frac{n}{l}\right\rfloor \mu(l)\Omega(l)$$

without $\Omega(l)$ we have the classic inclusion/exclusion which remove composites counted multiple times:

$$-\sum\limits_{l=2}^{n} \left\lfloor \frac{n}{l}\right\rfloor \mu(l)=\sum\limits_{p_i<=n}\lfloor \frac{n}{p_i} \rfloor-\Sigma\Sigma\lfloor \frac{n}{p_i\cdot p_j} \rfloor+\Sigma\Sigma\Sigma\lfloor \frac{n}{p_i\cdot p_j\cdot p_k} \rfloor-...=(n-1)$$

e.g. $210=2\cdot3\cdot5\cdot7$ is counted in $\lfloor \frac{n}{2} \rfloor$, $\lfloor \frac{n}{3} \rfloor$, $\lfloor \frac{n}{5} \rfloor$, $\lfloor \frac{n}{7} \rfloor$, what is counted twice is removed with $\lfloor \frac{n}{2\cdot3} \rfloor$, $\lfloor \frac{n}{2\cdot5} \rfloor$,$\lfloor \frac{n}{2\cdot7} \rfloor$,$\lfloor \frac{n}{3\cdot5} \rfloor$,$\lfloor \frac{n}{3\cdot7} \rfloor$,$\lfloor \frac{n}{5\cdot7} \rfloor$, what was removed too much is added back in $\lfloor \frac{n}{2\cdot3\cdot5} \rfloor$,$\lfloor \frac{n}{2\cdot3\cdot7} \rfloor$,$\lfloor \frac{n}{2\cdot5\cdot7} \rfloor$, $\lfloor \frac{n}{3\cdot5\cdot7} \rfloor$, and finaly $\lfloor \frac{n}{2\cdot3\cdot5\cdot7} \rfloor$ is removed.

In other word, with composites appearing multiple times (here having 4 distinct prime factors), we only count one of them in the end: $$\binom{4}{1}-\binom{4}{2}+\binom{4}{3}-\binom{4}{4}=1$$

And this is a property of the binomial coeficients (here with $m$ distinct prime factors):

$$\sum\limits_{i=1}^{m}(-1)^{i+1}\binom{m}{i}=1$$

Now if you put back $\Omega(l)$, we have this: $$-\sum\limits_{l=2}^{n} \left\lfloor \frac{n}{l}\right\rfloor \mu(l)\Omega(l)=1\cdot\sum\limits_{p_i<=n}\lfloor \frac{n}{p_i} \rfloor-2\cdot\Sigma\Sigma\lfloor \frac{n}{p_i\cdot p_j} \rfloor+3\cdot\Sigma\Sigma\Sigma\lfloor \frac{n}{p_i\cdot p_j\cdot p_k} \rfloor-4\cdot...$$ Now what happens to the composite of our exemple above is this: $$1\cdot\binom{4}{1}-2\cdot\binom{4}{2}+3\cdot\binom{4}{3}-4\cdot\binom{4}{4}=0$$

And this is another property of the binomial coeficients:

$$\sum\limits_{i=1}^{m>1}(-1)^{i+1}\cdot i\cdot\binom{m}{i}=0$$ Note: for $m=1$ the above equation is equal to $1$.

What it means is that no composite are counted. Only numbers with 1 factor are (primes and prime powers).

For $k>1$ the resoning is probably the same, but I had not much time yet.

EDIT: Sorry for the late update, I couldn't look at it earlier. I guess that you already looked at it by now, but for thoose who didn't: It is indeed the same reasoning. for $k=2$, primes and prime powers are counted up to $\sqrt[2]{n}$ which is a count of prime+prime powers squared, for $k=3$, primes+primes power cubes are counted, and so on....

Answer 2

(for $s$ large enough)

$$F(s)=\int_1^\infty \sum_l \lfloor y/l\rfloor \mu(l)\Omega(l) y^{-s-1}dy = \sum_l \mu(l) \Omega(l)l^{-s}\int_1^\infty \lfloor y\rfloor y^{-s-1}dy$$ $$=\frac{\zeta(s)}{s}\sum_l \mu(l) \Omega(l)l^{-s}=\frac{1}{s}\sum_n n^{-s}\sum_l \mu(l) l^{-s} \sum_{p | l}1 $$ $$ = \frac1s \sum_p \sum_{n,l, p |l} \mu(l) n^{-s} l^{-s} = \frac1s \sum_p \sum_d d^{-s}\sum_{ p L | d} \mu(pL)$$

If $v_p(d)=0$ then $\sum_{ p L | d} \mu(pL)=0$.

If $v_p(d)>0$ then $$\sum_{ p L | d} \mu(pL)=\sum_{L| dp^{-v_p(d)}}\mu(p)\mu(L)=-1_{d = p^{v_p(d)}}$$

Thus $$F(s)=-\frac1s \sum_p \sum_{r\ge 1} p^{-rs}$$

$$-\int_1^\infty \sum_k \mu(k)\sum_l \lfloor x^{1/k}/l\rfloor \mu(l)\Omega(l) x^{-s-1}dx=-\sum_k \mu(k) F(ks)k $$ $$= \frac1s\sum_k \mu(k)\sum_p \sum_{r\ge 1}p^{-rks}= \frac1s \sum_p p^{-s}= \int_1^\infty \pi(x)x^{-s-1}dx$$ Which proves your formula $-\sum_k \mu(k)\sum_l \lfloor x^{1/k}/l\rfloor \mu(l)\Omega(l)=\pi(x)$.