# Prime counting. Meissel, Lehmer: is there a general formula?

I am looking for a general forumla to count prime numbers on which the Meissel and Lehmer formula are based:
$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}{P_k(x,a)}$$

Wiki - prime counting - Meissel Lehmer

More precisely, I am looking for the detailed description of the $P_k$ for $k>3$.

$P_k(x,a)$ counts the numbers$\leqslant x$ with exactly $k$ prime factors all greater than $p_a$ ($a^{th}$ prime), but in the full general formula, this last condition is not necessary.

The Meissel formula stops at $P_2$ (and still uses some $\phi$/Legendre parts)
Wolfram - Meissel

The Lehmer formula stops at $P_3$ (and still uses some $\phi$/Legendre parts)
Wolfram - Lehmer

I don't find anything about the general formula (using all the $P_k$ terms). Is there any paper on it? Why stop at $P_3$? is it a performance issue?

Lehmer vaguely talk about it in his 1959 paper
On the exact number of primes less than a given limit

Prime counting Meissel, Lehmer, ...

Thanks

Edit: by "a general formula on which the Meissel and Lehmer formula are based", I meant the one they tend to (with all $P_k$), not the one they started from (Legendre, with no $P_k$). Sorry if it was not clear.

• – Max Alekseyev Apr 14 '18 at 2:52
• Legendre (which count integers less then $x$ not divisible by the first $a$ primes) is used in the first part of the general formula: $\pi(x)=\phi(x,a)+a-1$ where $a=\pi(\sqrt[2]{x})$ if we set all $P_k=0$. Meissel go one step further by lowering $a$ and using $P_2(x,a)$ to "compensate", which is more efficient. Lehmer lowers $a$ even further. In the "full formula", Legendre part can be skipped (if we set $a=0$) and $\phi(x,a)+a-1$ become $x-1$, but this is not mandatory, we can still set $a$ to the value we want (it's a kind of cursor which "distribute the work" between $\phi$ and $P_k$). – Collag3n Apr 14 '18 at 18:13

The answer to the question 'why stop at $P_3$?' is simply: because the choice $p_a^4>x$ implies $P_k=0$ for $k\geq 4$. So the papers that only include $P_2$ and $P_3$ in fact do start from the full formula with all $P_k$'s, it's just that the rest is assured to be identically zero by a judicious choice of $p_a$.

The performance gain if one takes a smaller $p_a$ so that higher $P_k$'s are nonzero is small (a factor $1/\log x$ when going from $p_a\gtrsim x^{1/3}$ to $p_a\gtrsim x^{1/4}$), at the expense of a greater complexity of the calculation. Since now polynomially faster algorithms are available (Lagarias, Miller & Odlyzko's algorithm is a factor $1/x^{1/3}$ faster than Meissel-Lehmer) there does not seem to be a motivation to speed up Meissel-Lehmer logarithmically by reducing $p_a$ below $x^{1/4}$.

• Yes, this is a choice. But is there any reason to make this choice? You could lower $a$ further to include $P_4$. You could do it again to include $P_5$. Why not? – Collag3n Apr 15 '18 at 20:02
• I guess it's just that lowering $a$ adds much complexity with little gain. – Carlo Beenakker Apr 16 '18 at 6:17
• Indeed, the sweet spot seems to be with $a=\pi(\alpha\sqrt[3]{x})$ (sweet.ua.pt/tos/bib/5.4.pdf). This is done by tweaking the algorithm, but I am still curious if there is still some gains to make by going from $P_3$ to $P_4$ and further. Outside the performance aspect, if you have any link about the $P_k$ for $k>3$, I am interested. – Collag3n Apr 16 '18 at 18:21
• I have searched quite extensively, but all papers I found take $a$ large enough so that $P_k=0$ for $k>3$. – Carlo Beenakker Apr 18 '18 at 6:01
• Yes, very hard to find something. I find it strange because Legendre set $a=\pi(\sqrt[2]{x})$, Meissel set $a=\pi(\sqrt[3]{x})$, and Lagarias get the best performances in between. You might think there is no point to look past Meissel, but Lehmer improve Meissel by setting $a=\pi(\sqrt[4]{x})$, so looking further might still be interesting (perhaps also with some tweaks). Anyway, thanks for the search. I think you are right, the gain is probably too small compared to the added complexity. – Collag3n Apr 19 '18 at 17:25

Here it is:

$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}\underbrace{{\Bigg\{ \sum\limits_{n_2=a+1}^{\pi(\sqrt[k]{x})} \sum\limits_{n_3=n_2}^{\pi\big(\sqrt[k-1]{\frac{x}{p_{n_2}}}\big)} \sum\limits_{n_4=n_3}^{\pi\Big(\sqrt[k-2]{\frac{x}{p_{n_2}\cdot p_{n_3}}}\Big)} ... \sum\limits_{n_k=n_{k-1}}^{\pi\Bigg(\sqrt[2]{\frac{x}{\prod\limits_{i=2}^{k-1}{p_{n_i}}}}\Bigg)} {\Bigg[\pi(\frac{x}{\prod\limits_{i=2}^{k}{p_{n_i}}})-\pi(p_{n_{k}})+1\Bigg]} \Bigg\}}}_{P_k(x,a)}$$

$a$ can be set to $\pi(\sqrt[{\lceil log_2(x) \rceil}]{x})=0$, so $\phi(x,a)+a-1$ become $x-1$ but as said above, $a$ can be set to any value up to $\pi(\sqrt[2]{x})$ (kindof cursor to distribute the "work" between $\phi$ and $P_k$)

(Note: $n_1=a+1$)

$\phi(x,a)+a-1$ can also be replaced by a more efficient recursive function which looks a lot like the right part (involving $\lfloor \frac{x}{\prod{p_{n_i}}} \rfloor -p_{n_k}+1$)