Alex's Adventures in Numberland - Alex Bellos [112]
Amazingly, however, Mersenne had been right about 127. Lucas used his method to prove that 2127 – 1, or 170,141,183,460,469,231, 731,687,303,715,884,105,727, was prime. This was the highest-known prime number until the computer age. Lucas, however, was unable to determine if 2257 – 1 was prime or not; the number was simply too large to work on with pencil and paper.
Despite its patches of error, Mersenne’s list immortalized him; and now a prime that can be written in the form 2n – 1 is known as a Mersenne prime.
The proof of whether 2257 – 1 is prime would take until 1952 to be proven, using the Lucas method, but with a big assist. A team of scientists gathered one day that year at the Institute for Numerical Analysis in Los Angeles to watch a 24ft scroll of tape be inserted into an early digital computer called the SWAC. Simply putting in the tape took several minutes. The operator then input the number to be tested: 257. In a fraction of a second came the result. Computer said no: 2257 – 1 is not prime.
On the same evening in 1952 on which it was discovered that 2257 – 1 is not prime, new potential Mersenne numbers were inserted into the machine. The SWAC rejected the first 42 as not prime. Then, at 10 p.m., came a result. Computer said yes! It announced that 2521 – 1 is prime. The number was the highest Mersenne prime identified in 75 years, making the corresponding perfect number, 2520 (2521 – 1), only the thirteenth discovered in almost twice as many centuries. But the number 2521 – 1 had only two hours to enjoy its status as top of the pile. Shortly before midnight the SWAC confirmed that 2607 – 1 was also prime. Over the next few months, SWAC worked to the limit of its capacities, finding three more primes. Between 1957 and 1996 another 17 Mersenne primes were discovered.
Since 1952, the largest-known prime number has always been a Mersenne prime (apart from a three-year interlude between 1989 and 1992 when the largest prime was (391581×2216193p>) – 1, which is a related type of prime). Among all the primes that exist, and we know there is an infinite number of them, Mersenne primes dominate the table of highest discovered primes because they give prime-hunters a target to aim for. The best technique for finding high primes is to look for Mersenne primes, in other words, to put the number 2n – 1 into a computer for higher and higher values of n and use the Lucas-Lehmer test, an improved version of Edouard Lucas’s method mentioned earlier, to see if it is prime.
Mersenne primes also have an aesthetic loveliness. For example, in binary notation any number 2n is written as 1 followed by n zeros. For example, 22 = 4, which in binary notation is written 100, and 25 = 32, which is written 100000. Since all Mersenne primes are 1 less than 2n, all binary expansions of Mersenne primes are strings of digits that contain only 1s.
The most influential prime-hunter of modern times was inspired in his mission by the markings on an envelope. When George Woltman was a boy, in the 1960s, his father showed him a postmark with the expression 211213 – 1, then the most recently calculated prime number. ‘I was amazed that a number so large could be proven prime,’ he remembered.
Woltman was later responsible for writing some software that has made an enormous contribution to the quest for primes. All projects that involved massive number-crunching used to be carried out on ‘supercomputers’, access to which was limited. Since the 1990s, however, many big tasks have been salami-sliced by dividing up the work among thousands of smaller machines connected to each other by the internet. In 1996 Woltman wrote a piece of software that users can download for free and that, once installed, allocates a small part of the uninvestigated number line where your machine can look for primes. The software uses the processor only when your computer is otherwise idle. While you are fast asleep, your machine is busy churning through numbers on the frontier