The Number Mysteries: A Mathematical Odyssey through Everyday Life. Marcus Sautoy du
Чтение книги онлайн.
Читать онлайн книгу The Number Mysteries: A Mathematical Odyssey through Everyday Life - Marcus Sautoy du страница 11
Название: The Number Mysteries: A Mathematical Odyssey through Everyday Life
Автор: Marcus Sautoy du
Издательство: HarperCollins
Жанр: Математика
isbn: 9780007362561
isbn:
His correspondence with Fermat led to the discovery of a powerful formula for finding huge primes. The secret of this formula is hidden inside the story of the rice and the chessboard. As you count up the grains of rice from the first square of the chessboard, the cumulative total quite often turns out to be a prime number. For example, after three squares there are 1+2+4=7 grains of rice, a prime number. By the fifth square there are 1+2+4+8+16=31 grains of rice.
Mersenne wondered whether it would turn out to be true that whenever you landed on a prime number square on the chessboard, the number of grains of rice up to that point might also be a prime. If it was, it would give you a way of generating bigger and bigger primes. Once you’d counted the prime number grains of rice, just move to this square on the chessboard and count the number of grains of rice up to this point, which Mersenne hoped would be an even bigger prime.
Unfortunately for Mersenne and for mathematics, his idea didn’t quite work. When you look on the 11th square of the chessboard, a prime number square, then up to that point there are a total of 2,047 grains of rice. Sadly, 2,047 is not prime—it equals 23×89. But although Mersenne’s idea didn’t always work, it has led to some of the largest prime numbers that have been discovered.
The Guinness Book of Primes
In the reign of Queen Elizabeth I, the largest known prime number was the number of grains of rice on the chessboard up to and including the 19th square: 524,287. By the time that Lord Nelson was fighting the Battle of Trafalgar, the record for the largest prime had gone up to the 31st square of the chessboard: 2,147,483,647. This ten-digit number was proved to be prime in 1772 by the Swiss mathematician Leonhard Euler, and it was the record-holder until 1867.
By 4 September 2006, the record had gone up to the number of grains of rice that would be on the 32,582,657th square, if we had a big enough chessboard. This new prime number has over 9.8 million digits, and it would take a month and a half to read it out loud. It was discovered not by some huge supercomputer but by an amateur mathematician using some software downloaded from the Internet.
The idea of this software is to utilize a computer’s idle time to do computations. The program it uses implements a clever strategy that was developed to test whether Mersenne’s numbers are prime. It still took a desktop computer several months to check Mersenne numbers with 9.8 million digits, but this is a lot faster than methods for testing whether a random number of this size is prime. By 2009, over ten thousand people had joined what has become known as the Great Internet Mersenne Prime Search, or GIMPS.
Be warned, though, that the search is not without its dangers. One GIMPS recruit worked for a telephone company in America and decided to enlist the help of 2,585 of the company’s computers in his search for Mersenne primes. The company began to get suspicious when its computers were taking five minutes rather than five seconds to retrieve telephone numbers.
If you want your computer to join the GIMPS, you can download the software at www.mersenne.org, or scan this code with your smartphone.
When the FBI eventually found the source of the slowdown, the employee owned up: ‘All that computational power was just too tempting for me,’ he admitted. The telephone company didn’t feel sympathetic to the pursuit of science, and fired the employee.
After September 2006, mathematicians were holding their breath to see when the record would pass the 10,000,000-digit barrier. The anticipation was not just for academic reasons—a prize of $100,000 was waiting for the person who got there first. The prize money was put up by the Electronic Frontier Foundation, a California-based organization that encourages collaboration and cooperation in cyberspace.
It was two more years before the record was broken. In a cruel twist of fate, two record-breaking primes were found within a few days of each other. The German amateur prime number sleuth Hans-Michael Elvenich must have thought he’d hit the jackpot when his computer announced on 6 September 2008 that it had just found a new Mersenne prime with 11,185,272 digits. But when he submitted his discovery to the authorities, his excitement turned to despair—he had been beaten to it by 14 days. On 23 August, Edson Smith’s computer in the maths department at UCLA had discovered an even bigger prime, with 12,978,189 digits. For the University of California at Los Angeles, breaking prime number records is nothing new. UCLA mathematician Raphael Robinson discovered five Mersenne primes in the 1950s, and two more were found by Alex Hurwitz at the beginning of the 1960s.
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 СКАЧАТЬ