A Greek and an Indian walk into a bar

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Despite their seemingly simple nature, there are still many unknowns about primes which makes them an always interesting topic to discuss. One of my favorite topics in primes are Prime Sieves, which are methods by which one could generate a list of primes rather easily.

In this brief article I would go over the Sieve of Eratosthenes, it's simplicity, a couple of simple ways to make it into an even more efficient Sieve, the Sieve of Sundaram, and the connection between those 2 sieves that was not at all obvious to me at first sight.

Eratosthenes lived more than 2000 years ago and was a man of many talents as he was a mathematician, poet, astronomer, music theorist, and of course a geographer since he invented the discipline of geography. however he is best known for being the first person to calculate the circumference of the Earth (with about 15% margin of error but I dare you to do any better with 2000 year old technology)

His Prime Sieve method is extremely simple. Start with a list all numbers from $2$ to $N$ with all of them unmarked.

Go to the first unmarked number and you get your first prime: $2$, then simply mark every number of the form $2+2x$ $(1 \le x)$

Now go to next unmarked number and you get your second prime: $3$, then simply mark every number of the form $3+3x$ $(1 \le x)$

Now go to next unmarked number and you get your third prime: $5$,then simply mark every number of the form $5+5x$ $(1 \le x)$

And so on...

doing this would mark all composite numbers but would leave all the prime numbers unmarked, to be later collected.

The Sieve of Eratosthenes also hides within in a rather large simplification: to get all prime numbers up to $N$ you only need to check all numbers up to $\sqrt{N}$ and no further.

Why $\sqrt{N}$? well simply because if you divide $N$ by a number larger than it's square root you get a number which is by definition smaller than it's square root, and since you have already checked all numbers beneath $\sqrt{N}$ to see if they are primes or not, and have also marked all of their multiples, no further information is gained.

Another way to look at it is to observe that if you have a list of all primes numbers $p_1,p_2,p_3,p_4,p_5...p_n$ then you can derive from it the list of all prime numbers up to $p_{n+1}^2$. this is because all numbers that are smaller than $p_{n+1}^2$ must have a factor that is smaller than $p_{n+1}$ which by the definitions of the primes must mean that it's either a prime or can be divided by another prime smaller than it. As such, if in our Eratosthenes Sieve we reach $\sqrt{N}$ we can confidently say that we have generated all prime numbers up to the-next-prime-number$^2$, and since this prime is bigger or equal to $\sqrt{N}$ we have generated all prime numbers up to $N$

If you have a mind like Eratosthenes you might have noticed a way to simplify our sieve even further. since each list up to $p_{n}$ gives us all primes up to $p_{n+1}^2$ we don't need to go over all the numbers between $p_{n+1}$ and $p_{n+1}^2$ when we mark the multiples of $p_{n+1}$ since they would be already marked.

For example let's say that our Eratosthenes Sieve algorithm has already generated the prime list $2,3,5,7$ and is just reaching $11$. according to our original statement the algorithm now needs to mark all multiples of $11$ which are $22,33,44,55,66,77,88,99,110,121...$. but since we already know that all numbers up to $11^2$ are either primes or composites of primes smaller than $11$ we can start marking all multiples of $11$ from $121$ onward and skip $22,33,44,55,66,77,88,99,110$ entirely.

As you can see this Sieve is extremely efficient at what it does.

Another useful sieve is the Sieve of Sundaram which can generate all prime numbers with the exception of 2. This sieve was only discovered in 1934 by Indian mathematician S. P. Sundaram, so it's a quite recent addition to prime research mathematics.

It's basic principle is simple:
each odd number can be written as a multiple of 2 other odd numbers $(1+2i) \times (1+2j)$. multiplying them gives us $1+2i+2j+4ij = 2(i+j+2ij)+1$

With the exception of 2 every prime number is an odd number and can only be written only as $1 \times p$ so that $i$ $or$ $j=0$. As such as long as $i$ or $j$ does not equal $0$ any odd number of the form $2(i+j+2ij)+1$ is an odd composite.

And so by iterating over all natural numbers $1 \le i \le j$ in $i+j+2ij$ we could get all numbers $k$ where $2k+1$ would be a odd composite. While on the other hand, the list we would be left after removing all $k$: $(\mathbb{N}-k = w)$ would be all the numbers where $2w+1=p$.

I would call all $k$ Sundaram Numbers and all $w$ Non Sundaram Numbers.

the first 25 Sundaram Numbers are

$4, 7, 10, 12, 13, 16, 17, 19, 22, 24, 25, 27, 28, 31, 32, 34, 37, 38, 40, 42, 43, 45, 46, 47, 49$

and the first 25 Non Sundaram Numbers are

$1,2,3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36,39,41,44,48,50$

At first it seems like there is no way to generate the Sundaram Numbers other than using 2 numbers but what I have recently learned by experimenting with them is that there is a quite simple and (an after the fact obvious) way of generating the Sundaram Numbers from the Non Sundaram Numbers . And the most striking aspect of that method is that it's only a slight variation of the Sieve of Eratosthenes.

First I'll present the Eratosthenes-Sundaram sieve and later on would give a full explanation of why it works.

Start with a list all numbers from $1$ to $N$ with all of them unmarked.

Go to the first unmarked number and you get your first Non Sundaram Number: $1$, then simply mark every number of the form $1+3x$ $(1 \le x)$

Now go to next unmarked number and you get your second Non Sundaram Number: $2$, then simply mark every number of the form $2+5x$ $(1 \le x)$

Now go to next unmarked number and you get your third Non Sundaram Number: $3$, then simply mark every number of the form $3+7x$ $(1 \le x)$

Now go to next unmarked number and you get your fourth Non Sundaram Number: $5$, then simply mark every number of the form $5+11x$ $(1 \le x)$

And so on...

At the end, all marked numbers would be the Sundaram Numbers and all unmarked numbers would be the Non Sundaram Numbers.

So why is it so?

First either list that is given to us by the Sundaram Numbers or Non Sundaram Numbers is a list of natural odd numbers that were reduced by $1$ and divided by $2$.

So if we have a list of natural odd numbers (excluding $1$)

$S_1=\mathbb{N}_{odd}=$ $3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39...$

the list our algorithm would be given would be

$S_2=\frac{\mathbb{N}_{odd}-1}{2}=$ $1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19...$

Or vice versa we could say that $S_1=2\times S_2 +1$

From this we could easily observe that any addition we might do in the second list would be doubled in the first list. For example if in $S_2$ we do $1+3=4$ then in $S_1$ it would be translated to $(2\times 1 +1) + (2\times 3 +1)=9$

Now assuming we would have wanted to use our original Sieve of Eratosthenes on $S_1$ we would see that all numbers of the form $2x$ would be gone and as such in the process of getting to the next unmarked number $p$ instead of marking every number of the form $p+px$ we would only need to mark every second number which is of the form $p+2px$ . we already know that the list obtained would be either marked odd composites or unmarked primes. Translating it to $S_2$ would give us either marked Sundaram Numbers or unmarked Non Sundaram Numbers.

Translating this to $S_2$ where $p=2w+1$

$\frac{2w+1+2x(2w+1)-1}{2}= w+(2w+1)x = w+px$ $(1 \le x)$

As you can see it seems like the sieve Sundaram discovered was hidden in plain site for 2000 years for all to see, but only recently has been pointed out. Those hidden connections are what makes math fun to research and discover.