скачать книгу бесплатно
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
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
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
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, you’ll find that being on 67 is crucial because here you get to choose which of the twin primes 71 and 73 you place the counter on. One is a winning choice; the other will lose you the game because every move from that point on is forced on you. Whoever is on 67 can win the game, and it seems that 89 is not so important. So how can you make sure you get there?
If you carry on tracing your way back through the game you’ll find that there’s a crucial decision to be made for anyone on the prime 37. From there, you can reach my daughters’ twin primes, 41 and 43. Move to 41, and you can guarantee winning the game. So now it looks as if the game is decided by whoever can force their opponent to move them to the prime 37. Continuing to wind the game back in this way reveals that there is indeed a winning opening move. Put the counter on 5, and from there you can guarantee that you get all the crucial decisions that ensure you get to move the stone to 89 and win the game because then your opponent can’t move.
What if we continue to make the maximum permitted jump even bigger: can we be always be sure that the game will end? What if we allow each player to move a maximum of 99 steps—can we be sure that the game won’t just go on for ever because you can always jump to another prime within 99 of the last one? After all, we know that there are infinitely many primes, so perhaps at some point you can simply jump from one prime to the next.
It is actually possible to prove that the game does always end. However far you set the maximum jump, there will always be a stretch of numbers greater than the maximum jump containing no primes, and there the game will end. Let’s look at how to find 99 consecutive numbers, none of which is prime. Take the number 100×99×98×97×…×3×2×1. This number is known as 100 factorial, and written as 100! We’re going to use an important fact about this number: if you take any number between 1 and 100, then 100! is divisible by this number.
Look at this sequence of consecutive numbers:
100!+2, 100!+3, 100!+4, …, 100!+98, 100!+99, 100!+100
100!+2 is not prime because it is divisible by 2. Similarly, 100!+3 is not prime because it is divisible by 3. (100! is divisible by 3, so if we add 3 it’s still divisible by 3.) In fact, none of these numbers is prime. Take 100!+53, which is not prime because 100! is divisible by 53, and if we add 53 the result is still divisible by 53. Here are 99 consecutive numbers, none of which is prime. The reason we started at 100!+2 and not 100!+1 is that with this simple method we can deduce only that 100!+1 is divisible by 1, and that won’t help us to tell whether it’s prime. (In fact it isn’t.)
This website has information about where the hopscotch game will end for larger and larger jumps: http://bit.ly/Primehopscotch You can use your smartphone to scan this code.
So we know for certain that if we set the maximum jump to 99, our prime number hopscotch game will end at some point. But 100! is a ridiculously large number. The game actually finished way before this point: the first place where a prime is followed by 99 non-primes is 396,733.
Playing this game certainly reveals the erratic way in which the primes seem to be scattered through the universe of numbers. At first sight there’s no way of knowing where to find the next prime. But if we can’t find a clever device for navigating from one prime to the next, can we at least come up with some clever formulas to produce primes?
Could rabbits and sunflowers be used to find primes?
Count the number of petals on a sunflower. Often there are 89, a prime number. The number of pairs of rabbits after 11 generations is also 89. Have rabbits and flowers discovered some secret formula for finding primes? Not exactly. They like 89 not because it is prime, but because it is one of nature’s other favourite numbers: the Fibonacci numbers. The Italian mathematician Fibonacci of Pisa discovered this important sequence of numbers in 1202 when he was trying to understand the way rabbits multiply (in the biological rather than the mathematical sense).
Fibonacci started by imagining a pair of baby rabbits, one male, one female. Call this starting point month 1. By month 2, these rabbits have matured into an adult pair, which can breed and produce in month 3 a new pair of baby rabbits. (For the purposes of this thought experiment, all litters consist of one male and one female.) In month 4 the first adult pair produce another pair of baby rabbits. Their first pair of baby rabbits has now reached adulthood, so there are now two pairs of adult rabbits and a pair of baby rabbits. In month 5 the two pairs of adult rabbits each produce a pair of baby rabbits. The baby rabbits from month 4 become adults. So by month 5 there are three pairs of adult rabbits and two pairs of baby rabbits, making five pairs of rabbits in total. The number of pairs of rabbits in successive months is given by the following sequence:
FIGURE 1.22 The Fibonacci numbers are the key to calculating the population growth of rabbits.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Keeping track of all these multiplying rabbits was quite a headache until Fibonacci spotted an easy way to work out the numbers. To get the next number in the sequence, you just add the two previous numbers. The bigger of the two is of course the number of pairs of rabbits up to that point. They all survive to the next month, and the smaller of the two is the number of adult pairs. These adult pairs each produce an extra pair of baby rabbits, so the number of rabbits in the next month is the sum of the numbers in the two previous generations.
Some readers might recognize this sequence from Dan Brown’s novel The Da Vinci Code. They are in fact the first code that the hero has to crack on his way to the Holy Grail.
It isn’t only rabbits and Dan Brown who like these numbers. The number of petals on a flower is often a Fibonacci number. Trillium has three, a pansy has five, a delphinium has eight, marigolds have 13, chicory has 21, pyrethrum 34, and sunflowers often have 55 or even 89 petals. Some plants have flowers with twice a Fibonacci number of petals. These are plants, like some lilies, that are made up of two copies of a flower. And if your flower doesn’t have a Fibonacci number of petals, then that’s because a petal has fallen off … which is how mathematicians get round exceptions. (I don’t want to be inundated with letters from irate gardeners, so I’ll concede that there are a few exceptions which aren’t just examples of wilting flowers. For example, the starflower often has seven petals. Biology is never as perfect as mathematics.)
As well as in flowers, you can find the Fibonacci numbers running up and down pine cones and pineapples. Slice across a banana and you’ll find that it’s divided into 3 segments. Cut open an apple with a slice halfway between the stalk and the base, and you’ll see a 5-pointed star. Try the same with a Sharon fruit, and you’ll get an 8-pointed star. Whether it’s populations of rabbits or the structures of sunflowers or fruit, the Fibonacci numbers seem to crop up whenever there is growth happening.
The way shells evolve is also closely connected to these numbers. A baby snail starts off with a tiny shell, effectively a little one-by-one square house. As it outgrows its shell it adds another room to the house and repeats the process as it continues to grow. Since it doesn’t have much to go on, it simply adds a room whose dimensions are based on those of the two previous rooms, just as Fibonacci numbers are the sum of the previous two numbers. The result of this growth is a simple but beautiful spiral.
Actually these numbers shouldn’t be named after Fibonacci at all, because he was not the first to stumble across them. In fact they weren’t discovered by mathematicians at all, but by poets and musicians in medieval India. Indian poets and musicians were keen to explore all the possible rhythmic structures you can generate by using combinations of short and long rhythmic units. If a long sound is twice the length of a short sound, then how many different patterns are there with a set number of beats? For example, with eight beats you could do four long sounds or eight short ones. But there are lots of combinations between these two extremes.
FIGURE 1.23 How to build a shell using Fibonacci numbers.
In 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 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+…+2
–2+2
–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+…+2
–1+2
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+…+2
+2
)–(1+2+4+8+…+2
+2
)
=(2+4+8+16+…+2
–1–)+2
–(2+4+8+…+2
+2
)
=2
–1
So the total number of grains of rice on the Nth square of the chess board is 2
–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?
