| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
GIMPS chances of finding a prime number
Odds are slippery things, not because they are hard to calculate but because people seem to rely on their intuition to tell them what the odds mean. Odds are used to calculate the probability of something happening based on the number of possible outcomes, not on what the last three or three hundred outcomes were.
Suppose we were talking about rolling dice. Each dice has six faces, which means that there are six different results from rolling one dice. The odds of any one particular result are therefore 1:6. This means that every single time you roll the dice there is a 1:6 chance of you throwing a six. It doesn't matter if you haven't thrown a six in the last fifty throws, the chances of you throwing a six on your next throw are 1:6. What has happened in the past does not affect the number of faces on the dice, which is all that is used to calculate the odds.
How does this apply to finding prime numbers?
One thing we know about prime numbers is that they thin out as they get bigger. Four of the first ten numbers are prime, but there isn't a single prime between 31,397 and 31,469, a gap of seventy-one numbers. But this thinning out does not happen evenly like a river broadening as it slows down, and there are twin primes - primes that are only 2 apart like 612,107 and 612,109 - and this makes matters more complicated.
In 1845, the French mathematician Joseph Bertrand (1822 - 1900) conjectured that there is always a prime between n and 2n, and five years later the Russian Pafnuty Chebyshev (1821 - 1894) proved it was true. This means that if you pick a number and double it, there is always at least one prime in the gap between your two numbers. But that refers to all primes, whereas GIMPS is only looking for Mersenne primes, and Chebyshev's result says nothing about where these might be. Which means that we can't just pick a big block of numbers and know with any degree of certainty that there is a Mersenne prime in there somewhere waiting to be found.
Lastly, switching the analogy from dice to coins, when you flip a coin it can only come down heads or tails; there are only two possible outcomes, so the chance of it being heads is 1:2. From the fact that a number either is prime or it is not one might suppose that in this instance there really are only two possible outcomes. But that is only true if the coin is evenly weighted, if it is what is called a 'fair' coin. From what we know about the distribution of the primes, and from the fact that each exponent is trial factored before being sent to a client, this coin is in effect not fair.
From the fact that the primes thin out, we know that the higher your number the lower its chance of being prime. From trial factoring we know that there are no small factors of your number and the more factoring that has been done the greater the chance that your number will be prime. We then throw in a constant that has proved over a large number of trials to have given accurate results. From this, we estimate that for a first time Lucas-Lehmer test of 2^p-1 that has been unsuccessfully trial factored to 2^b and P-1 factored to the default limits for exponent p, that it has 1 chance in ( p / ( (b-1) x 1.803 )) of being prime.
| General |
| Definitions |
| Work with GIMPS |
| Related |
| FAQ |
