Is Every Prime > 3 a Sum of a Prime and a Power of Two?

[CRGreathouse]

there also a kind of pathern to 11 when the values of k goes from +10, +20, +10, +20

and 7 goes from +6, +6, +6, ...

Every tenth one should be divisible by 11 (again, this is true because you're working mod 11 and the order of 2 mod 11 is 10). The ones that look like they're skipped just have other small factors.

 

[CRGreathouse]

you mean as p will never be 3 (must be at least 5 because k > 0)??

still not very clear to me

p is a prime, so 3 doesn't divide p (unless p = 3, but I said p > 3 to exclude that). Thus either 3 divides p - 1 or 3 divides p - 2. But 3 never divides 2^k (obviously), so 2^k is always 1 or 2 mod 3. In fact it alternates, giving you that pattern.

 

[CRGreathouse]

see http://www.research.att.com/~njas/sequences/A067760

a(n) = least positive k such that (2n+1)+2^k is prime.

COMMENT Does a(1065) exist? (Is 2131+2^k composite for all positive k?)

I mentioned A067760 in my PDF already.

In the update I send to Dr. Sloane yesterday, I said that 2131 + 2^k is not prime for 1 <= k <= 1,000,000.

 

[CRGreathouse]

you made a nice work here, this is all what matters! congrats, CGR4

Thanks!

could you state, in a later moment, the exactly densitiy of counterexamples?

you said n/(11511227035838054400 log n) but from where you put 11511227035838054400?

I don't know the exact density of the counterexamples. I made a rough guess (based on working mod 18446744073709551615 and a bunch of other things) about how many counterexamples there would be of one particular form, but I don't know that there aren't others.

The counterexample I found has 20 digits. I guessed that there would be a counterexample of at most 21 digits, which seems pretty good. I checked that there are no counterexamples with less than 5 digits. So the smallest counterexample has 5 to 20 digits.

Direct checking is hard, but will probably show that there are no 5 digit counterexamples. If I continued, I'd probably find a 6 or 7 digit number that I won't be able to easily show to be a counterexample or not a counterexample.