Sieving for Numbers

by Nicholas Mee and David Benjamin on October 1, 2017

Alexander’s general Ptolemy I Soter became the first pharaoh of the Ptolemaic dynasty of Egypt following Alexander’s death in 323 BC. Ptolemy founded the famous Library of Alexandria. Dedicated to the muses, the nine goddesses of the arts, it was the original museum. During the Ptolomaic era Alexandria would replace Athens as the leading cultural centre in the Hellenistic world. In 245 BC, Eratosthenes, from the Libyan city of Cyrene, was appointed librarian.

The Library of Alexandria. Credit: Rob Cain’s Ancient Rome Refocused.

Eratosthenes was a literary scholar who studied Homer and the Greek dramatists, but he is now chiefly remembered as a mathematician. He made original contributions to many disciplines and was known as the pentathlete to his admirers, although envious critics dismissed him as a jack-of-all-trades, referring to him disparagingly as beta. According to them he was second best in many fields, but first in none. Eratosthenes famously calculated the distance around the Earth. He is also remembered for an algorithm for finding prime numbers known as Eratosthenes sieve.

A prime number is a positive integer, or whole number, that is not divisible by any other positive integer other than itself and 1. All other integers are composite and are formed of a product of primes. So the primes are the bare bones from which all integers are composed, they are the arithmetical equivalent of the chemical elements. Often composite numbers can be factorised in different ways, for instance 36 = 9 x 4 = 6 x 6, but when resolved into primes, factorisation is always unique. In our example, 36 = 2 x 2 x 3 x 3. This simple fact is so important it is given the grandiose title of the fundamental theorem of arithmetic.

Eratosthenes Sieve. The cells corresponding to all multiples of 2, 3, 5, 7, 11 and 13 have been coloured, leaving the cells occupied by the primes white.

We will show how the sieving method finds all the primes lower than 225. First form a grid of integers from 1 to 225, then examine each integer sequentially. The number 1 is not considered to be a prime, because all numbers are divisible by 1. It is referred to as a unit. The number 2 is prime, as it has no divisors. We cross off (or colour in) all multiples of 2, as they cannot be prime. The number 3 is not crossed off so it is also prime. We now cross off all multiples of 3. The number 4 has been crossed off, because it is a multiple of 2. The number 5 is not crossed off, so it is prime. We cross off all multiples of 5. 6 has been crossed off. The number 7 is prime. We cross off all multiples of 7. The next number that is not crossed off is 11. Continuing in this way, we gradually compile a list of primes: 2, 3, 5, 7, 11, 13, 17, 19 and so on.

How Many Primes Are There?

New primes become less frequent as we move to higher numbers. Of the first ten integers, 4 are primes, that is 40% of the total. Of the first 100 integers, 25 are primes—25% of the total. But in the century between 1001 and 1100, there are only 16 primes—16% of the total—and in the century between 9901 and 10,000, there are just 9 primes—9% of the total. This raises the question of how many primes there are in all. Do they eventually peter out or do they keep on going for ever? It is conceivable that eventually sufficient primes accumulate that all higher numbers are composite, so the answer is not immediately obvious. Nevertheless, the definitive answer has been known for over 2000 years. It is one of the many remarkable results in the Elements of Euclid.

The new Library of Alexandria, which opened in 2002.

Euclid was a Greek mathematician. Although little is known about his life, he was probably a predecessor of Eratosthenes in Alexandria somewhere around 300 BC in the time of Ptolemy I. Euclid’s Elements is the most important work in the history of mathematics. Its succinct and elegant style of reasoning has remained at the heart of Western mathematics for over 2000 years.

We can enumerate the primes as follows: p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11 and so on. In Euclid’s proof, we take the product of the first n primes and add 1 to form an integer that we will call Nn. For instance, N4 = (2 x 3 x 5 x 7) + 1 = 211. If we divide N4 by each of the primes p1 to p4 there is a remainder of 1, so none of these primes is a factor of N4. There are only two possible explanations for this. Firstly, N4 could be prime. Secondly, N4 could be a composite number that is a product of primes that are not included in our list p1 to p4. Either way, we have shown that there must be at least one prime that is not included in our list. The critical part of the proof is that this result is true whatever our collection of primes. This means that our list can never be complete—we can always be sure that there is at least one more prime out there. The full list of primes is never ending or, to put it another way, there is an infinite number of primes.

The list below shows the first few numbers Nn of the form used in Euclid’s proof.

N1 = 2 + 1
N2 = (2 x 3) + 1
N3 = (2 x 3 x 5) + 1
N4 = (2 x 3 x 5 x 7) + 1
N5 = (2 x 3 x 5 x 7 x 11) + 1
N6 = (2 x 3 x 5 x 7 x 11 x 13) + 1

It is important to note that Euclid’s method does not imply that the number Nn is prime. It might be prime, but this is not always so. In the first five cases Nn equals a new prime number 3, 7, 31, 211, 2311. In the sixth case, however, N6 = 30031 = 59 x 509, so N6 is not a prime, it is the product of two new primes 59 and 509 that are greater than the six listed primes that were used to construct N6.

A Formula For Primes

Many sequences of numbers can be generated from a simple algebraic expression. For instance, the first five square numbers are 1, 4, 9, 16, 25 and the sequence of square numbers Sn is generated by plugging successive whole numbers into the formula Sn = n2.

Similarly, the first five triangular numbers are 1, 3, 6, 10, 15 and the sequence of triangular numbers Tn is generated by plugging successive whole numbers into the formula Tn = n(n+1)/2. For instance, to find the third triangular number we substitute the value n = 3 into the formula and find T3 = 3 x 4 /2 = 6.

This raises the question. Is it possible to find a formula that will generate all the prime numbers? Leonhard Euler (1707 – 1783), the great Swiss mathematician, discovered the best known formula for generating a sequence of primes Pn in 1772. The formula Pn = n2 + n + 41 works for n = 0, 1, 2, …, 39. Substituting successive integers into the formula we find: P0 = 41, P1 = 43, P2 = 47, …, P39 = 1601. Euler’s prime formula does not generate all the primes between 41 and 1601. Nevertheless, it is remarkable that such a simple formula will generate so many primes when, in many ways, their occurrence among the integers seems almost random.

It is worth noting that the formula must fail to find a prime for the next value of n, as:
P40 = 402 + 40 + 41 = 402 + 2 x 40 + 1 = (40 + 1)2 = 412 = 1681,
so P40 is a square number.

Mathematicians have discovered many other weird and wonderful formulae for generating primes, but the most successful is not very much better than Euler’s, generating 57 distinct primes. There is no formula that will generate the entire infinite sequence of primes.

Keeping Your Secrets

In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman, developed the RSA cryptosystem. Although you may be unaware of the subtle number theoretic calculations your computer is performing, you probably use RSA on a regular basis, as it is now the standard way in which data is securely transmitted via the internet.

The power of RSA derives from the difficulty of factorising a large number into two known primes. Only a moment’s thought is required to figure out that 35 = 7 × 5. But factorising 5,551,383,469 = 87,433 × 63,493 is a little more challenging. A modern computer could factorise 5,551,383,469 in an instant, however, so a product of this size would offer no real protection. For online security, the RSA algorithm is applied to products of primes that are so large their factorisation would take over 100 years on even the most powerful of today’s computers.

How large is a large prime? The current record holder is 274,207,281 – 1, a prime number with 22,338,618 digits found in January 2016 by the Great Internet Mersenne Prime Search (GIMPS). 22,338,618 digits may not sound that impressive but if printed in this font, it would stretch an amazing 46.8 kilometres, which is something to think about on your next road trip.

Further Information

For more about prime generating formulae see:
http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

There is a detailed description of the RSA algorithm in Simon Singh’s excellent The Code Book.

If we would like to know more about enormous prime numbers or lend your computer processing power to the search for even bigger primes, visit: https://www.mersenne.org/

{ 2 comments… read them below or add one }

Carl Larsen November 12, 2017 at 7:11 am

Reading about numbering systems is fascinating, but one tends to lose concentration when the numbers become too large to visualise mentally. When this happens, one begins to wonder if one’s understanding is still valid and are we losing the plot? It all comes down to the level of one’s own ability to keep up with the mind that is generating the information. Prime numbers, or the knowledge of them must have some useful purpose, but it escapes me, and it doesn’t stop me being interested in numbers as a whole. Please keep issuing this stuff, it’s compulsive reading, and it keeps my brain active.

Reply

Steve November 17, 2017 at 10:07 am

Very nice paper, David. Particularly liked the neat proof of there being an infinite number of primes.

Reply

Leave a Comment

Previous post:

Next post: