2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Collag3n Nov 13 '18 at 8:51
3
$\begingroup$

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

$\endgroup$

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.