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 22 to NN with all of them unmarked.

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

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

Now go to next unmarked number and you get your third prime: 55,then simply mark every number of the form 5+5x5+5x (1x)(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 NN you only need to check all numbers up to N\sqrt{N} and no further.

Why N\sqrt{N}? well simply because if you divide NN 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 N\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 p1,p2,p3,p4,p5...pnp_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 pn+12p_{n+1}^2. this is because all numbers that are smaller than pn+12p_{n+1}^2 must have a factor that is smaller than pn+1p_{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 N\sqrt{N} we can confidently say that we have generated all prime numbers up to the-next-prime-number2^2, and since this prime is bigger or equal to N\sqrt{N} we have generated all prime numbers up to NN

If you have a mind like Eratosthenes you might have noticed a way to simplify our sieve even further. since each list up to pnp_{n} gives us all primes up to pn+12p_{n+1}^2 we don't need to go over all the numbers between pn+1p_{n+1} and pn+12p_{n+1}^2 when we mark the multiples of pn+1p_{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,72,3,5,7 and is just reaching 1111. according to our original statement the algorithm now needs to mark all multiples of 1111 which are 22,33,44,55,66,77,88,99,110,121...22,33,44,55,66,77,88,99,110,121.... but since we already know that all numbers up to 11211^2 are either primes or composites of primes smaller than 1111 we can start marking all multiples of 1111 from 121121 onward and skip 22,33,44,55,66,77,88,99,11022,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)×(1+2j)(1+2i) \times (1+2j) . multiplying them gives us 1+2i+2j+4ij=2(i+j+2ij)+11+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×p1 \times p so that ii oror j=0j=0. As such as long as ii or jj does not equal 00 any odd number of the form 2(i+j+2ij)+12(i+j+2ij)+1 is an odd composite.

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

I would call all kk Sundaram Numbers and all ww 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,494, 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,501,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 11 to NN with all of them unmarked.

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

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

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

Now go to next unmarked number and you get your fourth Non Sundaram Number: 55, then simply mark every number of the form 5+11x5+11x (1x)(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 11 and divided by 22.

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

S1=Nodd=S_1=\mathbb{N}_{odd}= 3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39...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

S2=Nodd12=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...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 S1=2×S2+1S_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 S2S_2 we do 1+3=41+3=4 then in S1S_1 it would be translated to (2×1+1)+(2×3+1)=9(2\times 1 +1) + (2\times 3 +1)=9

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

Translating this to S2S_2 where p=2w+1p=2w+1

2w+1+2x(2w+1)12=w+(2w+1)x=w+px\frac{2w+1+2x(2w+1)-1}{2}= w+(2w+1)x = w+px (1x)(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
3 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Silvio Gabbianelli - 1 year, 2 months ago

Log in to reply

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 :)

Daniel Magen - 1 year, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...