20110212, 06:01  #1 
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? 
20110212, 08:43  #3 
"Nathan"
Jul 2008
Maryland, USA
5·223 Posts 

20110218, 19:06  #4 
Dec 2008
you know...around...
2^{2}×5×29 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 10^{6} 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...) 
20110218, 20:05  #5  
Jun 2003
4,703 Posts 
Quote:


20110218, 21:47  #6  
Dec 2008
you know...around...
2^{2}·5·29 Posts 
Quote:
The graph shapes are not consistent with the equations? Then my program/algorithm would be flawed... what graphs do you get for said values? 

20110219, 00:45  #7 
Aug 2006
1725_{16} Posts 
I also have trouble understanding the graph.

20110219, 08:19  #8 
Dec 2008
you know...around...
2^{2}×5×29 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~10^{8} and (1.789*log(1000))/log(n) for lim n>infinity. Last fiddled with by mart_r on 20110219 at 08:27 
20110302, 17:24  #9 
Dec 2008
you know...around...
2^{2}×5×29 Posts 
I found some time to check through another calculation again, and the values do seem to fluctuate.
That means: let q_{n} denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(q_{n}*log(p)). According to Mertens' theorem, for n = infinity, q_{inf} converges to e^gamma as p increases. (And specifically, from what I can tell, q_{inf} ~ ) Applying SOE for a given n and juxtaposing the values for n = infinity, the value q_{n} for the fixed n fluctuates around the other, q_{inf}, 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 20110302 at 17:27 
20110303, 13:36  #10  
Aug 2006
3·5^{2}·79 Posts 
Quote:
Quote:
I trust this is to be interpreted as as and 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 RHlike 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 MaierGranville 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:


20110303, 20:27  #11 
Dec 2008
you know...around...
2^{2}×5×29 Posts 
Right, the error term behaves much like .
And I was looking for an acceptable approximation rather than a bound. 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 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. Last fiddled with by mart_r on 20110303 at 20:39 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
probability  ATH  Homework Help  7  20141023 00:50 
Probability of factor (TF)  nuggetprime  Math  2  20110319 22:14 
Primality searches and primality successes  marco_calabresi  Information & Answers  3  20090417 19:44 
P1 Probability question  JuanTutors  Factoring  2  20050112 20:41 
What is the probability distribution for M42 ?  dsouza123  Math  2  20040602 02:16 