Easier pi(x) approximation

mathPuzzles · 2017-05-02, 21:41

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!

ATH · 2017-05-02, 22:59

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$

danaj · 2017-05-02, 23:29

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

mathPuzzles · 2017-05-03, 00:36

Perfect! That's exactly what I'm looking for. Thanks, guys!

mathPuzzles · 2017-05-03, 02:18

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!

science_man_88 · 2017-05-03, 02:27

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.

CRGreathouse · 2017-05-03, 10:22

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.)

mathPuzzles · 2017-05-03, 17:50

That's a very clear explanation that makes both the derivation and use straightforward. Thanks much!

CRGreathouse · 2017-05-04, 10:58

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.

2017-05-02, 21:41	#1
mathPuzzles Mar 2017 2⁵ 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-03, 02:18	#5
mathPuzzles Mar 2017 32₁₀ 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!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Would finding a definate Pi value easier if...	xtreme2k	Math	34	2013-09-09 23:54
Why does wetting the cotton make it easier to thread the needle?	Flatlander	Science & Technology	11	2011-10-12 12:39
Will prime finding become easier?	jasong	Math	5	2007-12-25 05:08
approximation of possible self-avoiding walks	ixfd64	Math	1	2007-11-26 05:57

2017-05-02, 22:59	#2
ATH Einyen Dec 2003 Denmark 2×3×5²×23 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 2×5×7×13 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⁵ Posts	Perfect! That's exactly what I'm looking for. Thanks, guys!

2017-05-03, 10:22	#7
CRGreathouse Aug 2006 2²×3×499 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 2⁵ 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 13544₈ 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.