Difference between revisions of "Sieve of Sundaram"
m |
m (→Generalization for r-almost prime finding) |
||
| (11 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> | + | 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> | + | <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&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& | + | 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& | + | 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& | + | 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& | + | 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& | + | 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& | + | 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 17:10, 27 February 2020
Contents
Description
The Sieve of Sundaram is a sieve for a range of odd prime numbers.The sieve starts out listing the natural numbers 
to 
like the following example (
)
![\[\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}\]](http://latex.artofproblemsolving.com/1/f/b/1fb43c28342ee1eef193f9405ef6ba6e6df9d701.png)
Step 2
Then it finds all numbers of form 
( fancy way of saying start at 
and increase by 
, for each not already eliminated ) 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}\]](http://latex.artofproblemsolving.com/8/b/9/8b96884dfae94b90bdead212feac47cfb43f5df6.png)
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}\]](http://latex.artofproblemsolving.com/0/e/8/0e89acc7a18058912a639f17412b9eec35f004e2.png)
Basis
The basis of the algorithm is that for 
(without loss of generality, as the form we double and add 1 to is made up of commutative operations); 
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 
for next index 
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 
copies of the same numbers ( one for each class), or 
(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}\]](http://latex.artofproblemsolving.com/0/5/e/05eefcac035174405e13311a9ba928733e36720c.png)
The table leaves 
off each to save space. the general rule, for modulus 
, with remainders 
is: ![\[m(mab+da+cb+\lfloor {cd\over m}\rfloor)+(cd\bmod m)\]](http://latex.artofproblemsolving.com/c/e/7/ce74170dcc10fc7c4007e75e7a3073eb32a06c80.png)
in general.
Generalization for r-almost prime finding
-almost prime
- A natural number with
prime factors including repetitions.
The sieve can be recursed on arguments and 
to check 
or 
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 
get back prime we have at least 4 prime factors, and this can go to any depth you choose.
See Also:
