mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-12-10, 17:19   #1
vimil
 
Nov 2007

310 Posts
Default Probability of a Mersenne number being prime

On clicking the status menu-item 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 Lucas-Lehmer test?
vimil is offline   Reply With Quote
Old 2007-12-10, 18:03   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by vimil View Post
On clicking the status menu-item 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 Lucas-Lehmer test?
No, it shouldn't. The LL (Lucas-Lehmer) test doesn't give any results until it is 100% completed, after which it determines whether the number is prime or composite. It does not find factors.
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/Lucas-LehmerTest.html
Mini-Geek is offline   Reply With Quote
Old 2007-12-10, 18:04   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by vimil View Post
On clicking the status menu-item 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 Lucas-Lehmer test?
I am curious as to why you think it should. The LL test is a
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 pseudo-random
within the finite field GF(P^2) where P = 2^p-1 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.
R.D. Silverman is offline   Reply With Quote
Old 2007-12-11, 02:35   #4
potonono
 
potonono's Avatar
 
Jun 2005
USA, IL

193 Posts
Default

You mean to say the probability isn't 50/50 when it gets to the last iteration? :)


jk
potonono is offline   Reply With Quote
Old 2007-12-11, 08:44   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,879 Posts
Default

Quote:
Originally Posted by potonono View Post
You mean to say the probability isn't 50/50 when it gets to the last iteration? :)
Of course not, it is 50/50 when you get half way through the interations.
retina is offline   Reply With Quote
Old 2007-12-11, 12:19   #6
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

23·3·52 Posts
Default

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
Fusion_power is offline   Reply With Quote
Old 2007-12-11, 14:45   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Fusion_power View Post
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, :

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.
R.D. Silverman is offline   Reply With Quote
Old 2007-12-11, 15:03   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
A Mersenne number is either prime or composite even before one conducts a LL test...

Conducting a primality test simply reveals which.
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 2007-12-11 at 15:06
bsquared is offline   Reply With Quote
Old 2007-12-11, 17:17   #9
vimil
 
Nov 2007

3 Posts
Default 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 2007-12-11 at 17:19
vimil is offline   Reply With Quote
Old 2007-12-11, 18:14   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
An *individual* number does not have a "probability" in the sense
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)
R.D. Silverman is offline   Reply With Quote
Old 2007-12-11, 18:15   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by vimil View Post
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?
A given integer N is either prime or not, but it's possible to *model* a range of integers using a probability distribution, in order to say something about how many primes to expect in that range. One rough estimate is the probability that an integer n is prime is about 1/log n. This figure must be modified if one has already determined that no small primes up to some limit divide the integer (and I presume your test number has been sieved to some bit depth). I don't know the exact implementation details, but I suspect that this is what prime95 is doing. Again, this is simply the output of a probablistic model and says nothing about the true primeness of a particular number.

- ben.

Last fiddled with by bsquared on 2007-12-11 at 18:25 Reason: tpyo
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
probability a number is prime with a weighted k. Trilo Homework Help 12 2014-06-06 19:17
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
probability of finding a Mersenne prime optim Math 2 2003-12-06 19:03
Probability of finding a prime number Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 18:09.

Fri Nov 27 18:09:11 UTC 2020 up 78 days, 15:20, 4 users, load averages: 2.00, 1.74, 1.48

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.