More Fun with Primes
In the first essay, Fun with Primes, two prime number sieves, one attributed to Eratosthenes and one that was a geometric, or visual, interpretation of such were examined. In this piece, we will study a different type of sieve. This sieve takes a different approach, one dealing more with parity, in generating the prime numbers.
Sieve of Sundaram
S. P. Sundaram was a student of mathematics from Sathyamangalam, East India in the early twentieth century. He discovered this sieve, which eliminates all composite numbers, from a list of natural values ranging from 1 to any n. His method is based upon the idea of parity, which is to say if a specific number is either odd or even. As can be readily discovered, consider what happens when you multiply values of the same or different parity:
An even number x another even number yields an even number
An even number x an odd number yields an even number
An odd number x another odd number yields an odd number
We know that all even numbers with the exception of the number 2 are composite, as they are multiples of 2, so, we are really interested in what products will yield an odd number. From our examination above, it is important to know that in order to get an odd product, you must have two odd factors. We can call these odd factors (2i + 1) and (2j + 1), and their product (2n + 1).
(2i + 1)(2j + 1) = (2n + 1)
By expanding the right hand side of this equation, we have:
4ij + 2i + 2j + 1 = 2n + 1
Finally, we can simplify by subtracting 1 and dividing by 2 on both sides:
2ij + i + j = n
What this amounts to is if a value, n, can be expressed as 2ij + i + j (where i and j are natural numbers), then it can be doubled, and 1 added to form a composite number. Removing all such values for n eliminates all compositeproducing values and leaves only primegenerating natural numbers.
So letŐs look at a concrete example of how this works. LetŐs say we want to develop a list of all prime values which are less than 100. We will need to determine (and eliminate!) all values for n which are less than 50 (because we will double n, and add 1 to achieve our list of primes).
These values for n which are compositeproducing can be found by hand, or more expediently, by software. Below, you will see a table generated in Excel which calculates these values. The row headers are values for i, and the column headers are values for j. Note that only j values which are greater than or equal to i are utilized, as we do not need to do the same calculation for a mere permutation of i and j.
CompositeGenerating
Values for n
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 

1 
4 
7 
10 
13 
16 
19 
22 
25 
28 
31 
34 
37 
40 
43 
46 
49 
2 
12 
17 
22 
27 
32 
37 
42 
47 
52 
57 
62 
67 
72 
77 
82 

3 
24 
31 
38 
45 
52 
59 
66 
73 
80 
87 
94 
101 
108 
115 

4 
40 
49 
58 
67 
76 
85 
94 
103 
112 
121 
130 
139 
148 

5 
60 
71 
82 
93 
104 
115 
126 
137 
148 
159 
170 
181 

6 
84 
97 
110 
123 
136 
149 
162 
175 
188 
201 
214 
Notice that we donŐt really need rows 5 and 6 as they do not contain any values less than or equal to 50.
1 
11 
21 

41 
2 




3 

23 
33 


14 


44 
5 
15 

35 

6 

26 
36 






8 
18 


48 
9 

29 
39 


20 
30 

50 
Now we want to take a list of all natural numbers from 1 to 50 (remember this is half of the maximum upper bound that we previously determined), and eliminate all values that are found in the table. The table at right shows the list of these natural numbers, and the values from the table above are indicated by a strikethrough:
1 
11 
21 

41 
2 




3 

23 
33 


14 


44 
5 
15 

35 

6 

26 
36 






8 
18 


48 
9 

29 
39 


20 
30 

50 
3 
23 
43 

83 
5 




7 

47 
67 


29 


89 
11 
31 

71 

13 

53 
73 






17 
37 


97 
19 

59 
79 


41 
61 

101 
What we have done thus far is to eliminate (or sieve out) all values for n that will generate composite numbers. Those values which remain will generate prime values when we double them, and add 1. The result of this simple calculation is shown in the table at right.
And so we see that this relatively recent discovery is yet another simple algorithm for determining the prime numbers.
Sources:
http://plus.maths.org/content/sundaramssieve
http://luckytoilet.wordpress.com/2010/04/18/thesieveofsundaram/
http://en.wikipedia.org/wiki/Sieve_of_Sundaram
http://pballew.blogspot.com/2010/03/differentprimesieve.html