The developers of the program used by GIMPS agreed that the prize money shouldn’t simply go to the lucky person who was assigned that Mersenne number to check. $5,000 went to the developers of the software, $20,000 was shared among those who had broken records with the software since 1999, $25,000 was given to charity and the rest went to Edson Smith in California.
If you still want to win money by looking for primes, don’t worry about the fact that the 10,000,000-digit mark has been passed. For each new Mersenne prime found there is a prize of $3,000. But if it’s the big money you’re after, there is $150,000 on offer for passing 100 million digits and $200,000 if you can make it to the billion-digit mark. Thanks to the Ancient Greeks, we know that such record primes are waiting out there for someone to discover them. It’s just a matter of how much inflation will have eaten into the worth of these prizes before someone eventually claims the next one.
How to write a number with 12,978,189 digits
Edson Smith’s prime is phenomenally large. It would take over 3,000 pages of this book to record its digits, but luckily a bit of mathematics can produce a formula that expresses the number in a much more succinct manner.
The total number of grains of rice up to the Nth square of the chessboard is
R=1+2+4+8+…+2N–2+2N–1
Here’s a trick to find a formula for this number. It looks totally useless at first sight because it is so obvious: R=2R–R. How on earth can such an obvious equation help in calculating R? In mathematics it often helps to take a slightly different perspective, because then everything can suddenly look completely different.
Let’s first calculate 2R. That just means doubling all the terms in the big sum. But the point is that if you double the number of grains of rice on one square, the result is the same as the number grains on the next square along. So
2R=2+4+8+16+…+2N–1+2N
The next move is to subtract R. This will just knock out all the terms of 2R except the last one:
R=2R–R=(2+4+8+16+…+2N–1+2N)–(1+2+4+8+…+2N…2 +2N–1)
=(2+4+8+16+…+2N–1–)+2N–1–(2+4+8+…+2N–2+2N–1)
=2N–1
So the total number of grains of rice on the Nth square of the chess board is 2N–1, and this is the formula responsible for today’s record-breaking primes. By doubling enough times then taking 1 away from the answer you might just hope to hit a Mersenne prime, as primes found using this formula are called. To get Edson Smith’s 12,978,189-digit prime set N=43,112,609 in this formula.
How to cross the universe with a dragon noodle
Rice is not the only food associated with exploiting the power of doubling to create large numbers. Dragon noodles, or la mian noodles, are traditionally made by stretching the dough between your arms and then folding it back again to double the length. Each time you stretch the dough, the noodle becomes longer and thinner, but you need to work quickly because the dough dries out quickly, disintegrating into a noodly mess.
Cooks across Asia have competed for the accolade of doubling the noodle length the most times, and in 2001 the Taiwanese cook Chang Hun-yu managed to double his dough 14 times in two minutes. The noodle he ended up with was so thin that it could be passed through the eye of a needle. Such is the power of doubling that the noodle would have stretched from Mr Chang’s restaurant in the centre of the Taipei to the outskirts of the city, and when it was cut there were a total of 16,384 noodles.
This is the power of doubling, and it can very quickly lead to very big numbers. For example, if it were possible for Chang Hunyu to have carried on and doubled his noodle 46 times, the noodle would be the thickness of an atom and would be long enough to reach from Taipei to the outer reaches of our solar system. Doubling the noodle 90 times would get you from one side of the observable universe to the other. To get a sense of how big the current record prime number is, you would need to double the noodle 43,112,609 times and then take one noodle away to get the record prime discovered in 2008.
What are the odds that your telephone number is prime?
One of the geeky things that mathematicians always do is to check their telephone number to see whether it is prime. I moved house recently and needed to change my telephone number. I hadn’t had a prime telephone number at my previous house (house number 53, a prime) so I was hoping that at my new house (number 1, an ex-prime) I might be luckier.
The first number the phone company gave me looked promising, but when I put it into my computer and tested it I found that it was divisible by 7. ‘I’m not sure I’m going to remember that number … any chance of another number?’ The next number was also not prime—it was divisible by 3. (An easy test to see whether your number is divisible by 3: add up all the digits of your telephone number, and if the number you get is divisible by 3 then so is the original number.) After about three more attempts, the exasperated telephone company employee snapped: ‘Sir, I’m afraid I’m just going to give you the next number that comes up.’ Alas, I now have an even telephone number, of all things!
So what were the chances of me getting a prime telephone number? My number has eight digits. There is approximately a 1 in 17 chance that an eight-digit number is prime, but how does that probability change as the number of digits increases? For example, there are 25 primes under 100, which means that a number with two or fewer digits has a 1 in 4 chance of being prime. On average, as you count from 1 to 100 you get a prime every four numbers. But primes get rarer the higher you count.
The table below shows the changes in probability:
Primes get rarer and rarer, but they get rarer in a very regular way. Every time I add a digit, the probability decreases by about the same amount, 2.3, each time. The first person to notice this was a fifteen-year-old boy. His name was Carl Friedrich Gauss (1777–1855), and he would go on to become one of the greatest names in mathematics.
TABLE 1.2
Gauss made his discovery after being given a book of mathematical tables for his birthday which contained in the back a table of prime numbers. He was so obsessed with these numbers that he spent the rest of his life adding more and more figures to the tables in his spare time. Gauss was an experimental mathematician who liked to play around with data, and he believed that the way the primes thinned out would carry on in this uniform way however far you counted through the universe of numbers.
But how can you be sure that something strange won’t suddenly happen when you hit 100-digit numbers, or 1,000,000-digit numbers? Would the probability still be the same as adding on 2.3 for each new digit, or could the probabilities suddenly start behaving totally differently? Gauss believed that the pattern would always be there, but it took until 1896 for him to be vindicated. Two mathematicians, Jacques Hadamard and Charles de la Vallée Poussin, independently proved what is now called the prime number theorem: that the primes will always thin out in this uniform way.
Gauss’s discovery has led to a very powerful model which helps to predict a lot about the behaviour of prime numbers. It’s as if, to choose the primes, nature used a set of prime number dice with all sides blank except for one with a PRIME written on it:
FIGURE 1.25 Nature’s prime number dice.
To decide whether each number is going to