The discussion centers around the conjecture that every prime number greater than 3 can be expressed as the sum of another prime and a power of two, formulated as p = q + 2^n, where p and q are primes and n is a positive integer. Examples provided illustrate this relationship for various primes, although exceptions exist, such as 997 and 6659, which cannot be represented in this form. Participants explore the potential for an algorithm to automate the identification of such representations and discuss the implications of these findings on the distribution of primes. The conversation also touches on the connection to Goldbach's conjecture and the infinite nature of primes that can be expressed in this way. Overall, the thread highlights ongoing curiosity and investigation into the properties of prime numbers and their relationships with powers of two.
#61
al-mahed
262
0
husseinshimal said:
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
I can't remember where we were. Do you mean your original conjecture?
al-mahed said:
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.
Last edited by a moderator:
#64
al-mahed
262
0
CRGreathouse said:
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
Last edited by a moderator:
#65
al-mahed
262
0
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
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.
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.
Last edited by a moderator:
#68
al-mahed
262
0
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
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"?
#70
al-mahed
262
0
CRGreathouse said:
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?
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.
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.
Last edited by a moderator:
#73
al-mahed
262
0
CRGreathouse said:
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?
#74
al-mahed
262
0
CRGreathouse said:
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)
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.
al-mahed said:
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.
al-mahed said:
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'.
al-mahed said:
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.)
Last edited:
#76
al-mahed
262
0
CRGreathouse said:
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...
#77
al-mahed
262
0
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?
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.
al-mahed said:
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).
al-mahed said:
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).
#79
al-mahed
262
0
CRGreathouse said:
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?
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.
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!)
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):
Code:
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.
#83
al-mahed
262
0
CRGreathouse said:
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?
#84
al-mahed
262
0
CRGreathouse said:
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):
Code:
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
#85
al-mahed
262
0
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, ...
Last edited:
#86
al-mahed
262
0
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?)
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.
#89
al-mahed
262
0
CRGreathouse said:
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?
#90
al-mahed
262
0
CRGreathouse said:
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)??
