20170502, 21:41  #1 
Mar 2017
2·3·5 Posts 
Easier pi(x) approximation
I 'm looking for a decent estimator for \(\pi(n)\) for n in the range of 10K to 100M. The Logarithmic integral function would be more than accurate enough for my estimate needs, but it would be annoying to code. I am using the cuder \(x\over \ln x\) estimator now, but I want it to be more accurate. Is there an easy second order correction term I could add? I suppose I could curvefit a correction term (since I know the range I have now) but maybe there's a simpler first order expansion I could just put in. I tried to get Mathematica to output a Taylor series estimator but my math and Mathematica skills are not good enough to get a usable correction in a simple form of say \(x\over \ln x\) + \(\alpha({x\over \ln x})^2\) or \(x\over \ln x\) + \(\alpha \ln x\)
Thanks! 
20170502, 22:59  #2 
Einyen
Dec 2003
Denmark
6527_{8} Posts 

20170502, 23:29  #3 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
In approximate order of accuracy, with caveats, and the upper/lower bound average depends heavily on which bounds you use.
n/log(n) n/(log(n)1) n/(log(n)  1  1/log(n)) average of upper/lower bounds, of the many bounds available. See multiple papers by Dusart, Axler, Buthe. Asymptotic, truncated where you'd like: n/log(n) * (1 + 1/log(n) + 2/log^2(n) + 6/log^3(n) + 24/log^4(n) + 120/log^5(n) + 720/log^6(n) + 5040/log^7(n) + 40320/log^8(n) + ... ) Li Truncated R using a few terms of Moebius / Li R 
20170503, 00:36  #4 
Mar 2017
2·3·5 Posts 
Perfect! That's exactly what I'm looking for. Thanks, guys!

20170503, 02:18  #5 
Mar 2017
11110_{2} Posts 
Working great!
But my ultimate estimations are all wrong due to another error I've made. My final goal is trying to estimate the chance that a large random number n is prime given that it has no prime factors less than some C. The chance that n is prime is well approximated by \( \pi(n)\over n\) and for some reason I thought the calculation for the probability of n being prime when it has no divisors less than C was \({\pi[n]\over n \pi[C]}\). Nope, I was wrong. What is the coarse estimator for this? I'm sure I've seen it in terms of \(\pi(n)\) and \(\pi(C)\) but deriving it myself is eluding me. Thanks again! 
20170503, 02:27  #6  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Last fiddled with by science_man_88 on 20170503 at 02:32 

20170503, 10:22  #7 
Aug 2006
1763_{16} Posts 
If you know that a number isn't divisible by a prime p, the 'probability' that it is prime increases by a factor of p/(p1). You can use Mertens' theorem here if C is small enough compared to n:
so and so the overall 'probability' is roughly This should be valid for x less than, say, n^0.4. (As you get close to n^0.5, weird things happen; Granville has a nice expository paper on this. When you hit n^0.5 of course the probability goes to 1.) 
20170503, 17:50  #8 
Mar 2017
11110_{2} Posts 
That's a very clear explanation that makes both the derivation and use straightforward. Thanks much!

20170504, 10:58  #9 
Aug 2006
5,987 Posts 
Glad to help.
You can actually replace n^0.4 with n^c for any c < 1/2, but the closer you get to 1/2 the higher up you need to go before you get a decent approximation. As you can see it gives the wrong answer if you use n^0.5 or above, the Granville article I mentioned explains why this is so. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Would finding a definate Pi value easier if...  xtreme2k  Math  34  20130909 23:54 
Why does wetting the cotton make it easier to thread the needle?  Flatlander  Science & Technology  11  20111012 12:39 
Will prime finding become easier?  jasong  Math  5  20071225 05:08 
approximation of possible selfavoiding walks  ixfd64  Math  1  20071126 05:57 