Difference between revisions of "Sieve of Sundaram"

m (Optimization)
m
Line 68: Line 68:
 
&&457&&461&463&&467&&&&&&479&\
 
&&457&&461&463&&467&&&&&&479&\
 
\end{array}</cmath>
 
\end{array}</cmath>
 +
 +
==Basis==
 +
 +
The basis of the algorithm is that for <math>1\leq a\leq b</math> (without loss of generality, as the form we double and add 1 to is made up of commutative operations); <math>2(2ab+a+b)+1=(2a+1)(2b+1)</math> with both factors nontrivial.
  
 
==Optimization==
 
==Optimization==
Line 75: Line 79:
 
==Generalization==
 
==Generalization==
  
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.
+
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 <math>\varphi(m)</math> copies of the same numbers ( one for each class), or <math>T_{\varphi(m)}</math> (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):
 +
 
 +
<cmath>%\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&23a+11b+8&53&54\
 +
13&62&63&64&65&66&67&68\
 +
17&77&78&79&80&81&82&83&84\
 +
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}</cmath>
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
[[Category:Algorithms]]

Revision as of 10:39, 27 February 2020

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 $2c^2+2c$ for next index $c$

Generalization

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&23a+11b+8&53&54\\
13&62&63&64&65&66&67&68\\
17&77&78&79&80&81&82&83&84\\
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}\] (Error compiling LaTeX. Unknown error_msg)