mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-05-02, 21:41   #1
mathPuzzles
 
Mar 2017

2·3·5 Posts
Default 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!
mathPuzzles is offline   Reply With Quote
Old 2017-05-02, 22:59   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

65278 Posts
Default

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
ATH is online now   Reply With Quote
Old 2017-05-02, 23:29   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

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
danaj is offline   Reply With Quote
Old 2017-05-03, 00:36   #4
mathPuzzles
 
Mar 2017

2·3·5 Posts
Default

Perfect! That's exactly what I'm looking for. Thanks, guys!
mathPuzzles is offline   Reply With Quote
Old 2017-05-03, 02:18   #5
mathPuzzles
 
Mar 2017

111102 Posts
Default

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!
mathPuzzles is offline   Reply With Quote
Old 2017-05-03, 02:27   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-05-03, 10:22   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176316 Posts
Default

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.)
CRGreathouse is offline   Reply With Quote
Old 2017-05-03, 17:50   #8
mathPuzzles
 
Mar 2017

111102 Posts
Default

That's a very clear explanation that makes both the derivation and use straightforward. Thanks much!
mathPuzzles is offline   Reply With Quote
Old 2017-05-04, 10:58   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:19.


Fri Dec 2 13:19:11 UTC 2022 up 106 days, 10:47, 0 users, load averages: 0.80, 0.88, 0.85

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔