1
$\begingroup$

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.

  • 0
    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.2012-10-25

0 Answers 0