OFFSET
1,1
COMMENTS
We can easily create a k-CNF Boolean IsPrimek() function. Make a list of all composite k-bit binary numbers. Assign each bit to a variable and invert the bits to create a k-clause. Combining these clauses gives us a CNF IsPrimek() function. For example, the 4-clause for 15 (1111 base2) is (~d+~c+~b+~a). The 5-clause for 15 (01111) will be (e+~d+~c+~b+~a). We have to add a variable to the clause for each new power of two until we get to 2^7. 128+15 is composite so we can remove the variable for 128.
This sequence is the list of powers of 2 that can be removed from the CNF clause for 15. I still can't prove this is an infinite sequence. Assume this sequence is finite. Then there exists a finite width prime sieve for powers of two. For every large enough power of two we can find a prime by adding one of the numbers in this sequence (assuming the sequence is finite). The sequence can still be used as a prime sieve even if the sequence is infinite, assuming it grows slowly enough.
CROSSREFS
KEYWORD
nonn,uned
AUTHOR
Russell Easterly, Feb 17 2010
STATUS
approved