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 2×52×67 Posts https://arxiv.org/abs/1002.0442 $\pi(x) \geq \frac{x}{ln x}(1 + \frac{1}{ln x}) for x \geq 599$ $\pi(x) \leq \frac{x}{ln x}(1 + \frac{1.2762}{ln x}) for x > 1$ $\pi(x) \geq \frac{x}{ln x - 1} for x \geq 5393$ $\pi(x) \leq \frac{x}{ln x - 1.1} for x \geq 60184$ $\pi(x) \geq \frac{x}{ln x}(1 + \frac{1}{ln x} + \frac{2}{(ln x)^2}) for x \geq 88783$ $\pi(x) \leq \frac{x}{ln x}(1 + \frac{1}{ln x} + \frac{2.334}{(ln x)^2}) for x \geq 2,953,652,287$
 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 2×3×5 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

2×5×839 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 $\pi(\sqrt{n})$ ? 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 3×1,993 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: $\prod_{p \le x} \frac{p-1}{p} \approx \frac{e^{-\gamma}}{\log x}$ so $\prod_{p \le x} \frac{p}{p-1} \approx e^{\gamma}\log x$ and so the overall 'probability' is roughly $\frac{e^\gamma\log x}{\operatorname{li}(n)}$ 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 111102 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 3×1,993 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.

 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 21:55.

Sat Aug 13 21:55:59 UTC 2022 up 37 days, 16:43, 2 users, load averages: 1.30, 1.79, 1.92