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