Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
[In reply to a now-deleted comment]I mean the polynomial does not generate that prime. The sieve isn't looking for anything like that - it's an algorithm that says e.g. "after 3 more primes, the next number is non-prime". I do not understand the significance of 163 @n=245 but I only point out its uniqueness among all its priors. FYI, these "mongrel" non-primes also form a simple series. Hence my original question about the generalisability of this approach. –  Andrew Palfreyman Oct 4 '13 at 4:51
    
I have now discovered a new pairwise series set very similar to the first set, which explains the above. I still do not know the answer to the generalisability question, but the fact that primes can be sieved using only a set of linearly increasing gaps is intriguing, and seems to point to some deeper result. –  Andrew Palfreyman Oct 9 '13 at 19:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.