
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 6th, 2015, 11:08 AM  #1 
Member Joined: Jun 2015 From: Ohio Posts: 99 Thanks: 19  Approximation for the Prime Counting Function
I was playing around with some of my sieve work and I came up with this interesting way to approximate the prime counting function (at least for small values, haven't tested larger ones). I wanted to throw it out here to see what you guys think of it compared to other known methods. Say you want to find the number of primes less than some number, 3721 for example. First, take the square root of the number sqrt(3721) = 61 Now take the product of (p  1)/p for all primes from 3 up to 61 60/61 * 58/59 * 52/53 * ... * 2/3 Subtract 1 from the original number, divide it by 2, then multiply it by that product. (3721  1)(60/61 * 58/59 * 52/53 * 46/47 ... * 2/3)/2 You get about 490 compared to an actual answer of 519. As far as I know, the accuracy increases with larger numbers. 
November 6th, 2015, 11:39 AM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
\pi_\text{approx}(x) := \frac{x1}{2}\prod_{p\le\sqrt x}\frac{p1}{p} $$ By Mertens' theorem, $$ \prod_{p\le x}\frac{p1}{p} \approx \frac{e^{\gamma}}{\log x} $$ and so $$ \pi_\text{approx}(x) \approx \frac{x1}{2}\frac{e^{\gamma}}{\log\sqrt x} \approx \frac{1}{e^{\gamma}}\frac{x}{\log x} = 0.561459\ldots\frac{x}{\log x}. $$ But this doesn't match your numbers: it gives $\pi_\text{approx}(3721)=244.752\ldots,$ as you can verify with this GP script: Code: piapprox(x)=(x1)/2*prodeuler(p=2,sqrt(x),11/p) piapprox(3721) Last edited by CRGreathouse; November 6th, 2015 at 11:46 AM.  
November 6th, 2015, 12:39 PM  #3 
Member Joined: Jun 2015 From: Ohio Posts: 99 Thanks: 19 
You divided by an extra 2 I believe. My exact answer is exactly double that. I only divide by primes 3 to 61, not 2 to 61 so I think that is the issue. Thanks for the information though, I had not heard of this theorem before I came to this.

November 6th, 2015, 02:21 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
Yes, it's very useful!  

Tags 
approximation, counting, function, prime 
Thread Tools  
Display Modes  

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