Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

Question

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ $\pi(x)$ is the prime counting function and $p_m$ is the $m$th prime that is previous of or equal to $\sqrt{x}$. As I can remember this was a rather simple result derived by a sieve, but I don't remember all the details so please point out any corrections if needed. Utilizing Mertens' third theorem I came to the conclusion that $$\lim \limits_{x \to \infty}\pi(x)\sim\frac x{e^\gamma\ln(p_m)}+m-1.$$ Testing these equations don't give particularly nice results and I am curious as to how sound all my math was and if it was sound, why such deviation from the actual value of $\pi(x)$?

Answer 1

The idea behind it is apparently that every positive integer $\leqslant x$ that is coprime to all primes $\leqslant \sqrt{x}$ is a prime - except for the special case $1$, so to count the primes $\leqslant x$, you count the positive integers $\leqslant x$ that are coprime to all primes $\leqslant \sqrt{x}$, subtract $1$ (since $1$ isn't prime), and add the number of primes $\leqslant \sqrt{x}$. So far, that is entirely correct.

Then you approximate $\Phi(x,m) = \operatorname{card} \{ n \leqslant x : p_k \nmid n \text{ for } 1 \leqslant k \leqslant m\}$ by

$$x\cdot \prod_{k = 1}^m \biggl(1 - \frac{1}{p_k}\biggr)$$

for $m = \pi(\sqrt{x})$. And that's where things go slightly awry.

The idea is sound, every second number is divisible by $2$, so we have $\approx x\bigl(1 - \frac{1}{2}\bigr)$ numbers $\leqslant x$ that are not divisible by $2$ - with an error of at most $\frac{1}{2}$. Of the numbers not divisible by $2$, every third is divisible by $3$, so you have $\approx x\bigl(1-\frac{1}{2}\bigr)\bigl(1 - \frac{1}{3}\bigr)$ numbers $\leqslant x$ neither divisible by $2$ nor by $3$. The error is still not large, at most $\frac{2}{3}$. And so on. But, the more primes you take, the larger the error becomes, and if you take all primes up to $\sqrt{x}$, the error becomes quite significant.

Let $P = \prod\limits_{k = 1}^m p_k$. Then

$$x\cdot \prod_{k = 1}^m \biggl(1 - \frac{1}{p_k}\biggr) = x\sum_{d\mid P} \frac{\mu(d)}{d} = \sum_{d \mid P} \mu(d) \frac{x}{d},\tag{1}$$

where $\mu$ is the Möbius function. The correct value is, by inclusion-exclusion,

$$\Phi(x,m) = \sum_{d\mid P} \mu(d) \biggl\lfloor \frac{x}{d}\biggr\rfloor.\tag{2}$$

The difference is thus

$$\sum_{d\mid P} \mu(d) \biggl(\frac{x}{d} - \biggl\lfloor \frac{x}{d}\biggr\rfloor\biggr).$$

Every term in the sum is less than $1$ in absolute value, but there are so many terms in the sum - $P$ has $2^m$ divisors - that even small deviations can add up to large values.

Generally, we have $m = \pi(\sqrt{x}) \sim \dfrac{2\sqrt{x}}{\log x}$, so for larger $x$, the number of terms in the sum is huge compared to $x$.

I don't know of an easy way to estimate the error except through the prime number theorem and Mertens' theorem. The correction $m-1$ for the primes $\leqslant \sqrt{x}$ and $1$ is insignificant (for large $x$), and by the prime number theorem we have $\pi(x)\sim \dfrac{x}{\log x}$, while by Mertens' theorem

$$x\cdot\prod_{k = 1}^m \biggl(1-\frac{1}{p_k}\biggr) \sim \frac{x}{e^\gamma \log p_m} \sim \frac{2x}{e^\gamma\log x},$$

so the approximation is asymptotically off by a factor of $2e^{-\gamma} \approx 1.1229$.

Answer 2

The second formula is not correct, in the usual sense, as $\pi(x) \sim x/ \ln x $ and this is not what you get, as $\ln(p_m)$ is about $(\ln x)/2$ while $e^{\gamma}$ is not $2$ but smaller.

The first formula should be obtained by the argument that for each prime $p$ you sieve out $x/p$ of the numbers so to see what is left you multiply by $(1-1/p)$. The $m-1$ is likely added to compensate for the fact that you also would have taken out $p$ itself by the above (but this is actually negligible).

This is a reasonably heuristic but you "sieve" some number twice, like $15$ with $3$ and $5$.

In sum, this is an alright idea, but there are things to be improved.