My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree1Thanks
  • 1 Post By SteveC
LinkBack Thread Tools Display Modes
April 6th, 2018, 12:45 PM   #1
Joined: Sep 2017
From: Belgium

Posts: 19
Thanks: 7

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

I am looking for a general formula to count prime numbers on which the Meissel and Lehmer formulas are based:
$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_2(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 $<=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

Deleglise talks about performances here
Prime counting Meissel, Lehmer, ...


Last edited by skipjack; April 6th, 2018 at 02:46 PM.
Collag3n is offline  
June 22nd, 2019, 12:24 PM   #2
Joined: Sep 2016
From: Tempe, Arizona

Posts: 6
Thanks: 1

The answer I posted to a question titled "one to one mapping between the floor function and the Riemann prime counting function" at may perhaps provide some insight. I've also derived an alternate expression for $b_{\pi}(n)$ if you're interested.
Thanks from Collag3n
SteveC is offline  
June 23rd, 2019, 09:46 AM   #3
Joined: Sep 2017
From: Belgium

Posts: 19
Thanks: 7

Hi Steven.

I already looked at $a_{\pi}(n)=\sum\limits_{d|n}\mu(d)\,\omega(\frac{ n}{d})$ and $\omega(n)=\sum\limits_{d|n}a_{\pi}(d)$

But never at $b_{\pi}(n)$, so yes, I am interested.

I noticed that unless $n$ contains one square in the prime factorization (no need to be full square-free), $b_{\pi}(n)=-\mu(n)\omega(n)$
But in this case, I have $K(x)=\sum\limits_{n=1}^x b_{\pi}(n)\lfloor \frac{x}{n}\rfloor$ instead of $\pi(x)=\sum\limits_{n=1}^x b_{\pi}(n)\lfloor \frac{x}{n}\rfloor$

For my initial question, I found a formula, but I am still interested in any references/paper on the subject:


Last edited by Collag3n; June 23rd, 2019 at 09:53 AM.
Collag3n is offline  
July 21st, 2019, 11:39 AM   #4
Joined: May 2018
From: NYC

Posts: 11
Thanks: 0

I have an exact formula, given by a power series

In my paper, An Exact Formula for the Prime Counting Function (
I derive the very first power series for $\displaystyle \pi(x)$, which is a function of the values of the zeta function at the positive integers (hence, they have closed forms) and which doesn't depend on the zeros of the Riemann zeta function (hence, it's easier to compute.)

It's still a power series, whose calculation becomes difficult for large values of $\displaystyle x$.

The formula is:
$\displaystyle \pi(x)=-8\sum _{h=1}^{\infty} H_{-2h}(x)\sum _{i=1}^h \log\zeta(2i)\sum _{v=i}^{h}\frac{(-1)^{h-v}(4\pi )^{2h-2v}}{\zeta(2v-2i)(2h+2-2v)!}$

where $\displaystyle H_{-2h}(x)$ is the sum of the $2h$-th powers of the first $x$ positive integers.

I'm still thinking about the problem of how to turn this power series into an asymptotic formula.
If you know how to do this, be my guest.
jrsousa2 is offline  

  My Math Forum > College Math Forum > Number Theory

counting, formula, general, lehmer, meissel, prime

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Approximation for the Prime Counting Function numberguru1 Number Theory 3 November 6th, 2015 01:21 PM
A property of the prime counting function. Jonas Castillo T Number Theory 6 May 9th, 2015 06:26 PM
An equation of prime counting function. jim198810 Number Theory 6 March 26th, 2015 07:31 PM
Question on prime counting function \pi fafa Number Theory 24 June 22nd, 2013 12:55 AM
Lower Bound for the Prime Counting Function guynamedluis Number Theory 2 April 21st, 2012 12:48 PM

Copyright © 2019 My Math Forum. All rights reserved.