|
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.
|
|
0
|
|
|
%I #8 Jul 25 2021 10:52:09
%S 15,143,527,655,1039,1167,1551,1679
%N 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.
%C 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.
%C 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.
%K nonn,uned
%O 1,1
%A _Russell Easterly_, Feb 17 2010
|
