# I made the following conjecture

by al-mahed
Tags: conjecture
P: 258
 Quote by CRGreathouse 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?
P: 258
 Quote by 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 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 writen 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)
HW Helper
P: 3,680
 Quote by al-mahed 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.

 Quote by al-mahed 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.

 Quote by al-mahed 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'.

 Quote by al-mahed 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.)
P: 258
 Quote by CRGreathouse 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...
 P: 258 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?
HW Helper
P: 3,680
 Quote by al-mahed 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.

 Quote by al-mahed 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).

 Quote by al-mahed 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).
P: 258
 Quote by CRGreathouse 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 dont 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 aproach to work on?
HW Helper
P: 3,680
 Quote by al-mahed but seriously, I was wondering... we dont 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 aproach 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.

HW Helper
P: 3,680

 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!)
 Sci Advisor HW Helper P: 3,680 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.
P: 258
 Quote by CRGreathouse 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 wich ==> 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?
P: 258
 Quote by 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.
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
 P: 258 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, ...
 P: 258 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?)
HW Helper
P: 3,680
 Quote by al-mahed I do believe that S is infinite wich ==> 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.

 Quote by al-mahed 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.
HW Helper
P: 3,680
 Quote by al-mahed 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.
P: 258
 Quote by 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.
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?
P: 258
 Quote by 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.
you mean as p will never be 3 (must be at least 5 because k > 0)??

still not very clear to me

 Related Discussions Biology 9 Special & General Relativity 0 General Math 4 Linear & Abstract Algebra 9 General Discussion 0