# Difference between revisions of "Sieve of Sundaram"

(→Generalization: tried to comment out the work in progress...) |
m (→Generalization) |
||

Line 77: | Line 77: | ||

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>2c^2+2c</math> for next index <math>c</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\\ | |

− | + | 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\\ | |

− | + | 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}</cmath> | |

## Revision as of 13:17, 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 ()

### 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):

### Step 3

Double each number and add one:

## 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%b+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}\] (Error compiling LaTeX. ! Extra alignment tab has been changed to \cr.)