A173406 This sequence starts with any odd, composite number, like 15. There exists a power of two such that every 2^n + s_i is composite, where s_i is a term in the sequence less than 2^n. For example, 128+15=143, 512+15=527, 512+143=655, etc.

15, 143, 527, 655, 1039, 1167, 1551, 1679

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.

Links

Table of n, a(n) for n=1..8.

Crossrefs

Sequence in context: A179524 A235864 A177065 * A291619 A071700 A133126

Adjacent sequences: A173403 A173404 A173405 * A173407 A173408 A173409

Keyword

nonn,uned

Author

Russell Easterly, Feb 17 2010

Status

approved