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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have played around with deriving a Boolean IsPrime function.

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, ... 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|cite|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


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

Browse other questions tagged or ask your own question.