The Number Mysteries: A Mathematical Odyssey through Everyday Life. Marcus Sautoy du

the eighth century AD the Indian writer Virahanka took up the challenge to determine exactly how many different rhythms are possible. He discovered that as the number of beats goes up, the number of possible rhythmic patterns is given by the following sequence: 1, 2, 3, 5, 8, 13, 21, … He realized, just as Fibonacci did, that to get the next number in the sequence you simply add together the two previous numbers. So if you want to know how many possible rhythms there are with eight beats you go to the eighth number in the sequence, which is got by adding 13 and 21 to arrive at 34 different rhythmic patterns.

      Perhaps it’s easier to understand the mathematics behind these rhythms than to try to follow the increasing population of Fibonacci’s rabbits. For example, to get the number of rhythms with eight beats you take the rhythms with six beats and add a long sound or take the rhythms with seven beats and add a short sound.

      There is an intriguing connection between the Fibonacci sequence and the protagonists of this chapter, the primes. Look at the first few Fibonacci numbers:

      1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

      Every pth Fibonacci number, where p is a prime number, is itself prime. For example, 11 is prime, and the 11th Fibonacci number is 89, a prime. If this always worked it would be a great way to generate bigger and bigger primes. Unfortunately it doesn’t. The 19th Fibonacci number is 4,181, and although 19 is prime, 4,181 is not: it equals 37×113. No mathematician has yet proved whether infinitely many Fibonacci numbers are prime numbers. This is another of the many unsolved prime number mysteries in mathematics.

      How can you use rice and a chessboard to find primes?

      Legend has it that chess was invented in India by a mathematician. The King was so grateful to the mathematician that he asked him to name any prize as a reward. The inventor thought for a minute, then asked for 1 grain of rice to be placed on the first square of the chessboard, 2 on the second, 4 on the third, 8 on the fourth, and so on, so that each square got twice as many grains of rice as were on the previous square.

      The King readily agreed, astonished that the mathematician wanted so little—but he was in for a shock. When he began to place the rice on the board, the first few grains could hardly be seen. But by the time he’d got to the 16th square, he was already needing another kilogram of rice. By the 20th square, his servants had to bring in a wheelbarrow full. He never reached the 64th and last square on the board. By that point the total number of grains of rice on the board would have been a staggering

      18,446,744,073,709,551,615

      If we tried to repeat the feat at the heart of London, the pile of rice on the 64th square would stretch to the boundaries of the M25 and would be so high that it would cover all the buildings. In fact, there would be more rice in this pile than has been produced across the globe in the last millennium.

      FIGURE 1.24 Repeated doubling makes numbers grow very quickly.

      Not surprisingly, the King of India failed to give the mathematician the prize he had been promised and was forced into parting with half his fortune instead. That’s one way maths can make you rich.

      But what has all this rice got to do with finding big prime numbers? Ever since the Greeks had proved that the primes go on for ever, mathematicians had been on the look-out for clever formulas that might generate bigger and bigger primes. One of the best of these formulas was discovered by a French monk called Marin Mersenne. Mersenne was a close friend of Pierre de Fermat and René Descartes, and he functioned like a seventeenth-century Internet hub, receiving letters from scientists all across Europe and communicating ideas to those he thought could develop them further.

      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