Sundaram’s Sieve

Sundaram’s sieve, like the Sieve of Eratosthenes, finds prime numbers.  It relies wholly on a easily constructable symmetric table.  The first row (and column), is an arithmetic sequence, starting with a = 4 with a step of d = 3.  The remainder of the rows are also arithmetic sequences with their a’s determined by the original sequence.  For the second row, now, use d = 5 as the step, and use d = 7 for the step for the third row.  Continue this pattern, letting each row’s d be the next highest odd integer than for the row above.  This creates the following table:

4

7

10

13

16

7

12

17

22

27

10

17

24

31

38

13

22

31

40

49

16

27

38

49

60

Let N > 2 be any natural number.  Then N occurs on the table if and only if 2N + 1 is composite.  There are two proofs of this pivotal statement; one is via a companion chart, the second via elementary algebra.  Both proofs will be discussed.

The Table Proof

We construct a companion table to the original one, where each entry, N, in the original table is replaced by 2N +1 in the companion table.  Thus we have

9

15

21

27

33

15

25

35

45

55

21

35

49

63

77

27

45

63

81

99

33

55

77

99

121

This table shows all composites x = pq, where p and q are odd natural numbers.  The only numbers not on the table are either even or prime.  Since the only even prime, 2, has been neatly avoided by the assumption that N > 2, any odd number not on this companion table must be prime.  Therefore if N appears on the original table, then 2N +1 is a composite of two odd numbers, and if an odd number 2N+1 does not appear on the companion table (and thus is prime), then N does not appear on the original table.

The Algebraic Proof

            Let Sm,n represent the entry in the mth column and nth row.  It is easy to confirm that .  Suppose that the natural number N > 2 occurs on the table.  Then there exist natural numbers m and n such that .  Consider 2N + 1.

Therefore 2N + 1 is composite.

            Conversely, suppose 2N +1 = pq for natural numbers p and q, both greater than 1.  2N +1 is odd, so p and q must be odd.  Let m and n be natural numbers such that  and .

Therefore, , so N is in the chart.

Connections to Cryptography

            Sundaram’s sieve is tied to primality testing and factoring odd numbers.  It is not, however, practical to use for the thousand-digit numbers typical in modern cryptography and cryptanalysis.  The problem lies in the difficulty to predict whether or not a large number lies in the table without direct computation.

 

References:

New Zealand Maths Newletter 18 (October 2002).  [On-line] www.nzmaths.co.nz/HelpCentre/Newsletter18.pdf  September 8, 2004.

 

Ogilvy, C. Stanley and John T. Anderson.  Excursions in Number Theory.  Oxford University Press, Inc., New York.  ©1966.

Andrew Baxter