I am not a number theorist. I mean… well scratch that. I am not an especially knowledgeable number theorist ((We’re all number theorists. Some more so than others.)) but I do enjoy number theory when it’s around my level.

The Sieve of Sundaram is about my level.

What is the Sieve of Sundaram?

OK, let’s start with the Sieve of Eratosthenes, which is considerably harder to say, but also much easier to think about ((I haven’t checked that what I’ve written down is precisely what Eratosthenes had in mind, but it’s on the right lines.)).

An algorithm for finding all of the primes smaller than $n$ goes as follows:

  1. Make a list of all of the numbers from 2 to $n$.
  2. Take the smallest number, $p$, remaining in the list and write it down as a prime.
  3. Remove every multiple of $p$ remaining in the list.
  4. Go back to step 2 until its first number is larger than $\sqrt{n}$.
  5. Add the remaining numbers in your list to the list of primes.

To list all the primes up to 25, you would:

  • Start with 2,3,4,5, … , 23, 24, 25.
  • So 2 is a prime! We delete every multiple of 2, leaving us 3,5,7,9,11,…23, 25.
  • So 3 is a prime! We delete every multiple of 3, leaving us 5,7,11,13,17,19,23,25.
  • So 5 is a prime! We delete every multiple of 5, leaving us 7,11,13,17,19,23.

We’ve written down 2, 3, 5, 7,11,13,17,19,23 as primes - exactly the primes up to 25.

This is the idea of prime sieving: because primes are (in some sense) what’s left over once you take the patterns away, sieving takes away the patterns and leaves you with the primes. There are many different types of sieve; as I say, Sundaram’s is on my level. Here’s the algorithm:

  • List the numbers from 1 to $n$
  • For $j$ between 1 and $n$, inclusive:
    • For $i$ between 1 and $j$, inclusive:
      • if $i + j + 2ij \le n$, remove it from the list
  • Double the remaining numbers and add 1.

What remains is all of the odd primes between 1 and $2n+2$.

Again, to list all of the odd primes from 1 to 25, let $n=12$, and run through all the possible values for $i$ and $j$:

  • $(1,1)$: remove 4.
  • $(2,1)$: remove 7.
  • $(2,2)$: remove 12.
  • $(3,1)$: remove 10.
  • $(3,2)$: (too high - skip (3,3))
  • $(4,1)$: (too high - we’re done)

We’re still got 1, 2, 3, 5, 6, 8, 9 and 11.

Double these and add 1, and we get 3, 5, 7, 11, 13, 17, 19 and 23. Boom!

Why is it important?

As is so often the case, I’m not sure that the Sieve of Sundaram is important so much as it is interesting. It’s significantly quicker than the Sieve of Eratosthenes, and it’s a bit more work to figure out why it works.

The numbers that are removed from the list are of the form $i + j + 2ij$. Those correspond - after the double-and-increment step - to numbers of the form $2i + 2j + 4ij + 1$, which factorises as $(1+2i)(1+2j)$.

What the Sieve of Sundaram does is systematically remove all of the odd composite numbers. In addition, it only touches the odd semiprimes once each. It’s really neat!

Who was Sundaram?

Although he was slightly earlier, looking for George Osborn was comparatively easy. S. P. Sundaram has left very little trace on the internet. The most I can tell you is that he was a student from Sathyamangalam in Tamil Nadu, India.

As always, if you know more, I’d love to hear about it!

* Edited 2020-07-06 to fix a typo.