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 have played around with deriving a Boolean IsPrime function. http://science.niuz.biz/boolean-t313980.html?s=5e8b6805a1b73daa7c1062fabbe74e90

I have found a simple method for deriving a single clause in this IsPrime function. I start with 1 or an odd, composite number. Find the first power of 2 such that 2^k+1 is composite. This is 9. Add 9 to the set. Now find the first "composite power of 2" such that both 2^k+1 and 2^k+9 are composite. This is 2^11. Add these composites to the set and repeat. Starting with 1, we get the sequence 1, 9, 2049, 2057, 4097, 4105, 6145, 6153, ... http://oeis.org/A173281. I know the next term in the first sequence is greater than 2^23. My question is: is this a "good" prime sieve? If I randomly chose eight odd numbers greater than 2^22, would I expect one of these numbers to be prime? 2^20 + 6145, 2^21 + 4097, and 2^22 + 4105 are all prime.

share|improve this question
    
What do you want from your prime sieve? Good is in the eye of the beholder. Numbers are prime with probability $\frac 1{\ln n}$, so around $2^{22}$ about 1 in 15 numbers is prime. If you restrict to odd ones, your odds are about 1 in 8. The fact that there are only these eight terms in OEIS suggests that any more are quite a bit larger. –  Ross Millikan Oct 24 '12 at 20:47
    
I guess I would want a method for choosing numbers of a given size that might be prime. I put the terms in OEIS. I stopped at eight because that is the minimum they like to have. I have no reason to think this a good method for finding primes. Your comment suggests it is not much better than chance. –  Russell Easterly Oct 24 '12 at 21:02
    
I hadn't noticed that you submitted the sequence recently. The short list is then not a good test for the next terms being large. –  Ross Millikan Oct 24 '12 at 21:27
    
I got these terms by hand. I gave up when I found the next term is at least 2^23. I had expected the sequence to grow rapidly, but it does not. If it grows more slowly than 1 / ln n then it would be a good prime sieve. –  Russell Easterly Oct 25 '12 at 16:13

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.