## Sundaram's Sieve

Submitted by plusadmin on March 1, 2009The primes are the atoms among numbers. But how can we find them all?

The prime numbers — so simple, yet so mysterious. Primes are those numbers that are divisible only by themselves and the number 1. They are the atoms amongst the integers because every whole number can be written as a product of a unique set of primes. We have known since the time of Euclid that there are infinitely many primes — there is no largest prime — but there is no general formula that
generates all of them. Their distribution among the other numbers is still a mystery and motivates some of the biggest open questions in mathematics (see the *Plus* articles A whirlpool of numbers and Mathematical mysteries: the Goldbach conjecture). As the eighteenth century mathematical genius
Leonhard Euler put it, "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate."

However, all is not lost: we do have algorithms that can find all the primes up to a given number. In this article we'll look at an example of such an algorithm, in which the primes pop out of a very simple, and highly regular, structure as if by magic. It's called the *sieve of Sundaram*, after an obscure East Indian mathematician by the name of S.P. Sundaram, who discovered it in the
1930s. Sundaram's algorithm is not a real sieve, of course, but a clever way of spotting numbers that are not prime, thus "sieving out" those that are.

Sundaram's sieve is based on an array of numbers formed from *arithmetic progressions*, in other words, sequences of numbers in which successive numbers are a given fixed distance apart.

We start with the infinite sequence in which successive numbers are exactly three steps apart, and which starts with the number 4:

Next up is the sequence starting with the number 7 and with successive numbers exactly 5 steps apart:

Now consider the sequence starting with the number 10 and with a difference of 7 between successive numbers:

You can see the pattern emerging: the starting point of each sequence is three steps on from that of the previous one, and the distance between successive numbers is the distance of the previous sequence plus 2. Writing the sequences beneath each other, we get the following doubly infinite array:

4 | 7 | 10 | 13 | 16 | 19 | 22 | 25 | ... |

7 | 12 | 17 | 22 | 27 | 32 | 37 | 42 | ... |

10 | 17 | 24 | 31 | 38 | 45 | 52 | 59 | ... |

13 | 22 | 31 | 40 | 49 | 58 | 67 | 76 | ... |

16 | 27 | 38 | 49 | 60 | 71 | 82 | 93 | ... |

.. | .. | .. | .. | .. | .. | .. | .. | ... |

The array exhibits a lot of structure: the first row is equal to the first column, each row is an arithmetic progression, and the differences between entries in two consecutive rows form the sequence

Now pick any number in this array, double it, add 1, and ask yourself if the resulting number is a prime. Repeat this a few times and you'll find that your answer, no matter which number from the array you pick, is always "no". So what about the numbers not in the array, for example 5, 6, 8, etc? A few calculations should convince you that for a number *N* not in the array, the number
2*N*+1 is prime.

That is, the first set of calculations suggests that

*N*lies in the array, then 2

*N*+1 is not prime.

*N*does not lie in the array, then 2

*N*+1 is prime.

We can roll the two statements into one as follows:

*N*+1 is prime, if — and only if —

*N*does not lie in the array.

Euclid of Alexandria, ca 325 BC - 265 BC. He proved that there are infinitely many primes.

If this statement is indeed true for all numbers *N*, then it gives us a way of deriving the sequence of primes, with all its well-known irregularity, from an array with a high degree of mathematical structure, and the simplest structure as well: that of arithmetic progressions. Quite an amazing result!

But can we be sure that the statement is true for all *N*? We can indeed, because it is possible to prove it in its full generality. But rather than giving you the proof to read off the page, we challenge you to come up with your own version. It doesn't require any mathematical knowledge beyond a familiarity with multiplication and division, and a tiny bit of algebra. If you get stuck,
the three steps below guide you through the process, and there are hints too, in case you need them.

### Conclusion

If you've found your way through our three steps, or have found your own version of the proof, then you have shown that *N* lies in the array if and only if 2*N*+1 is not prime. This proves that Sundaram's sieve works: to find the *kth* prime, simply find the (*k*-1)st number not in the array, double it, and add 1. (It's the (*k*-1)st missing number, because the array
doesn't generate the first prime, which is 2.)

Of course, there are other methods for "sieving out" primes, including the famous *sieve of Eratosthenes* (see the *Plus* article Goldbach revisited) and the lesser-known *visual sieve* (see the *Plus* article Catching primes). These methods are altogether different, although their
workings are equally mysterious and the mathematics involved is similarly elementary.

### About the author

Julian Havil is a prematurely retired mathematics teacher who for 33 years taught the subject at Winchester College. He spends his retirement as people should, enjoying the freedom it brings and trying to make good use of the time gifted to him: writing books and articles, giving talks, and travelling both for teaching and for leisure.

Havil's books *Impossible?*, *Nonplussed!*, and *Gamma: Exploring Euler's Constant*, have all been reviewed in *Plus*.

Havil's latest book has the working title *The Irrationals*. It will give an historical account of their discovery and development throughout the centuries, spanning ancient Greece to 19th century Europe. It will explore the importance of these numbers, as well as many significant results associated with them. The book will be aimed at good sixth form students and above, and will be
published by Princeton University Press.