Dictionary of Mathematical Eponymy: The Sieve of Sundaram

I am not a number theorist. I mean… well scratch that. I am not an especially knowledgeable number theorist1 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 about2.

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.

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. We’re all number theorists. Some more so than others. []
  2. I haven’t checked that what I’ve written down is precisely what Eratosthenes had in mind, but it’s on the right lines. []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter