20071210, 17:19  #1 
Nov 2007
3_{10} Posts 
Probability of a Mersenne number being prime
On clicking the status menuitem from the Test menu of Prime95 I am told the probabilty of the mercene number I have chosen to test being prime is 1 in 317069.Even though the percentage of iterations of Lucas Lehmer test increases this probabilty remains the same. Shouldn't this probability increase with the iterations of LucasLehmer test?

20071210, 18:03  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2×3×23×31 Posts 
Quote:
Here's more reading about the LL test: (the top one has info on the other tests Prime95 runs) http://www.mersenne.org/math.htm http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers http://mathworld.wolfram.com/LucasLehmerTest.html 

20071210, 18:04  #3  
"Bob Silverman"
Nov 2003
North of Boston
16510_{8} Posts 
Quote:
computational procedure. It gives a yes/no answer based on a simple modular criterion that says at the *ultimate iteration*, a certain value should be 0. Why do you think this implies that running some number of earlier iterations yields any information about what the final answer will be? [hint: it doesn't; the map x_{n+1} = x_n^2 2 is pseudorandom within the finite field GF(P^2) where P = 2^p1 is the number being tested] I am curious as to your thought processes on this matter. And stating that the probability is 1/317069 is fuzzy at best. In actuality, for any given number, the probability is either 1 or 0. Asserting that it is 1/317069 (1) Assumes some facts that have not yet been proven. (2) Assigns a probability based on the assumption that a number has been drawn, uniformly at random, from a fairly short interval of potential candidates. However, this is the a priori probability for any candidate in the interval. Once you have taken a *sample*, the probability becomes either 0 or 1. (3) Uses more significant digits than any possible theorem can give. It implies more accuracy in the estimate than is mathematically possible. Mathematicians do have some heuristics that tells us what the probability will be for randomly drawn candidates that are SUFFICIENTLY LARGE. Sufficiently large means as the candidates go to infinity. These heuristics can give only a very rough approximate probability for the small numbers we are working with today. 

20071211, 02:35  #4 
Jun 2005
USA, IL
193 Posts 
You mean to say the probability isn't 50/50 when it gets to the last iteration? :)
jk 
20071211, 08:44  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6640_{10} Posts 

20071211, 12:19  #6 
Aug 2003
Snicker, AL
2^{6}×3×5 Posts 
One way to look at this is that a Mersenne number could be either prime or composite right up to completion of the final iteration. From this perspective, it is similar to the Shroedinger's Cat scenario, meaning there is a cat in a box and it could be either alive or dead and in some ways is both. Only when the box is opened do the probabilities converge and one result is seen.
From this viewpoint, saying the probability is 50/50 at any point during the iterations is ludicrous. DarJones 
20071211, 14:45  #7  
"Bob Silverman"
Nov 2003
North of Boston
7496_{10} Posts 
Quote:
Codswallop. A Mersenne number is either prime or composite even before one conducts a LL test. Bringing in QM is nonsense. Indeed, *every* number (except for units) is either prime or composite. Conducting a primality test simply reveals which. We simply don't know the answer until after the test is run. But it is definitely one or the other, unlike QM when it is *neither* until the wave function collapses. 

20071211, 15:03  #8 
"Ben"
Feb 2007
7213_{8} Posts 
It is this fact which I think confuses people when they say there is a probability that a number is prime, because it seems like a flip of the coin as to which is revealed. I know it has confused me. I like to think of the primeness of a number as a signal in a channel which has been muddled by noise. We just can't tell what the signal is until after we apply our perfect dectector to the channel (the LL test), but the signal itself is never in doubt.
Last fiddled with by bsquared on 20071211 at 15:06 
20071211, 17:17  #9 
Nov 2007
3 Posts 
How does Prime95 come up with this probability
Allright, how does Prime95 come up with this probability then? Does it run some other probablistic test on a mercenne number before giving it to the user to test?
Last fiddled with by vimil on 20071211 at 17:19 
20071211, 18:14  #10  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
you discuss. When we assign a probability we mean that if one selects a number *uniformly at random* from some short interval, then it might be prime or it might be composite. The probability is the percentage of numbers in the interval that ARE prime. probability always means with respct to some underlying distribution. For Mersenne primes, the distribution is *believed* to be Poisson, but there is no proof. (nor any hope of proof in the near future) 

20071211, 18:15  #11  
"Ben"
Feb 2007
7213_{8} Posts 
Quote:
 ben. Last fiddled with by bsquared on 20071211 at 18:25 Reason: tpyo 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!  dabaichi  News  571  20201026 11:02 
probability a number is prime with a weighted k.  Trilo  Homework Help  12  20140606 19:17 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
probability of finding a Mersenne prime  optim  Math  2  20031206 19:03 
Probability of finding a prime number  Deamiter  Software  4  20021011 16:36 