I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the form m(k) = m(k-1) + C(k); k=0,1,2.., C(k) = A*k + B, A,B constants, s.t. if n=m(k), then that entry should be discarded. There is one extra new such sieve for each multiple of the range mod 41. For example:
2 <= n <= 40 : all numbers are prime
1*41 <= n < 2*41: gaps between non-primes go as 0,2,4,6,8..
2*41 <= n < 3*41: gaps between non-primes go as 0,1,2,3,4..
3*41 <= n < 4*41: gaps between non-primes go as 0,3,2,7,4,11,6.., which is the interleave of the 2 series 3,7,11.. and 2,4,6..
4*41 <= n < 5*41: gaps between non-primes go as 0,5,2,11,4,17,6.., which is the interleave of the 2 series 5,11,17.. and 2,4,6..
5*41 <= n < 6*41: gaps between non-primes go as 0,7,2,15,4,23,6.., which is the interleave of the 2 series 7,15,23.. and 2,4,6..
and so forth. The rule is that a generated number is prime if all sieves fail to reject it. As n grows, so does the number of sieves. It is clear that the sieves are simply related and are computationally very cheap. It seems perhaps surprising that these simple arithmetic progressions suffice to rid the list of non-primes. The pairwise interleaving I find similarly surprising.
This method generates 100% correctly-sieved primes from n=1 (41) up to n=244 (58847). All non-primes are correctly discarded, and no primes are discarded by the sieves.
However, at n=245, a non-prime is found (59821) which is not discarded. The uniqueness of this non-prime is that its lowest prime factor is not in the sequence, unlike all prior non-primes discarded. I would like to extend this technique but am stuck on n=245. Can anyone afford me some insight?