# Reference request: a formula for the prime-counting function

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.

• Looks like it tries to build the legendre formula in a highly inneficient way. Interesting formula, I'll dig into it as soon as I find some time. The values used to sum the thing reminds me of what I used for this mathoverflow.net/a/300060/118898 – Collag3n Nov 13 '18 at 8:51

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{n})+\pi(\sqrt{n})+\pi(\sqrt{n})+\pi(\sqrt{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{n}$$ which is a count of prime+prime powers squared, for $$k=3$$, primes+primes power cubes are counted, and so on....