# 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.

Note by Daniel Magen
5 years, 1 month ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Dear Daniel, I'm a mathematician for hobby and I was studying the prime numbers looking for some property I came across a nice relationship between the position and the number, so since it seemed not possible that no one had ever highlighted this relationship I wanted to do a search on the internet and so I discovered I had rediscovered the Sieve of Sundaram! If you are interested, I'd like to send you my small study, which if you think fit, could partially supplement your article Your sincerely Silvio Gabbianelli

- 2 years, 11 months ago

Dear Silvio, first of all, I'm sorry for the late reply, I got no notice of your comment and for the last couple of years I have not logged in to this site, so it's quite fortunate that I saw your comment only 2 weeks after you posted it. of course, I will gladly read it, my mail is

secondly, I was\am a hobby mathematician as well, I started learning mathematics and computer science at the Hebrew University last year, and I certainly was a hobby mathematician when I wrote this article. I share your sense of excitement yet disappointment at rediscovering old knowledge, my entire 2 part article on this site "How many numbers do a given set of primes generate as a fraction of all natural numbers" turned out to be useless and inefficient because a much better solution has existed for a couple hundred years - Euler's totient function.

I also searched privately for a way to generate algebraic equations for binary, ternary and generally n-tary logic gates, before I began to study at the university, and managed to make an evolutionary program that took quite some time to find all the ternary equations (there are 3^9=19683 of them) and was quite proud of it. but in my first semester, I learned about linear interpolation and was able to create a general formula to find all algebraic equations for any n-tary logic gates using nothing more than simple matrices operations, which made my program useless.

as you can see I'm familiar with the sense of excitement yet disappointment at rediscovering old knowledge :)

- 2 years, 11 months ago