mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2011-02-12, 06:01   #1
siegert81
 
Dec 2010

2·37 Posts
Default 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?
siegert81 is offline   Reply With Quote
Old 2011-02-12, 07:10   #2
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

232 Posts
Default

Read "The Math".
ckdo is offline   Reply With Quote
Old 2011-02-12, 08:43   #3
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5·223 Posts
Default

Quote:
Originally Posted by cmd View Post
non it :

non probabilità non di non primalità

<snip crazy crap>

"
<Bob Silverman> Would you happen to be on quaaludes? </Bob Silverman>
NBtarheel_33 is offline   Reply With Quote
Old 2011-02-18, 19:06   #4
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22×5×29 Posts
Default

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
Click image for larger version

Name:	probability of primality.JPG
Views:	131
Size:	64.2 KB
ID:	6245  
mart_r is offline   Reply With Quote
Old 2011-02-18, 20:05   #5
axn
 
axn's Avatar
 
Jun 2003

4,703 Posts
Default

Quote:
Originally Posted by mart_r View Post
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?
axn is online now   Reply With Quote
Old 2011-02-18, 21:47   #6
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22·5·29 Posts
Default

Quote:
Originally Posted by axn View Post
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?
mart_r is offline   Reply With Quote
Old 2011-02-19, 00:45   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172516 Posts
Default

I also have trouble understanding the graph.
CRGreathouse is online now   Reply With Quote
Old 2011-02-19, 08:19   #8
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22×5×29 Posts
Default

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
Click image for larger version

Name:	probability of primality.JPG
Views:	112
Size:	64.4 KB
ID:	6251  

Last fiddled with by mart_r on 2011-02-19 at 08:27
mart_r is offline   Reply With Quote
Old 2011-03-02, 17:24   #9
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22×5×29 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2011-03-03, 13:36   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by mart_r View Post
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 View Post
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 View Post
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 View Post
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.
CRGreathouse is online now   Reply With Quote
Old 2011-03-03, 20:27   #11
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

22×5×29 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 View Post
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
Click image for larger version

Name:	probability of primality+.JPG
Views:	102
Size:	85.2 KB
ID:	6307  

Last fiddled with by mart_r on 2011-03-03 at 20:39
mart_r is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
probability ATH Homework Help 7 2014-10-23 00:50
Probability of factor (TF) nuggetprime Math 2 2011-03-19 22:14
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
P-1 Probability question JuanTutors Factoring 2 2005-01-12 20:41
What is the probability distribution for M42 ? dsouza123 Math 2 2004-06-02 02:16

All times are UTC. The time now is 15:39.

Thu Oct 1 15:39:16 UTC 2020 up 21 days, 12:50, 1 user, load averages: 0.64, 1.19, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.