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

[CRGreathouse]

do know a counter example in both ways? p - 2^k and p + 2^k never prime number?

Not at the moment. I checked for very small ones and didn't find any. Finding primes [not] of the form q - 2^k is challenging: I've expended roughly 100 quadrillion processor cycles on the problem in the last year. (I was planning to send the results, almost complete, to Sloane in a week or two.)

Edit: No counterexamples below 36,000.
Edit: No counterexamples below 41,000.

 

[CRGreathouse]

Okay, so the PDF I linked to shows that there are 64 families of residues mod 18446744073709551615 for which any member + 2^k is composite. By Dirichlet's theorem, there are about n/(143890337947975680 log n) primes in these classes up to n.

Members of http://www.research.att.com/~njas/sequences/A065381 seem to have density 1/80 or so (nonproof: look at the scatterplot).

Combining these two, I expect that there are about n/(11511227035838054400 log n) counterexamples to your conjecture from those 64 families alone. There may be many more not in those residue classes. In particular, it seems likely that there is a counterexample before a billion trillion.

 

[al-mahed]

Not at the moment. I checked for very small ones and didn't find any. Finding primes [not] of the form q - 2^k is challenging: I've expended roughly 100 quadrillion processor cycles on the problem in the last year. (I was planning to send the results, almost complete, to Sloane in a week or two.)

Edit: No counterexamples below 36,000.
Edit: No counterexamples below 41,000.

what means No counterexamples below 41,000? 41,000º prime number or number 41,000?

 

[al-mahed]

Okay, so the PDF I linked to shows that there are 64 families of residues mod 18446744073709551615 for which any member + 2^k is composite. By Dirichlet's theorem, there are about n/(143890337947975680 log n) primes in these classes up to n.

Members of http://www.research.att.com/~njas/sequences/A065381 seem to have density 1/80 or so (nonproof: look at the scatterplot).

Combining these two, I expect that there are about n/(11511227035838054400 log n) counterexamples to your conjecture from those 64 families alone. There may be many more not in those residue classes. In particular, it seems likely that there is a counterexample before a billion trillion.

there is a counterexample before a billion trillion of p - 2^k prime numbers form, right? or you're talking about counterexample of both forms? p - 2^k and p + 2^k?

can you make an algorithm to search the counterexamples for both forms? I mean, waht is important is to find first the prime number that cannot be written as p - 2^k and then search below until the prime 3

i.e., supose that you "find" that p + 2^n is composite for all values of n, what means there is no value of n such that p = q - 2^n for q = prime...

now you will test the values for g + 2^k (=p) such that g = prime number (until g = 3) and there is natural k > 0

then should be interesting, if you find such prime number, to see if there is any property for the counterexamples, like: they are twin, palindromic, of the xb + h form, etc, or if it is a totaly random event

as you have the list of some counterexamples for p - 2^k, I ask you if you can plot some of then here, at least the small ones (10 examples, if possible)

 

[CRGreathouse]

there is a counterexample before a billion trillion of p - 2^k prime numbers form, right? or you're talking about counterexample of both forms? p - 2^k and p + 2^k?

Conjecture 1: All odd prime numbers are of the form q + 2^k.
Conjecture 2: All odd prime numbers are of the form q - 2^k.
Conjecture 3: All odd prime numbers are of the form q + 2^k or q - 2^k.

The first counterexample to conjecture 1 is 127. The first *proven* counterexample I know of for the second is 3367034409844073483 (but the first true counterexample may be as small as 2131).

I gave a heuristic argument supporting a counterexample for conjecture 3 below a billion trillion.

can you make an algorithm to search the counterexamples for both forms?

I've been searching for one. It takes a lot of raw computational power. (I could use less by restricting my search, but instead I'm using the data to fill in A094076 so I can send it to Neil Sloane.)

Or rather, I'm searching for non-counterexamples -- showing that the conjecture holds up to certain bounds. I could instead start with known counterexamples to A094076 (all of which are large) and search for ones not of the form q + 2^k; this could find a true (proven) counterexample, but the results would be very large.

then should be interesting, if you find such prime number, to see if there is any property for the counterexamples, like: they are twin, palindromic, of the xb + h form, etc, or if it is a totaly random event

All numbers are of the form xb + h for appropriate x, b, and h. I don't know what you mean by that.

A proven counterexample is unlikely to be a twin prime or a palindrome, since those forms are rare. They are likely to be of 'no special form'.

as you have the list of some counterexamples for p - 2^k, I ask you if you can plot some of then here, at least the small ones (10 examples, if possible)

You should be able to work through my PDF (half a page long) to find all the counterexamples of the form I gave.

But some quick examples (just from one family) are
3367034409844073483
150940986999520486403
261621451441777796093
556769356621130621933
778130285505645241313
1147065166979836273613
1958721906223056544673
2106295858812732957593
2180082835107571164053
2401443763992085783433
3618928872856916190023
4799520493574327493383
5426709792080452248293
6533514436503025345193
7382064663893664719483
9079165118674943468063
9263632559412038984213
9817034881623325532663
10333543715687192977883
12768513933416853791063
13063661838596206616903
13580170672660074062123
14428720900050713436413
14613188340787808952563
15314164615588771913933

(All members of this family end in 3 or 8, and the ones ending in 8 are never prime. Other families have other residues mod 5.)

 

[al-mahed]

All numbers are of the form xb + h for appropriate x, b, and h. I don't know what you mean by that.

A proven counterexample is unlikely to be a twin prime or a palindrome, since those forms are rare. They are likely to be of 'no special form'.

I meant: they are all of the form 2x + 19, or something else... but I think there is no special form as you pointed...

 

[al-mahed]

lets call conjecture this one: All odd prime numbers are of the form q $$\pm$$ 2^k, where q is a prime number

it is more easy

for your program, can you use a previous prime numbers list, and a previous 2^n values list to speed up your calculation?

we are interested in all primes not of the p = q - 2^k, then we should search for the forms q + 2^k, it is more faster, of course, because it is "limited below" when q = 3

ok, so backing to the both lists, each of the members of both lists will be "marked" with the total of bits they have, so you only have to compare the primes and the values of 2^n with total of bits added near to the total of bits of your prime number in question

of course you need a list avaiable of very large primes, is there such list in the sloane research papers?

is this helpfull somehow? or it is a dummy suggestion?

 

[CRGreathouse]

we are interested in all primes not of the p = q - 2^k, then we should search for the forms q + 2^k, it is more faster, of course, because it is "limited below" when q = 3

Good suggestion. I made the same one in post #67.

ok, so backing to the both lists, each of the members of both lists will be "marked" with the total of bits they have, so you only have to compare the primes and the values of 2^n with total of bits added near to the total of bits of your prime number in question

The numbers that are hard are those of the form q - 2^k, for which one must test numbers that are close to a power of 2. For example,
5101 + 2^5760
is 1.6e1730 times 5101, but is within 1.000...0001 times the value of 2^5760.

So the difficulty here is proving many large numbers composite (and one large number prime).

of course you need a list avaiable of very large primes, is there such list in the sloane research papers?

A list of primes large enough to include the above certified prime would require about 1.4e1724 gigabytes. If a super-advanced hard drive can store a billion TB per gram, a hard drive a googol googol googol googol googol googol googol googol googol googol googol googol googol googol googol googol times the weight of the sun couldn't store the list (at 720 bytes per prime).

 

[al-mahed]

A list of primes large enough to include the above certified prime would require about 1.4e1724 gigabytes. If a super-advanced hard drive can store a billion TB per gram, a hard drive a googol googol googol googol googol googol googol googol googol googol googol googol googol googol googol googol times the weight of the sun couldn't store the list (at 720 bytes per prime).

it is amazing what you can find in wallmart these days

but seriously, I was wondering... we don't know yet what will be the use of this conjecture (if its true) to number theory, specially in twin primes conjecture; you said that will be one of the biggest steps towards a proof in one of your first posts, but how? do you have an heuristcs about it? any ideas of an approach to work on?

 

[CRGreathouse]

but seriously, I was wondering... we don't know yet what will be the use of this conjecture (if its true) to number theory, specially in twin primes conjecture; you said that will be one of the biggest steps towards a proof in one of your first posts, but how? do you have an heuristcs about it? any ideas of an approach to work on?

I don't think that the conjecture is true at all, so I'm not inclined to worry about what its consequences might be. Maybe I'll look at the first few posts to see what I might have said about the twin prime conjecture.

Heuristics about what?

 

[CRGreathouse]

OK, what I wrote was this:

Call S the set of primes that can be represented in the form p + 2^k.

The twin prime conjecture (more generally, de Polignac's conjecture or the first Hardy-Littlewood conjecture) implies that S is infinite.

Your original conjecture, in those terms, is that S = P, the set of the primes. We know that this isn't true, since 127 is not in S.

If we call T the set of primes of the form q - 2^k for q prime, then your second conjecture is that T = P. This is also false, since 3367034409844073483 is not in T.

Your third conjecture is that $S\cup T=\mathcal{P}.$ I haven't found a counterexample to this yet, but I don't think it's true.
So since those seem to not hold, I suggested (way back on page 2) a weakening of conjecture 1. Call it conjecture 1A: S is infinite. Even this hasn't been proved (AFAIK), though it would follow from the twin prime conjecture. (There's no reason to doubt this conjecture, but I imagine a proof of this would be very difficult!)

 

[CRGreathouse]

OK, I finally have a counterexample, 84478029997463945033 = n.

n + 2^k is always divisible by one of {2, 3, 5, 17, 257, 641, 65537, 6700417}.

As for n - 2^k, there are only 66 cases to check (since n < 2^67):

n - 2^1 is divisible by 3
n - 2^2 is divisible by 11
n - 2^3 is divisible by 3
n - 2^4 is divisible by 7
n - 2^5 is divisible by 3
n - 2^6 is divisible by 67
n - 2^7 is divisible by 3
n - 2^8 is divisible by 13
n - 2^9 is divisible by 3
n - 2^10 is divisible by 7
n - 2^11 is divisible by 3
n - 2^12 is divisible by 11
n - 2^13 is divisible by 3
n - 2^14 is divisible by 3637
n - 2^15 is divisible by 3
n - 2^16 is divisible by 7
n - 2^17 is divisible by 3
n - 2^18 is divisible by 279494437
n - 2^19 is divisible by 3
n - 2^20 is divisible by 13
n - 2^21 is divisible by 3
n - 2^22 is divisible by 7
n - 2^23 is divisible by 3
n - 2^24 is divisible by 131
n - 2^25 is divisible by 3
n - 2^26 is divisible by 3559
n - 2^27 is divisible by 3
n - 2^28 is divisible by 7
n - 2^29 is divisible by 3
n - 2^30 is divisible by 6359911
n - 2^31 is divisible by 3
n - 2^32 is divisible by 11
n - 2^33 is divisible by 3
n - 2^34 is divisible by 7
n - 2^35 is divisible by 3
n - 2^36 is divisible by 43669
n - 2^37 is divisible by 3
n - 2^38 is divisible by 151
n - 2^39 is divisible by 3
n - 2^40 is divisible by 7
n - 2^41 is divisible by 3
n - 2^42 is divisible by 11
n - 2^43 is divisible by 3
n - 2^44 is divisible by 13
n - 2^45 is divisible by 3
n - 2^46 is divisible by 7
n - 2^47 is divisible by 3
n - 2^48 is divisible by 3049
n - 2^49 is divisible by 3
n - 2^50 is divisible by 103
n - 2^51 is divisible by 3
n - 2^52 is divisible by 7
n - 2^53 is divisible by 3
n - 2^54 is divisible by 163
n - 2^55 is divisible by 3
n - 2^56 is divisible by 13
n - 2^57 is divisible by 3
n - 2^58 is divisible by 7
n - 2^59 is divisible by 3
n - 2^60 is divisible by 214860817
n - 2^61 is divisible by 3
n - 2^62 is divisible by 11
n - 2^63 is divisible by 3
n - 2^64 is divisible by 7
n - 2^65 is divisible by 3
n - 2^66 is divisible by 653

Oh, and n is less than a billion trillion, as expected.

 

[al-mahed]

OK, what I wrote was this:



Your original conjecture, in those terms, is that S = P, the set of the primes. We know that this isn't true, since 127 is not in S.

If we call T the set of primes of the form q - 2^k for q prime, then your second conjecture is that T = P. This is also false, since 3367034409844073483 is not in T.

Your third conjecture is that $S\cup T=\mathcal{P}.$ I haven't found a counterexample to this yet, but I don't think it's true.



So since those seem to not hold, I suggested (way back on page 2) a weakening of conjecture 1. Call it conjecture 1A: S is infinite. Even this hasn't been proved (AFAIK), though it would follow from the twin prime conjecture.

I do believe that S is infinite which ==> twin prime, of course, but its not interesting to find that S is infinite

to find a counterexample for $S\cup T=\mathcal{P}.$ is really pretty much more interesting, but this is beyond my computational skills... it is possible to work with only that PARI program to deal with VERY large prime numbers? like 30 bits numbers?

 

[al-mahed]

OK, I finally have a counterexample, 84478029997463945033 = n.

n + 2^k is always divisible by one of {2, 3, 5, 17, 257, 641, 65537, 6700417}.

As for n - 2^k, there are only 66 cases to check (since n < 2^67):

n - 2^1 is divisible by 3
n - 2^2 is divisible by 11
n - 2^3 is divisible by 3
n - 2^4 is divisible by 7
n - 2^5 is divisible by 3
n - 2^6 is divisible by 67
n - 2^7 is divisible by 3
n - 2^8 is divisible by 13
n - 2^9 is divisible by 3
n - 2^10 is divisible by 7
n - 2^11 is divisible by 3
n - 2^12 is divisible by 11
n - 2^13 is divisible by 3
n - 2^14 is divisible by 3637
n - 2^15 is divisible by 3
n - 2^16 is divisible by 7
n - 2^17 is divisible by 3
n - 2^18 is divisible by 279494437
n - 2^19 is divisible by 3
n - 2^20 is divisible by 13
n - 2^21 is divisible by 3
n - 2^22 is divisible by 7
n - 2^23 is divisible by 3
n - 2^24 is divisible by 131
n - 2^25 is divisible by 3
n - 2^26 is divisible by 3559
n - 2^27 is divisible by 3
n - 2^28 is divisible by 7
n - 2^29 is divisible by 3
n - 2^30 is divisible by 6359911
n - 2^31 is divisible by 3
n - 2^32 is divisible by 11
n - 2^33 is divisible by 3
n - 2^34 is divisible by 7
n - 2^35 is divisible by 3
n - 2^36 is divisible by 43669
n - 2^37 is divisible by 3
n - 2^38 is divisible by 151
n - 2^39 is divisible by 3
n - 2^40 is divisible by 7
n - 2^41 is divisible by 3
n - 2^42 is divisible by 11
n - 2^43 is divisible by 3
n - 2^44 is divisible by 13
n - 2^45 is divisible by 3
n - 2^46 is divisible by 7
n - 2^47 is divisible by 3
n - 2^48 is divisible by 3049
n - 2^49 is divisible by 3
n - 2^50 is divisible by 103
n - 2^51 is divisible by 3
n - 2^52 is divisible by 7
n - 2^53 is divisible by 3
n - 2^54 is divisible by 163
n - 2^55 is divisible by 3
n - 2^56 is divisible by 13
n - 2^57 is divisible by 3
n - 2^58 is divisible by 7
n - 2^59 is divisible by 3
n - 2^60 is divisible by 214860817
n - 2^61 is divisible by 3
n - 2^62 is divisible by 11
n - 2^63 is divisible by 3
n - 2^64 is divisible by 7
n - 2^65 is divisible by 3
n - 2^66 is divisible by 653

Oh, and n is less than a billion trillion, as expected.

nice find! what is interesting is that when k is odd p - 2^k is allways divisible by 3 as the smallest prime number factor, but perhaps this means anything

 

[al-mahed]

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, ...

 

[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]

I do believe that S is infinite which ==> twin prime, of course, but its not interesting to find that S is infinite

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

it is possible to work with only that PARI program to deal with VERY large prime numbers? like 30 bits numbers?

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]

nice find! what is interesting is that when k is odd p - 2^k is allways divisible by 3 as the smallest prime number factor, but perhaps this means anything

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]

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.

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]

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.

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

still not very clear to me

 

[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.