Sieve of Sundaram

Revision as of 14:49, 27 February 2020 by Science man 88 (talk | contribs)

Description

The Sieve of Sundaram is a sieve for a range of odd prime numbers.The sieve starts out listing the natural numbers $1$ to $n$ like the following example ($n=240$)

\[\begin{array}{ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ 16&17&18&19&20&21&22&23&24&25&26&27&28&29&30\\ 31&32&33&34&35&36&37&38&39&40&41&42&43&44&45\\ 46&47&48&49&50&51&52&53&54&55&56&57&58&59&60\\ 61&62&63&64&65&66&67&68&69&70&71&72&73&74&75\\ 76&77&78&79&80&81&82&83&84&85&86&87&88&89&90\\ 91&92&93&94&95&96&97&98&99&100&101&102&103&104&105\\ 106&107&108&109&110&111&112&113&114&115&116&117&118&119&120\\ 121&122&123&124&125&126&127&128&129&130&131&132&133&134&135\\ 136&137&138&139&140&141&142&143&144&145&146&147&148&149&150\\ 151&152&153&154&155&156&157&158&159&160&161&162&163&164&165\\ 166&167&168&169&170&171&172&173&174&175&176&177&178&179&180\\ 181&182&183&184&185&186&187&188&189&190&191&192&193&194&195\\ 196&197&198&199&200&201&202&203&204&205&206&207&208&209&210\\ 211&212&213&214&215&216&217&218&219&220&231&222&223&224&225\\ 226&227&228&229&230&231&232&233&234&235&236&237&238&239&240\\ \end{array}\]

Step 2

Then it finds all numbers of form $2ab+a+b$ ( fancy way of saying start at $a$ and increase by $2a+1$, for each not already eliminated $a$) and eliminates them (empty cells):

\[\begin{array}{ccccccccccccccc} 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&51&&53&54&&56&&&&\\ &&63&&65&&&68&69&&&&&74&75\\ &&78&&&81&&83&&&86&&&89&90\\ &&&&95&96&&98&99&&&&&&105\\ &&&&&111&&113&114&&116&&&119&120\\ &&&&125&&&128&&&131&&&134&135\\ &&138&&140&141&&&&&146&&&&\\ &&153&&155&156&&158&&&&&&&165\\ &&168&&&&&173&174&&176&&&179&\\ &&183&&&186&&&189&&191&&&194&\\ &&198&&200&&&&204&&&&&209&210\\ &&&&215&216&&&219&&221&&&224&\\ &&228&&230&231&&233&&&&&&239&\\ \end{array}\]


Step 3

Double each number and add one:

\[\begin{array}{ccccccccccccccc} 3&5&7&&11&13&&17&19&&23&&&29&31\\ &&37&&41&43&&47&&&53&&&59&61\\ &&67&&71&73&&&79&&83&&&89&\\ &&97&&101&103&&107&109&&113&&&&\\ &&127&&131&&&137&139&&&&&149&151\\ &&157&&&163&&167&&&173&&&179&181\\ &&&&191&193&&197&199&&&&&&211\\ &&&&&223&&227&229&&233&&&239&241\\ &&&&251&&&257&&&263&&&269&271\\ &&277&&281&283&&&&&293&&&&\\ &&307&&311&313&&317&&&&&&&331\\ &&337&&&&&347&349&&353&&&359&\\ &&367&&&373&&&379&&383&&&389&\\ &&397&&401&&&&409&&&&&419&421\\ &&&&431&433&&&439&&443&&&449&\\ &&457&&461&463&&467&&&&&&479&\\ \end{array}\]

Basis

The basis of the algorithm is that for $1\leq a\leq b$ (without loss of generality, as the form we double and add 1 to is made up of commutative operations); $2(2ab+a+b)+1=(2a+1)(2b+1)$ with both factors nontrivial.

Optimization

The equivalent in Step 2 above, of the Sieve of Eratosthenes starting the at the next prime squared, is starting at $2f^2+2f$ for next index $f$

Generalization for prime finding

Looking close, if you know modular arithmetic, you'll note the remainder 1 forms the modular multiplicative group modulo 2. This generalizes to the modular multiplicative group mod any natural number( with loss of factors in the prime list). This generalization either needs $\varphi(m)$ copies of the same numbers ( one for each class), or $T_{\varphi(m)}$ (triangle numbers) colors . The class of remainder 1, is the only class where variable must stay nonzero to introduce a nontrivial factor by default ( negative representatives increase variable value required by 1). Modulo 30 is sketched out below (8 classes):

\[\begin{array}{ccccccccc} c\slash d&1&7&11&13&17&19&23&29\\ 1&a+b&7a+b&11a+b&13a+b&17a+b&19a+b&23a+b&29a+b\\ 7&a+7b&7(a+b)+1&11a+7b+2&13a+7b+3&17a+7b+3&19a+7b+4&23a+7b+5&29a+7b+6\\ 11&a+11b&7a+11b+2&11(a+b)+4&13a+11b+4&17a+11b+6&19a+11b+6&23a+11b+8&29a+11b+10\\ 13&a+13b&7a+13b+3&11a+13b+4&13(a+b)+5&17a+13b+7&19a+13b+8&23a+13b+9&29a+13b+12\\ 17&a+17b&7a+17b+3&11a+17b+6&13a+17b+7&17(a+b)+9&19a+17b+10&23a+17b+13&29a+17b+16\\ 19&92&93&94&95&96&97&98&\\ 23&107&108&109&110&111&112&113&114\\ 29&122&123&124&125&126&127&128&\\ \end{array}\]

The table leaves $30ab$ off each to save space. the general rule, for modulus $m$, with remainders $c,d$ is: \[m(mab+da+cb+\lfloor {cd\over m}\rfloor)+(cd\bmod m)\] in general.

Generalization for $r$-almost prime finding

$r$-almost prime

A natural number with $r$ prime factors including repetitions.

The sieve can be recursed on arguments $a$ and $b$ to check $mb+d$ or $ma+c$ for primality, if both are, we have a semiprime.

On the chance we don't get back prime for more than one, we can test the components. This will find out if our original number had 3 prime factors.

In the case of neither of $a,b$ get back prime we have at least 4 prime factors, and this can go to any depth you choose.


See Also:

Number Theory Sieve of Erastosthenes