 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

3×7×53 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... 10010101112 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

5×23×41 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...

599 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 22·1,483 Posts I also have trouble understanding the graph.   2011-02-19, 08:19 #8 mart_r   Dec 2008 you know...around... 599 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... 10010101112 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 ~ ) 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

22×1,483 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

Quote:
 Originally Posted by mart_r And specifically, from what I can tell, qinf ~
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 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...

599 Posts Quote:
 Originally Posted by CRGreathouse I trust this is to be interpreted as as and
Right, the error term behaves much like .
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 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   Thread Tools Show Printable Version Email this Page 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 18:37.

Tue Oct 27 18:37:38 UTC 2020 up 47 days, 15:48, 1 user, load averages: 1.43, 1.83, 1.90