21554The munchkin seive - has it been done?
- Jul 2, 2010The munchkin seive is actually 2 analogous seives, one for 6n+1 primes (npp) and the other for 6n-1 primes (npm).
The 6n + 1 seive
Let a be a positive integer. The npp values relative to a are 6a ± (a/b + b) where b is a factor of a and a >= b².
So a = 1 npp = 4, 8
a = 2 npp = 9, 15
a = 3 npp = 14, 22
a = 4 npp = 29, 19, 28
If c is a positive integer then c is npp or 6c +1 is prime.
The 6n 1 sieve
Let a be a positive integer. The npm values relative to a are 6a ± (a/b - b) where b is a factor of a and a >= b².
If c is a positive integer then c is npm or 6c-1 is prime.
How did I get here?
Given a 6n +1 number that was not prime then it must have had either a pair of factors (6g+1)(6h+1) or a pair (6g-1)(6h-1). These give 36gh + 6g +6h +1 or 36gh 6g 6h +1 (which are the two sides of the seive)
Similarly 6n -1 gives (6g+1)(6h-1) = 36gh 6g + 6h -1 (which gives both sides of the npm seive)
Subtract (or add) 1 and divide by 6 to get the seive formulas.
Yeah! So what?
The seive grows geometrically, 5n to 7n, as opposed to most sieves that grow exponentially. Take any number a, the range is (depending on the seive) 5a ± 1 to 7a ± 1 and you need to calculate values for 5a/7 <= A <= 7a/5.
Observation. The npp and npm values are symmetrical about node 6a. But the (a-1) values and the (a+1) values differ. So there can be no non-trivial nodes about which the 6n+1 or the 6n-1 primes are symmetrical.
Princess Sophie - how do you spell seive?