mersenneforum.org Probability of primality
 Register FAQ Search Today's Posts Mark Forums Read

 2011-02-12, 06:01 #1 siegert81   Dec 2010 2×37 Posts Probability of primality I notice that when I get a new number to test from GIMPS, the program will say that it has a 1 in 450,000 chance of being prime (not the actual probability). How is this probability determined? How can one calculate probabilities for other types of numbers (Proth, generalized Fermat, factorial, etc.)? How does trial division up to N affect the probability of a number's primality?
 2011-02-12, 07:10 #2 ckdo     Dec 2007 Cleves, Germany 2·5·53 Posts Read "The Math".
2011-02-12, 08:43   #3
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

21338 Posts

Quote:
 Originally Posted by cmd non it : non probabilità non di non primalità "
<Bob Silverman> Would you happen to be on quaaludes? </Bob Silverman>

 2011-02-18, 19:06 #4 mart_r     Dec 2008 you know...around... 5·157 Posts Although I'm able to write at the same level of creativity as cmd does, it gets slightly irritating by now. But that's beside the point, because I, too, have a question about the probability of primality: Look at the graph attached: it seems fairly less likely for a number n to be prime compared to the approximation via Mertens' theorem, if it's trial divided up to about n^¼. I've also checked this for numbers in the regions 106 and a few others. The graphs always looked about the same: at some number x the purple line dropped below the blue line, reached a certain minimum, then turned around and headed toward 2. Sure, I did expect it to look about that way, but what confuses me is that minimum value at around sqrt(sqrt(n)). Is there anything known about this? (The difference is small, sure, but when I look for simultaneous primes, the difference between, for example, 3.95^14 and 4^14 becomes more significant...) Attached Thumbnails
2011-02-18, 20:05   #5
axn

Jun 2003

22×3×449 Posts

Quote:
 Originally Posted by mart_r I, too, have a question about the probability of primality: Look at the graph attached: it seems fairly less likely for a number n to be prime compared to the approximation via Mertens' theorem, if it's trial divided up to about n^¼. I've also checked this for numbers in the regions 106 and a few others. The graphs always looked about the same: at some number x the purple line dropped below the blue line, reached a certain minimum, then turned around and headed toward 2. Sure, I did expect it to look about that way, but what confuses me is that minimum value at around sqrt(sqrt(n)). Is there anything known about this?
How was this graph generated? What are the axes? What is q1 & q2? The graph shapes are not consistent with the equations written there?

2011-02-18, 21:47   #6
mart_r

Dec 2008
you know...around...

5×157 Posts

Quote:
 Originally Posted by axn How was this graph generated? What are the axes? What is q1 & q2? The graph shapes are not consistent with the equations written there?
I used one million values for n between 99,500,000 and 100,499,999 for the graph. The values of q1 and q2 are those on the y-axis for trial division up to p (x-axis).
The graph shapes are not consistent with the equations? Then my program/algorithm would be flawed... what graphs do you get for said values?

 2011-02-19, 00:45 #7 CRGreathouse     Aug 2006 175D16 Posts I also have trouble understanding the graph.
 2011-02-19, 08:19 #8 mart_r     Dec 2008 you know...around... 5×157 Posts Aah shoot, I went for ln instead of log... aaand mixed up the actual value with the reciprocal value, what's wrong with me???? I'll upload a new graph... Anyway, for a better understanding (I hope): trial division up to p=1000 gives a probability of about (1.773*log(1000))/log(n) for n~108 and (1.789*log(1000))/log(n) for lim n-->infinity. Attached Thumbnails   Last fiddled with by mart_r on 2011-02-19 at 08:27
 2011-03-02, 17:24 #9 mart_r     Dec 2008 you know...around... 14218 Posts I found some time to check through another calculation again, and the values do seem to fluctuate. That means: let qn denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(qn*log(p)). According to Mertens' theorem, for n = infinity, qinf converges to e^gamma as p increases. (And specifically, from what I can tell, qinf ~ $e^{gamma}*(1+\frac{1}{sqrt p*log(p)})$) Applying SOE for a given n and juxtaposing the values for n = infinity, the value qn for the fixed n fluctuates around the other, qinf, as p increases, with a local minimum at p ~ n^0.362. Moreover, looking at the difference between the two values of q, there's a local maximum at p ~ n^0.288 which is of a much smaller scale than the local minimum. Again, before that, there is another yet smaller minimum at p ~ n^0.23...0.24. (Mathematically correctly phrased? Unclear constant/letter assignment? Mr Silverman?:) These are only results I obtained for relatively small n. No conjecture, nothing I can prove, just sounding out. Last fiddled with by mart_r on 2011-03-02 at 17:27
2011-03-03, 13:36   #10
CRGreathouse

Aug 2006

5,981 Posts

Quote:
 Originally Posted by mart_r That means: let qn denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(qn*log(p)).
OK, this can be defined sensibly if we think of choosing a random number in so appropriate region of n (say, 0.9n to 1.1n) that is p-smooth. Of course the interval can be taken arbitrarily small if we're willing to look at large enough numbers.

Quote:
 Originally Posted by mart_r According to Mertens' theorem, for n = infinity, qinf converges to e^gamma as p increases.
Right. Or rather the appropriate product converges to that value by Mertens' theorem, and for n sufficiently large (n ≫ p2 + ε, I think) you have
$q_\infty\stackrel{\tiny\Delta}{=}\lim_{p\to\infty}q_p=e^\gamma.$

Quote:
 Originally Posted by mart_r And specifically, from what I can tell, qinf ~ $e^{gamma}*(1+\frac{1}{sqrt p*log(p)})$
I trust this is to be interpreted as

$q_p=e^\gamma\left(1+\frac{1+o(1)}{\sqrt p\log p}\right)$

as $p\to\infty$ and $n\gg p^{2+\varepsilon}.$

Hmm. First of all, the best known bounds on the product itself are much weaker -- more like (1 + O(1/log^2 n)) than (1 + o(n^-.5)). Getting that part under that much control seems hard, probably of RH-like difficulty (though I don't know this!). Once you have a number for the product, though, you may have additional problems getting the numbers to work nicely if p is close to the square root of n, causing Maier-Granville type problems. (Fortunately the examples you have below have p small enough that I don't think this second type of problem will be an issue.)

Quote:
 Originally Posted by mart_r Applying SOE for a given n and juxtaposing the values for n = infinity, the value qn for the fixed n fluctuates around the other, qinf, as p increases, with a local minimum at p ~ n^0.362. Moreover, looking at the difference between the two values of q, there's a local maximum at p ~ n^0.288 which is of a much smaller scale than the local minimum. Again, before that, there is another yet smaller minimum at p ~ n^0.23...0.24.
I'm not sure I understand.

2011-03-03, 20:27   #11
mart_r

Dec 2008
you know...around...

5×157 Posts

Quote:
 Originally Posted by CRGreathouse I trust this is to be interpreted as $q_p=e^\gamma\left(1+\frac{1+o(1)}{\sqrt p\log p}\right)$ as $p\to\infty$ and $n\gg p^{2+\varepsilon}.$
Right, the error term behaves much like $\frac{Li(x)-Pi(x)}{sqrt x/log(x)}-1$.
And I was looking for an acceptable approximation rather than a bound.

Quote:
 Originally Posted by CRGreathouse I'm not sure I understand.
Me, too :)

You see, for a long time I lived on the assumption that a number n, when trial divided up to p, has a chance of $\frac{2*\log p}{\log n}$ being prime. (Some time ago, axn pointed out to me that this is not quite true.) The only thing I do here is to elaborate on the "2" in this fraction.

Again, a nice graphic potpourri in the attachment. By the difference between the graphs you may see what I was referring to when I talked about these local maxima/minima.

And thanks for contributing so much to my "projects", it's highly appreciated.
Attached Thumbnails

Last fiddled with by mart_r on 2011-03-03 at 20:39

 Similar Threads Thread Thread Starter Forum Replies Last Post ATH Homework Help 7 2014-10-23 00:50 nuggetprime Math 2 2011-03-19 22:14 marco_calabresi Information & Answers 3 2009-04-17 19:44 JuanTutors Factoring 2 2005-01-12 20:41 dsouza123 Math 2 2004-06-02 02:16

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

Sat Aug 20 06:07:25 UTC 2022 up 2 days, 3:35, 0 users, load averages: 1.26, 1.15, 1.14