I made the following conjecture

al-mahed

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?)

CRGreathouse

No, twin prime conjecture => S is infinite. A priori, it's possible that S is infinite but the twin prime conjecture fails.

Pari can easily work with numbers up to hundreds of bits. To prove the primality of numbers with thousands of digits, I use Primo instead.

CRGreathouse

The least prime factor of p - 2^k for p > 3 always alternates between 3 and another number. This is true because 3 does not divide p.

al-mahed

my mistake, I changed the order... but this is not important, you made a nice work here, this is all what matters!!!! congrats, CGR4

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

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

al-mahed

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

still not very clear to me

CRGreathouse

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

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

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

Thanks!

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.