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

[al-mahed]

We know that \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... \ =1, but your sum above seems to converges to 0.16667 or something like that

 

[CRGreathouse]

I was trying to calculate the probability of "a given number be prime" and "be a paticular sum of powers of two plus another power of two". What I meant saying "particular sum of powers of two" is "a fixed sum", for example, 5 = 2^0 + 2^2 is the only sum of powers of two for 5, called "particular sum of powers of two" or "q".

Terminology: I say call 5 = 1 + 4 the unique binary expansion for 5. When you say fixed that makes me wonder what it's fixed in relation to. Are you asking about solutions to n = 1 + 4, where the "5" part above now varies but the "1 + 4" part is fixed? This of course has only one solution, which gives the 1/2^n probability you mentioned -- but what's the point?

Then in the nth-class what is the probability of x = 2^0 + 2^2 + 2^n be a prime number? The probability of x be prime "times" the probability of 2^0 + 2^2 = 5 be combined with an exponent 2^n. But you are right, this last probability is wrong.

Actually I also gave the wrong probability, but it's not important. As long as you can show that there are infinitely many prime p with where p + 2^k is prime for some k, you've proved the result, regardless of how many such k there are for a given p.

This should let us conclude, without any formal proof, that all the elements of a "class" (considering a "class" the set of all elements with the same highest exponent) are a sum of the highest exponent of the class and each of the elements of all the precedents "classes" (but not the first element 2^n itself^{[1]}).

You're saying that the numbers between 2^n and 2^(n+1) are just 2^n plus a number from {0, 1, ..., 2^n}. Sure, that's right... but what of it?

This lead us to ask for the probability of an arrangement of 2-exponents of a prime in the last class, already taking off the greater 2-exponent, be exacly a prime of one of the precedent classes.

I'll admit, I have no idea what you just write here. Let me try to work through it and you can help me, okay?

What you call a k-class I call a (k+1)-bit number. So you're asking for the probability that a (k+1)-bit number, less its most significant bit (2^k), is prime "of one of the precedent classes". The precedent classes would then be those numbers below 2^k. But since the number minus 2^k is always under 2^k, this is just the probability that a (k+1)-bit number, less its most significant bit, is prime.

Alright, I can see how that is relevant. This is the power of two that leaves the smallest remainder when subtracted from the original, making the remaining number most likely to be prime.

More generally, we could ask for the probability of an arrangement of 2-exponents of a prime in the last class be exacly a prime of one of the precedent classes, tanking off ONE of the any 2-exponents (but not 2^0 obviously). This should consider an arrangement inside the class itself.

This is just a restricted version of your original question, not allowing for the possibility of subtracting a power of two not present in the binary expansion of the number.

Why did you use sum instead product?

I was going to ask you why you used the product. The expected number of occurrences of independent events of probability p1, p2, ..., pn is p1 + p2 + ... + pn.

 

[CRGreathouse]

As a first "look" seems to be an strong suggestion indeed! I'll think about something!

Actually you led me to do at least 60 CPU-hours of work on problems related to A094076, so I'm clearly interested. It's a fascinating sequence; its irregularities lead me to wonder about the appropriateness of standard heuristic arguments in this case. But it is surely reasonable to conjecture that there are infinitely many positive members of the sequence, which implies your conjecture.

If I make enough progress on it I'll send Sloane the updates and post them here as well.

 

[al-mahed]

Actually you led me to do at least 60 CPU-hours of work on problems related to A094076, so I'm clearly interested. It's a fascinating sequence; its irregularities lead me to wonder about the appropriateness of standard heuristic arguments in this case. But it is surely reasonable to conjecture that there are infinitely many positive members of the sequence, which implies your conjecture.

If I make enough progress on it I'll send Sloane the updates and post them here as well.

You are trully making efforts to find a solution! I am spending my time to find some kind of proof, or at least to find another implication between the infinity of p +- 2^n set (called S here) and the twin prime conjecture (we know that the twin prime conjecture ==> infinity of S, but what about a necessary condition "<=="; find it and we prove twin prime conj. proving the infinity of S)

I'll make a comment about another observation of mine that involves twin prime conjecture.

In order to find an appropriate heuristic argument could be more prolific if we work in the same particular direction, because there are a lot of possibilities.

 

[al-mahed]

Terminology: I say call 5 = 1 + 4 the unique binary expansion for 5. When you say fixed that makes me wonder what it's fixed in relation to. Are you asking about solutions to n = 1 + 4, where the "5" part above now varies but the "1 + 4" part is fixed? This of course has only one solution, which gives the 1/2^n probability you mentioned -- but what's the point?

No, I am asking about the "1+4" part is fixed and the 2^n part varies.

You're saying that the numbers between 2^n and 2^(n+1) are just 2^n plus a number from {0, 1, ..., 2^n}. Sure, that's right... but what of it?

I am trying to state some things without any doubt, even the obvious one. I think that write all the numbers in the binary form (actually I'm not really using another numerical base) should help to see my arguments more cleary.

I'll admit, I have no idea what you just write here. Let me try to work through it and you can help me, okay??

In fact, I suck in english and also in probabilities (my bigger weakness), as you can see!

What you call a k-class I call a (k+1)-bit number. So you're asking for the probability that a (k+1)-bit number, less its most significant bit (2^k), is prime "of one of the precedent classes". The precedent classes would then be those numbers below 2^k. But since the number minus 2^k is always under 2^k, this is just the probability that a (k+1)-bit number, less its most significant bit, is prime.

Exactly, you stated accurately. And if we consider the number less any bit (2^g, here g < k, or the most significant bit 2^k itself) we are including the k-class, or the (k+1)-bit numbers, in our calculation, i.e., we are seeking for "matches" in the same class.

About your last statement I am not sure (actually I don't know) if the probability of "a (k+1)-bit number, less its most significant bit, is prime" is the same probability of 1/ln[(k)-bit] be prime, but I think this is not relevant here.

Alright, I can see how that is relevant. This is the power of two that leaves the smallest remainder when subtracted from the original, making the remaining number most likely to be prime.

Actually I did not think about this in these terms, I was thinking in terms of increasing the possibilities of find another prime number using the binary expansion of an any prime number.

This is just a restricted version of your original question, not allowing for the possibility of subtracting a power of two not present in the binary expansion of the number.

Lets call p = q +- 2^n, p,q are prime numbers, a "match". I was trying to say that if we consider the k-class itself, not only the precedent classes, this is a little bit more general.

The question remains the same at its most general case: given a prime number p (which has an unique binary expansion, like all the other integer numbers), we ask for the possibilities of find a prime number q "inside" its binary expansion such that p = q +-2^n.

What I am asking you to consider is to look for the probability of making "matches" looking at the binary expansion of the other prime numbers discriminated in classes, i.e, another angle to see these possibilities, because we know that in the last class all the precedent prime numbers binary expansions shows up. I know this is a little obscure to you because of my bad english, it's already difficult to explain in my own language, but I'll try to be more intelligible to you with some examples!

Note that somehow, adding and deducting exponets must cover a portion of the adjacent classes. Let's see 2 classes considering only the odd numbers:

First:

5 = 2^0 + 2^2
<br /> 7 = 2^0 + 2^1 + 2^2


Second:

9 = 2^0 + 2^3
<br /> 11 = 2^0 + 2^1 + 2^3
<br /> 13 = 2^0 + 2^2 + 2^3
<br /> 15 = 2^0 + 2^1 + 2^2 + 2^3


First of all I would like to comment an obvious relation:

2^{n+1} + 2^n = 2^n

How many odd numbers could be represented by, for example, 5 + 2^n in the following class?

The prime number 5 has 1 significant (excluding 2^0, because if we add or deduct 2^0=1 of an odd number we must find an even number, and this is not important for what we want) binary part (or 2-exponent) 2^2, so we should ask for the probability of 2^0+2^2+2^3-2^3 or 2^0+2^2+2^2-2^2\ = 2^0+2^3-2^2, whose "binary elements" that represents an odd number in the folloing class are 2^0+2^2+2^3 and 2^0 + 2^3 respectively, are = p - 2^x, where p is prime.

Prime number that has only one significant bit should make a "match" with no more than 2 odd numbers in the following class.

Prime numbers that has 2 significant bits are in one of these cases:

Let p = 2^0+2^a+2^b be this prime ==> p = 2^0+2^a+2^b+2^c-2^c, and x = b+1 exponent of the following class, then:

1)c=x>b ==> p = 2^0+2^a+2^b+2^x-2^x,

2)c=b ==> p = 2^0+2^a+2^{b+1}-2^b = p = 2^0+2^a+2^x-2^b

3) c=a<b, and b+1=a ==> p = 2^0+2^{a+1}+2^b-2^a = p = 2^0+2^b+2^b-2^a = p = 2^0+2^x-2^a

if c=a<b, but b+1>a, then the third case is not possible.

Prime numbers with 1 significant bit could find 2 odd numbers as a "match" in the following class.

Prime numbers with 2 significant bits could find 2 odd numbers as a "match" in the following class, and 3 if and only if the difference of the exponents of the 2 significant bits = 1.

Prime numbers with 3 significant bits could find 2 odd numbers as a "match" in the following class, 3 if and only if the difference of the exponents of the last 2 significant bits = 1, and 4 if and only if the difference of a bit and the following bit = 1 for all.

The maximum number of "matches" for a prime number in the following class = number of bits of the prime + 1.

Which is the relevance of this? I was thinking on estimate the probability of the amount of primes in the precedent class cover any prime of the following class, obviously considering the amount of primes of the following class. But the difficulty here is that 2 or more primes in the precedent class could be exactly the same prime in the following class, reducing the possibilities in the following class (in fact we can see this happening when we evidence that a given prime has more that one way to be written as a sum of a prime and a power of two).

Restrict this "method" only to adjacent "classes" is obviously the worst case possible, because we cannot work with "matches" in the same "class" and from non-adjacent "classes" neither.

I was going to ask you why you used the product. The expected number of occurrences of independent events of probability p1, p2, ..., pn is p1 + p2 + ... + pn.

Because I think they are not independent, p is only a prime number if p - 2^n, for an any n, is a prime number to, according to our definition. But you must be aware that I really never dedicated myself to study probabilities. I'll improve myself on this topic.

 

[al-mahed]

I noticed that the amount of numbers with k-terms in a "class" is given by the coefficients of the paschal triangle (or Newton's binomial) as shown below:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

Where:
the first line is the class 2^0 with 2^0 = 1 element
the second line is the class 2^1 with 2^1 = 1 + 1 =2 elements
the third line is the class 2^2 with 2^2 = 1 + 2 + 1 = 4 elements
the fourth line is the class 2^3 with 2^3 = 1 + 3 + 3 + 1 =8 elements
and so on...

The subgroups inside the class, whose amount of elements are the coefficients of the binomial expansion, contains only numbers with the same total of terms (or what you call bits; for instance, 2^0 + 2^3 + 2^8 = 3-terms number). Let us call "x-number" the number which represents the coefficient in the paschal triangle. So, the first column of a line is a subgroup with x-numbers having one term (in fact, every first column subgroup is always an 1-term number and x = 1), the second column of a line is a subgroup with x-numbers having 2 terms, the third column of a line is a subgroup with x-numbers having 3 terms, and so on...

For instance, the fourth line "1 4 6 4 1", representing the 2^3= 3th-class, must be read in this fashion: one number having one term, four numbers having two terms, six numbers having three terms, four numbers having four terms, and one number having five terms.

Now, we want to calculate the probability of an any prime number, like 5, beeing "inside" the binary expansion of another prime number such that p = 5 + 2^n for any n. As 5 has 2 terms (2^0 and 2^2), obviously we are interested in the subgroups of the following classes whose numbers has exactly 3 terms.

Looking at the triangle again, the subgroup of 5 is in red, so we are interested in the subgroups in blue:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

Now we can ask for the probabilities in these terms: what is the probability of a prime number "q" in the precedent class be another prime number "p" in the following class such that the first prime number is "inside" the binary expansion of the other prime number such that p = q + 2^n such that n is the most significant bit of the following class?

If q = 5, the probability (P_1) of a number be inside the subgroup with 3 numbers in the 3th-class is = \frac{3}{2^3}, the probability (P_2) of one of the three numbers in this subgroup has 5 as a number "inside" its binary expansion is = \frac{1}{3}, and the probability (P_3) of this number in this subgroup be a prime number is = \frac{1}{ln(2)}*(\frac{n-1}{n^2+n}) = \frac{1}{ln(2)}*(\frac{1}{6}) in this case.

This lead us to conclude that the probability of a prime number with k-terms in the nth-class be equal to a prime number with (k-1)-terms of the precedent class plus a power of two is = (P_1)*(P_2)*(P_3) = \frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n} as I said before.

But now I see, as you said, that the probability of a prime number "q" in the precedent class be another prime number "p" in the following class such that the first prime number is "inside" the binary expansion of another prime number such that p = q + 2^n for an any n (n beeing the most significant bit of an any class) is the addition of the probabilities in each increasing class. Call P this probability, then:

P = \frac{1}{ln(2)}*\left\{\frac{n_1-1}{(n_1^2+n_1)*2^{n_1}} + \frac{n_2-1}{(n_2^2+n_2)*2^{n_2}} + \frac{n_3-1}{(n_3^2+n_3)*2^{n_3}} + \cdots \right\} which I think clearly converges to a small real number

This is the worse case, because we are working with primes of the form p + 2^n when p - 2^n seems to be more abundant. We are considering only relations between adjacent classes, when there are "matches" in the same class (i.e. p and q are in the same class and the relation p = q +-2^n holds).

I need to generalize these heuristics for all cases, and I'm sure that the result will be interesting.

 

[al-mahed]

I committed an error of typewriting on post #55.

Where are written the follow:

"First of all I would like to comment an obvious relation:

2^{n+1} + 2^n = 2^n"

please read the follow:

"First of all I would like to comment an obvious relation:

2^{n+1} - 2^n = 2^n"

 

[al-mahed]

A remarkable heuristics from the particular case of 5 given above is:

given the paschal triangle

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

such that the diagonal line in blue represents the waited sub-groups of the "classes" where the prime numbers of the form 5 + 2^n will be found

lets think about the following argument: if all primes of a certain "class" always will be in the sub-group represented for this line in blue this certainly strengthen the hypothesis of that there are infinitely many prime numbers of the form 5 + 2^n

this hypothesis is strongly unlikely since the probability of "m" prime numbers beeing all inside the same subgroup with \left(^{n}_{k}\righ) elements is \prod^{\infty}_{n=2}\frac{\left(^{n}_{k}\righ)}{2^{n+m}} where m = \frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n}) and k is the column of the "class", which diverges to zero when n becomes bigger.

this let us to conclude that it is extremely probable that there is a prime number out of these sub-groups for at least one of the "classes" represented by the diagonal line in blue.

lets point its sub-group in green

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

now I can give the same argument for this new prime number such which I gave for number 5, that is, I want to calculate the probability of the subgroups represented below in orange having inside a prime number such that the prime number in the green subgroup plus an any power of two 2^n represents another prime number in an any nth-class.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

And I can extend the same argument to this orange line as I did to the blue line (that is pretty much unlikely that all primes shall be inside the subgroups of one of these two diagonals lines, blue and orange), and so on^{[1]}... If I consider that an any prime number could "appear" in an any "class" such that its subgroup is a subgroup on the left of a "line of probability" (a diagonal line of another prime number), this possibility should strengthen the conjecture "there are infinitely many primes of the form p+2^n". This is shown in pink as follows:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

[1]someone could affirm: you are considering that there is to few diagonal lines in order that the probability of the event "all the existing prime numbers shall be lying into one of these sub-groups, of these diagonal lines" will be very small; and the answer is: if I decrease the probability of there is a prime number out of these sub-groups for at least one of the 'classes' represented by the diagonal line of an any number the number of another diagonal lines will be increased in such hypothesis, so the result will be the same in both directions.

Then I think that statistically speaking the conjecture is proved by these arguments, or other similar arguments!

 

[al-mahed]

the probability of "m" prime numbers beeing all inside the same subgroup with \left(^{n}_{k}\righ) elements is \prod^{\infty}_{n=2}\frac{\left(^{n}_{k}\righ)}{2^{n+m}} where m = \frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n}) and k is the column of the "class", which diverges to zero when n becomes bigger.

This is wrong, I made a mistake in the calculation, in fact the probability is


\prod^{\infty}_{n=2}\frac{\left(^{n}_{k}\righ)}{2^n}*\frac{1}{ln(2)}*(\frac{n-1}{n^2+n}) \approx \prod^{\infty}_{n=2}\frac{\left(^{n}_{k}\righ)}{n*2^n*ln(2)} which diverges to zero when n becomes bigger also

 

[husseinshimal]

wrong example

dear sir,in your post you gave awrong example,namely87.it is no prime number.i would like to refere that some times it worthless to search about how to express prime numbers?

 

[al-mahed]

dear sir,in your post you gave awrong example,namely87.it is no prime number.i would like to refere that some times it worthless to search about how to express prime numbers?

You're right, 87 = 3*29, but in fact this simple wrong example doesn't change anything about the further discussion

 

[al-mahed]

is there any news about it?

 

[CRGreathouse]

is there any news about it?

I can't remember where we were. Do you mean your original conjecture?

Every prime number > 3 could be written as a sum of a prime number and a power of two.

As I commented on http://www.research.att.com/~njas/sequences/A094076 (see my PDF there), 2^k + 3367034409844073483 is composite for all natural numbers k, even though 3367034409844073483 is prime. So the conjecture fails.

 

[al-mahed]

I can't remember where we were. Do you mean your original conjecture?



As I commented on http://www.research.att.com/~njas/sequences/A094076 (see my PDF there), 2^k + 3367034409844073483 is composite for all natural numbers k, even though 3367034409844073483 is prime. So the conjecture fails.

but p = 3367034409844073483 - 2^60 (=1152921504606850000) is a prime number

 

[al-mahed]

the original conjecture is: all prime numbers can be expressed as q + 2^k, q is prime

but there are some gaps, like 997 and 6659 (997 and 6659 must be expressed as q - 2^k)

so the second form of conjecture is: all prime numbers can be expressed as q - 2^k, q is prime

what you found? you found that for a particular prime there are no prime numbers such that p = 2^k + 3367034409844073483 is prime, for all natural k

wich means 3367034409844073483 cannot be expressed as q - 2^k

but as 3367034409844073483 can be expressed as q + 2^60 this is not a counter example of both conjecture forms

I used excel and the program primo 3.0.6, I don't know if excel did a mistake in calculating the corret value for 2^60 = 1152921504606850000

3367034409844073483 is a gap of the second conjecture form

 

[CompuChip]

I used excel and the program primo 3.0.6, I don't know if excel did a mistake in calculating the corret value for 2^60 = 1152921504606850000

3367034409844073483 is a gap of the second conjecture form

2^60 = 1152921504606846976
Don't trust programs like Excel for doing math

3367034409844073483 can be written in the form prime + 2^n in two ways: 2^10 + 3367034409844072459 or 2^30 + 3367034408770331659
However, 3367034409844073483 - 2^60 is not prime, it is 137 x 16161408067425011.

 

[CRGreathouse]

the original conjecture is: all prime numbers can be expressed as q + 2^k, q is prime

but there are some gaps, like 997 and 6659 (997 and 6659 must be expressed as q - 2^k)

so the second form of conjecture is: all prime numbers can be expressed as q - 2^k, q is prime

So your actual conjecture is that for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime. Is that right?

In that case it suffices to show that all members of http://www.research.att.com/~njas/sequences/A065381 (alas, not currently accessible; let me look it up tomorrow) which I can use to find the first small example not known to work.

 

[al-mahed]

CompuCHIP:

:) all right, I don't have the best programs as you and Charles, so I must trust in excel and other bullCH... sorry for my 5rd world resources

CGR:

Nice to talk with you again! it is nice to see that I am still the most iluded amatheur EVER :)... in fact I am back to "paper" since my last post here, I have a complicated life... one year and 30 years old, now we have almost the same cardinality kkkkkk

well, let's see... seems that U show with some "formal" math in your sloane pdf some stuff we discuss here before, like that "classes" chat... in fact you did pretty much more if you are right in your counter example... I really cannot follow you at the moment, I mean, analyse your arguments (need to study again the elementary number theory)...

but I noticed that compuchip did show that your pdf is wrong because 3367034409844072459 is prime number

 

[CRGreathouse]

:) all right, I don't have the best programs as you and Charles, so I must trust in excel and other bullCH... sorry for my 5rd world resources

Might I recommend Pari/GP? You can download it from here:
http://pari.math.u-bordeaux.fr/download.html

but I noticed that compuchip did show that your pdf is wrong because 3367034409844072459 is prime number

No. My PDF showed that 3367034409844073483 + 2^k is never prime, and it isn't. My paper didn't show anything about 3367034409844073483 - 2^k.

And I repeat my question to you. Is your full, final conjecture "for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime"?

 

[al-mahed]

And I repeat my question to you. Is your full, final conjecture "for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime"?

yes.

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

 

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