 mersenneforum.org > Math Easier pi(x) approximation
 Register FAQ Search Today's Posts Mark Forums Read 2017-05-02, 21:41 #1 mathPuzzles   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 curve-fit 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!   2017-05-02, 22:59 #2 ATH Einyen   Dec 2003 Denmark 7×479 Posts    2017-05-02, 23:29 #3 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·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   2017-05-03, 00:36 #4 mathPuzzles   Mar 2017 3010 Posts Perfect! That's exactly what I'm looking for. Thanks, guys!   2017-05-03, 02:18 #5 mathPuzzles   Mar 2017 2×3×5 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!   2017-05-03, 02:27   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

3×2,797 Posts Quote:
 Originally Posted by mathPuzzles 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!
well if we test divisibility by all primes less than or equal to sqrt(n) 100% because then both divisors if n is broken down into two divisors would be greater than sqrt(n) and since sqrt(n)*sqrt(n) = n the product is greater than n therefore a contradiction occurs if both factors are greater than sqrt(n). I'll admit I don't have an answer but maybe related to ? as that's the number of primes that need testing to divide into n.

Last fiddled with by science_man_88 on 2017-05-03 at 02:32   2017-05-03, 10:22 #7 CRGreathouse   Aug 2006 135358 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/(p-1). 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.)   2017-05-03, 17:50 #8 mathPuzzles   Mar 2017 1E16 Posts That's a very clear explanation that makes both the derivation and use straightforward. Thanks much!   2017-05-04, 10:58 #9 CRGreathouse   Aug 2006 5,981 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post xtreme2k Math 34 2013-09-09 23:54 Flatlander Science & Technology 11 2011-10-12 12:39 jasong Math 5 2007-12-25 05:08 ixfd64 Math 1 2007-11-26 05:57

All times are UTC. The time now is 07:26.

Thu Aug 18 07:26:40 UTC 2022 up 4:55, 0 users, load averages: 0.88, 0.93, 1.01