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

are my daughters’ middle names 41 and 43?

      If we can’t write down the primes in one big table, then perhaps we can try to find some pattern to help us to generate the primes. Is there some clever way to look at the primes you’ve got so far, and know where the next one will be?

      Here are the primes we discovered by using the Sieve of Eratosthenes on the numbers from 1 to 100:

      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,

      59, 61, 67, 71, 73, 79, 83, 89, 97

      The problem with the primes is that it can be really difficult to work out where the next one will be, because there don’t seem to be any patterns in the sequence that will help us to help locate them. In fact, they look more like a set of lottery ticket numbers than the building blocks of mathematics. Like waiting for a bus, you can have a huge gap with no primes and then suddenly several come along in quick succession. This behaviour is very characteristic of random processes, as we shall see in Chapter 3.

      Apart from 2 and 3, the closest that two prime numbers can be is two apart, like 17 and 19 or 41 and 43, since the number between each pair is always even and therefore not prime. These pairs of very close primes are called twin primes. With my obsession for primes, my twin daughters almost ended up with the names 41 and 43. After all, if Chris Martin and Gwyneth Paltrow can call their baby Apple, and Frank Zappa can call his daughters Moon Unit and Diva Thin Muffin Pigeen, why can’t my twins be 41 and 43? My wife was not so keen, so these have had to remain my ‘secret’ middle names for the girls.

      Although primes get rarer and rarer as you move out into the universe of numbers, it’s extraordinary how often another pair of twin primes pops up. For example, after the prime 1,129 you don’t find any primes in the next 21 numbers, then suddenly up pop the twin primes 1,151 and 1,153. And when you pass the prime 102,701 you have to plough through 59 non-primes, and then the pair of primes 102,761 and 102,763 suddenly appear. The largest twin primes discovered by the beginning of 2009 have 58,711 digits. Given that it only takes a number with 80 digits to describe the number of atoms in the observable universe, these numbers are ridiculously large.

      But are there more beyond these two twins? Thanks to Euclid’s proof, we know that we’re going to find infinitely many more primes, but are we going to keep on coming across twin primes? As yet, nobody has come up with a clever proof like Euclid’s to show why there are infinitely many of these twin primes.

      At one stage it seemed that twins might have been the key to unlocking the secret of prime numbers. In The Man Who Mistook His Wife for a Hat, Oliver Sacks describes the case of two real-life autistic savant twins who used the primes as a secret language. The twin brothers would sit in Sacks’s clinic, swapping large numbers between themselves. At first Sacks was mystified by their dialogue, but one night he cracked the secret to their code. Swotting up on some prime numbers of his own, he decided to test his theory. The next day he joined the twins as they sat exchanging six-digit numbers. After a while Sacks took advantage of a pause in the prime number patter to announce a seven-digit prime, taking the twins by surprise. They sat thinking for a while, since this was stretching the limit of the primes they had been exchanging to date, then they smiled simultaneously, as if recognizing a friend.

      During their time with Sacks, they managed to reach primes with nine digits. Of course, no one would find it remarkable if they were simply exchanging odd numbers or perhaps even square numbers, but the striking thing about what they were doing is that the primes are so randomly scattered. One explanation for how they managed it relates to another ability the twins had. Often they would appear on television, and impress audiences by identifying that, for example, 23 October 1901 was a Wednesday. Working out the day of the week from a given date is done by something called modular or clock arithmetic. Maybe the twins discovered that clock arithmetic is also the key to a method that identifies whether a number is prime.

      If you take a number, say 17, and calculate 2¹⁷, then if the remainder when you divide this number by 17 is 2, that is good evidence that the number 17 is prime. This test for primality is often wrongly attributed to the Chinese, and it was the seventeenth-century French mathematician Pierre de Fermat who proved that if the remainder isn’t 2, then that certainly implies that 17 is not prime. In general, if you want to check that p is not a prime, then calculate 2^p and divide the result by p. If the remainder isn’t 2, then p can’t be prime. Some people have speculated that, given the twins’ aptitude for identifying days of the week, which depends on a similar technique of looking at remainders on division by 7, they may well have been using this test to find primes.

      At first, mathematicians thought that if 2^p does have remainder 2 on division by p, then p must be prime. But it turns out that this test does not guarantee primality. 341=31×11 is not prime, yet 2³⁴¹ has remainder 2 on division by 341. This example was not discovered until 1819, and it is possible that the twins might have been aware of a more sophisticated test that would wheedle out 341. Fermat showed that the test can be extended past powers of 2 by proving that if p is prime, then for any number n less than p, n^p always has remainder n when divided by the prime p. So if you find any number n for which this fails, you can throw out p as a prime impostor.

      For example, 3³⁴¹ doesn’t have remainder 3 on division by 341—it has remainder 168. The twins couldn’t possibly have been checking through all numbers less than their candidate prime: there would be too many tests for them to run through. However, the great Hungarian prime number wizard Paul Erdos estimated (though he couldn’t prove it rigorously) that to test whether a number less than 10¹⁵⁰ is prime, passing Fermat’s test just once means that the chances of the number being not prime are as low as 1 in 10⁴³. So for the twins, probably one test was enough to give them the buzz of prime discovery.

      Prime number hopscotch

      This is a game for two players in which knowing your twin primes can give you an edge.

      Write down the numbers from 1 to 100, or download the prime numbers hopscotch board from The Number Mysteries website. The first player takes a counter and places it on a prime number, which is at most five steps away from square 1. The second player takes the counter and moves it to a bigger prime that is at most five squares ahead of where the first player placed it. The first player follows suit, moving the counter to an even higher prime number which again is at most five squares ahead. The loser is the first player unable to move the counter according to the rules. The rules are: (1) the counter can’t be moved further than five squares ahead, (2) it must always be moved to a prime, and (3) it can’t be moved backwards or left where it is.

      FIGURE 1.21 An example of a prime number hopscotch game where the maximum move is five steps.

      The picture above shows a typical scenario. Player 1 has lost the game because the counter is at 23 and there are no primes in the five numbers ahead of 23 which are prime. Could Player 1 have made a better opening move? If you look carefully, you’ll see that once you’ve passed 5 there really aren’t many choices. Whoever moves the counter to 5 is going to win because they will at a later turn be able to move the stone from 19 to 23, leaving their opponent with no prime to move to. So the opening move is vital.

      But what if we change the game a little? Let’s say that you are allowed to move the counter to a prime which is at most seven steps ahead. Players can now jump a little further. In particular, they can get past 23 because 29 is six steps ahead and within reach. Does your opening move matter this time? Where will the game end? If you play the game you’ll find that this time you have many more choices along the way, especially when there is a pair of twin primes.

      At first sight, with so many choices it looks like your first move is irrelevant. But look again. You lose if you find yourself on 89 because the next prime after 89 is 97, eight steps ahead. If you trace your way back through the primes,