What will be the next number in this sequence?
“At school I was never really good at maths” is an all too common reaction when mathematicians name their profession.
In view of most people’s perceived lack of mathematical talent, it may come as somewhat of a surprise that a recent study carried out at John Hopkins University has shown that six-month-old babies already have a clear sense of numbers. They can count, or at least approximate, the number of happy faces shown on a computer screen.
By the time they start school, at around the age of five, most children are true masters of counting, and many will proudly announce when for the first time they have counted up to 100 or 1000. Children also intuitively understand the regular nature of counting; by adding sufficiently many ones to a starting value of one they know they will eventually reach their own age, that of their parents, grandparents, 2011, and so on.
Counting is child’s play. Photography By Shaeree
From counting to more general addition of whole numbers is only a small step—again within children’s almost-immediate grasp. After all, counting is the art of adding one, and once that is mastered it takes relatively little effort to work out that 3 + 4 = 7. Indeed, the first few times children attempt addition they usually receive help from their fingers or toes, effectively reducing the problem to that of counting:
3 + 4 = (1 + 1 + 1) + (1 + 1 + 1 + 1) = 7.
For most children, the sense of joy and achievement quickly ends when multiplication enters the picture. In theory it too can be understood through counting: 3 x 6 is three lots of six apples, which can be counted on fingers and toes to give 18 apples.
In practice, however, we master it through long hours spent rote-learning multiplication tables—perhaps not among our favourite primary school memories.
But at this point, we ask the reader to consider the possibility—in fact, the certainty—that multiplication is far from boring and uninspiring, but that it is intrinsically linked with some of mathematics’ deepest, most enduring and beautiful mysteries. And while a great many people may claim to be “not very good at maths” they are, in fact, equipped to understand some very difficult mathematical questions.
Primes
Let’s move towards these questions by going back to addition and those dreaded multiplication tables. Just like the earlier example of 7, we know that every whole number can be constructed by adding together sufficiently many ones. Multiplication, on the other hand, is not so well-behaved.
The number 12, for example, can be broken up into smaller pieces, or factors, while the number 11 cannot. More precisely, 12 can be written as the product of two whole numbers in multiple ways: 1 x 12, 2 x 6 and 3 x 4, but 11 can only ever be written as the product 1 x 11. Numbers such as 12 are called composite, while those that refuse to be factored are known as prime numbers or simply primes. For reasons that will soon become clear, 1 is not considered a prime, so that the first five prime numbers are 2, 3, 5, 7 and 11.
Just as the number 1 is the atomic unit of whole-number addition, prime numbers are the atoms of multiplication. According to the Fundamental Theorem of Arithmetic, any whole number greater than 1 can be written as a product of primes in exactly one way. For example: 4 = 2 x 2, 12 = 2 x 2 x 3, 2011 = 2011 and
13079109366950 = 2 x 5 x 5 x 11 x 11 x 11 x 37 x 223 x 23819,
where we always write the factors from smallest to largest. If, rather foolishly, we were to add 1 to the list of prime numbers, this would cause the downfall of the Fundamental Theorem of Arithmetic:
4 = 2 x 2 = 1 x 2 x 2 = 1 x 1 x 2 x 2 = …
In the above examples we have already seen several prime numbers, and a natural question is to ask for the total number of primes. From what we have learnt about addition with its single atom of 1, it is not unreasonable to expect there are only finitely many prime numbers, so that, just maybe, the 2649th prime number, 23819, could be the largest. Euclid of Alexandria, who lived around 300BC and who also gave us Euclidean Geometry, in fact showed that there are infinitely many primes.
Euclid’s reasoning can be captured in just a single sentence: if the list of primes were finite, then by multiplying them together and adding 1 we would get a new number which is not divisible by any prime on our list—a contradiction.
A few years after Euclid, his compatriot Eratosthenes of Cyrene found a clever way, now known as the Sieve of Eratosthenes, to obtain all primes less than a given number.
For instance, to find all primes less than 100, Eratosthenes would write down a list of all numbers from 2 to 99, cross out all multiples of 2 (but not 2 itself), then all multiples of 3 (but not 3 itself), then all multiples of 5, and so on. After only four steps(!) this would reveal to him the 25 primes
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
While this might seem very quick, much more sophisticated methods, combined with very powerful computers, are needed to find really large prime numbers. The current world record, established 2008, is the truly monstrous 243112609 – 1, a prime number of approximately 13 million digits.
The quest to tame the primes did not end with the ancient Greeks, and many great mathematicians, such as Pierre de Fermat, Leonhard Euler and Carl Friedrich Gauss studied prime numbers extensively. Despite their best efforts, and those of many mathematicians up to the present day, there are many more questions than answers concerning the primes.
One famous example of an unsolved problem is Goldbach’s Conjecture. In 1742, Christian Goldbach remarked in a letter to Euler that it appeared that every even number greater than 2 could be written as the sum of two primes.
For example, 2012 = 991 + 1021. While computers have confirmed the conjecture holds well beyond the first quintillion (1018) numbers, there is little hope of a proof of Goldbach’s Conjecture in the foreseeable future.
Another intractable problem is that of breaking very large numbers into their prime factors. If a number is known to be the product of two primes, each about 200 digits long, current supercomputers would take more than the lifetime of the universe to actually find these two prime factors. This time round our inability to do better is in fact a blessing: most secure encryption methods rely heavily on our failure to carry out prime factorisation quickly. The moment someone discovers a fast algorithm to factor large numbers, the world’s financial system will collapse, making the GFC look like child’s play.
To the dismay of many security agencies, mathematicians have also failed to show that fast algorithms are impossible—the possibility of an imminent collapse of world order cannot be entirely ruled out!
Margins of error
For mathematicians, the main prime number challenge is to understand their distribution. Quoting Don Zagier, nobody can predict where the next prime will sprout; they grow like weeds among the whole numbers, seemingly obeying no other law than that of chance. At the same time the prime numbers exhibit stunning regularity: there are laws governing their behaviour, obeyed with almost military precision.
The Prime Number Theorem describes the average distribution of the primes; it was first conjectured by both Gauss and Adrien-Marie Legendre, and then rigorously established independently by Jacques Hadamard and Charles Jean de la Vallée Poussin, a hundred years later in 1896.
The Prime Number Theorem states that the number of primes less than an arbitrarily chosen number n is approximately n divided by ln(n), where ln(n) is the natural logarithm of n. The relative error in this approximation becomes arbitrarily small as n becomes larger and larger.
For example, there are 25 primes less than 100, and 100/ln(100) = 21.7…, which is around 13% short. When n is a million we are up to 78498 primes and since 106/ln(106) = 72382.4…, we are only only 8% short.
The Riemann Hypothesis
The Prime Number Theorem does an incredible job describing the distribution of primes, but mathematicians would love to have a better understanding of the relative errors. This leads us to arguably the most famous open problem in mathematics: the Riemann Hypothesis.
Posed by Bernhard Riemann in 1859 in his paper “Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse” (On the number of primes less than a given magnitude), the Riemann Hypothesis tells us how to tighten the Prime Number Theorem, giving us a control of the errors, like the 13% or 8% computed above.
The Riemann Hypothesis does not just “do better” than the Prime Number Theorem—it is generally believed to be “as good as it gets”. That is, we, or far-superior extraterrestrial civilisations, will never be able to predict the distribution of the primes any better than the Riemann Hypothesis does. One can compare it to, say, the ultimate 100 metres world record—a record that, once set, is impossible to ever break.
Finding a proof of the Riemann Hypothesis, and thus becoming record holder for all eternity, is the holy grail of pure mathematics. While the motivation for the Riemann Hypothesis is to understand the behaviour of the primes, the atoms of multiplication, its actual formulation requires higher-level mathematics and is beyond the scope of this article.
In 1900, David Hilbert, the most influential mathematician of his time, posed a now famous list of 23 problems that he hoped would shape the future of mathematics in the 20th century. Very few of Hilbert’s problems other than the Riemann Hypothesis remain open.
Inspired by Hilbert, in 2000 the Clay Mathematics Institute announced a list of seven of the most important open problems in mathematics. For the successful solver of any one of these there awaits not only lasting fame, but also one million US dollars in prize money. Needless to say, the Riemann Hypothesis is one of the “Millennium Prize Problems”.
Hilbert himself remarked: “If I were awoken after having slept for a thousand years, my first question would be: has the Riemann Hypothesis been proven?” Judging by the current rate of progress, Hilbert may well have to sleep a little while longer.
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Ole Warnaar*