Difference between revisions of "Sieve of Sundaram"

(Generalization: tried to comment out the work in progress...)
m (Generalization for r-almost prime finding)
 
(9 intermediate revisions by the same user not shown)
Line 75: Line 75:
 
==Optimization==
 
==Optimization==
  
The equivalent in Step 2 above, of the [[Sieve of Eratosthenes]] starting the at the next prime squared, is starting at <math>2c^2+2c</math> for next index <math>c</math>
+
The equivalent in Step 2 above, of the [[Sieve of Eratosthenes]] starting the at the next prime squared, is starting at <math>2f^2+2f</math> for next index <math>f</math>
  
==Generalization==
+
==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 <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):
 
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}
+
<cmath>\begin{array}{ccccccccc}
%c\slash d&1&7&11&13&17&19&23&29\\
+
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\\
+
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+7%b+4&23a+7b+5&29a+7b+6\\
+
7&a+7b&7(a+b)+1&11a+7b+2&13a+7b+3&17a+7b+3&19a+7+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\\
+
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&62&63&64&65&66&67&68\\
+
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&77&78&79&80&81&82&83&84\\
+
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\\
+
19&a+19b&7a+19b+4&11a+19b+6&13a+19b+8&17a+19b+10&19(a+b)+12&23a+19b+14&29a+19b+18\\
%23&107&108&109&110&111&112&113&114\\
+
23&a+23b&7a+23b+13&11a+23b+8&13a+23b+9&17a+23b+13&19a+23a+14&23(a+b)+17&29a+23b+22\\
%29&122&123&124&125&126&127&128\\
+
29&a+29b&7a+29b+6&11a+29b+10&13a+29b+12&17a+29b+16&19a+29b+18&23a+29b+22&29(a+b)+28\\
%\end{array}</cmath>
+
\end{array}</cmath>
  
 +
The table leaves <math>30ab</math> off each to save space. the general rule, for modulus <math>m</math>, with remainders <math>c,d</math> is: <cmath>m(mab+da+cb+\lfloor {cd\over m}\rfloor)+(cd\bmod m)</cmath> in general.
  
 +
==Generalization for r-almost prime finding==
  
 +
<math>r</math>-almost prime
  
 +
: A natural number with <math>r</math> prime factors including repetitions.
  
 +
The sieve can be recursed on arguments <math>a</math> and <math>b</math> to check <math>mb+d</math> or <math>ma+c</math> 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 <math>a,b</math> 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 Eratosthenes]]
  
  
  
 
[[Category:Algorithms]]
 
[[Category:Algorithms]]

Latest revision as of 18:10, 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 $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+7+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&a+19b&7a+19b+4&11a+19b+6&13a+19b+8&17a+19b+10&19(a+b)+12&23a+19b+14&29a+19b+18\\ 23&a+23b&7a+23b+13&11a+23b+8&13a+23b+9&17a+23b+13&19a+23a+14&23(a+b)+17&29a+23b+22\\ 29&a+29b&7a+29b+6&11a+29b+10&13a+29b+12&17a+29b+16&19a+29b+18&23a+29b+22&29(a+b)+28\\ \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 Eratosthenes

Invalid username
Login to AoPS