I made the following conjecture

  • Thread starter al-mahed
  • Start date
  • Tags
    Conjecture
In summary: Plot[PowerOfTwo[n], Region[{1, n}]]In summary, every prime number greater than 3 can be written as a sum of a prime number and a power of two.
  • #1
al-mahed
262
0
Every prime number > 3 could be written as a sum of a prime number and a power of two.

p,q are primes, n is positive whole number ==> p = q + 2^n

5 = 3 + 2^1
7 = 5 + 2^1 = 3 + 2^2
11 = 7 + 2^2
13 = 5 + 2^3
17 = 13 + 2^2
19 = 3 + 2^4
23 = 7 + 2^4
29 = 13 + 2^4
31 = 23 + 2^3
37 = 29 + 2^3

87 = 23 + 2^6
101 = 37 + 2^6

1213 = 701 + 2^9
1217 = 1153 + 2^6
1223 = 967 + 2^8

seems that this is really truth, but fails for some primes (997, 6659 are some primes that this is not true)

I wonder if there is some property which could be used to discriminate such primes
 
Physics news on Phys.org
  • #2
You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.
 
  • #3
CompuChip said:
You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.

how did you figure that out?
 
  • #4
Had a hunch that n might be s.t. 2^n > p.
Then it took just a little trial and error and a Mathematica system.
Probably not too hard to write a program that does it automatically.
 
  • #5
Actually, here is an ugly (but effective) one
Code:
CheckConjecture[n_] := Module[{},
  If[!PrimeQ[n], Print[n, " is not prime"]; Return[]];
  For[i = 0, i <= Sqrt[n], i++, 
   If[n - 2^i // PrimeQ, 
    Print[StringForm["`` = `` + 2^``", n, n - 2^i, i]]; Break[], 
    0
   ]
  ];
 ]
It finds the one for 6659 in less than 0.01 second :smile:
(note, upper boundary is selected somewhat arbitrarily. I think it would be very odd if you happened to plug in a prime for which it even needs to get close).

Here is the result for the first 100 prime numbers
Code:
Composition[CheckConjecture, Prime] /@ Range[1, 100];
3 = 2 + 2^0
5 = 3 + 2^1
7 = 5 + 2^1
11 = 7 + 2^2
13 = 11 + 2^1
17 = 13 + 2^2
19 = 17 + 2^1
23 = 19 + 2^2
29 = 13 + 2^4
31 = 29 + 2^1
37 = 29 + 2^3
41 = 37 + 2^2
43 = 41 + 2^1
47 = 43 + 2^2
53 = 37 + 2^4
59 = 43 + 2^4
61 = 59 + 2^1
67 = 59 + 2^3
71 = 67 + 2^2
73 = 71 + 2^1
79 = 71 + 2^3
83 = 79 + 2^2
89 = 73 + 2^4
97 = 89 + 2^3
101 = 97 + 2^2
103 = 101 + 2^1
107 = 103 + 2^2
109 = 107 + 2^1
113 = 109 + 2^2
131 = 127 + 2^2
137 = 73 + 2^6
139 = 137 + 2^1
149 = -107 + 2^8
151 = 149 + 2^1
157 = 149 + 2^3
163 = 131 + 2^5
167 = 163 + 2^2
173 = 157 + 2^4
179 = 163 + 2^4
181 = 179 + 2^1
191 = 127 + 2^6
193 = 191 + 2^1
197 = 193 + 2^2
199 = 197 + 2^1
211 = 179 + 2^5
223 = 191 + 2^5
227 = 223 + 2^2
229 = 227 + 2^1
233 = 229 + 2^2
239 = 223 + 2^4
241 = 239 + 2^1
251 = -5 + 2^8
257 = 241 + 2^4
263 = 199 + 2^6
269 = 13 + 2^8
271 = 269 + 2^1
277 = 269 + 2^3
281 = 277 + 2^2
283 = 281 + 2^1
293 = 277 + 2^4
307 = 179 + 2^7
311 = 307 + 2^2
313 = 311 + 2^1
317 = 313 + 2^2
331 = -181 + 2^9
347 = 331 + 2^4
349 = 347 + 2^1
353 = 349 + 2^2
359 = 103 + 2^8
367 = 359 + 2^3
373 = -139 + 2^9
379 = 347 + 2^5
383 = 379 + 2^2
389 = 373 + 2^4
397 = 389 + 2^3
401 = 397 + 2^2
409 = 401 + 2^3
419 = 163 + 2^8
421 = 419 + 2^1
431 = 367 + 2^6
433 = 431 + 2^1
439 = 431 + 2^3
443 = 439 + 2^2
449 = 433 + 2^4
457 = 449 + 2^3
461 = 457 + 2^2
463 = 461 + 2^1
467 = 463 + 2^2
479 = 463 + 2^4
487 = 479 + 2^3
491 = 487 + 2^2
499 = 491 + 2^3
503 = 499 + 2^2
509 = -3 + 2^9
521 = 457 + 2^6
523 = 521 + 2^1
541 = 509 + 2^5
and for some arbitrary large ones
Code:
9544791479 = 9544791463 + 2^4
22129347137 = 22129347133 + 2^2
4648194659 = 4648194643 + 2^4
11534533159 = 11400315431 + 2^27
20435808557 = 20435808493 + 2^6
11932479739 = 11932446971 + 2^15
14934903251 = 14934641107 + 2^18
21592521889 = 21592519841 + 2^11
20643758743 = 20643758741 + 2^1
17469583409 = 17468534833 + 2^20
3084406151 = 3017297287 + 2^26
7767771523 = 7767771521 + 2^1
Note how the powers of two hardly increase.
In fact, if you have access to Mathematica yourself, you might find it interesting to plot the powers of two separately:
Code:
PowerOfTwo[n_] := 
 Module[{}, If[! PrimeQ[n], Print[n, " is not prime"]; Return[-1]];
  For[i = 0, i <= Sqrt[n], i++, 
   If[n - 2^i // PrimeQ, Return[i], -1]]]
{Range[1, 5000], Composition[PowerOfTwo, Prime] /@ Range[1, 5000]} // Transpose // ListPlot
(Composition[PowerOfTwo, Prime] /@ Range[1, 10000]) // Tally // ListPlot
 
Last edited:
  • #6
CompuChip said:
You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.

I was thinking on positive whole numbers
 
  • #7
compuchip, could you write an algoritm that expresse a prime as a sum of the minor prime possible and powers of two?

in another words: given the prime 31

we have:

7 = 5 + 2^1 = 3 + 2^2

23 = 7 + 2^4

31 = 23 + 2^3 ==>

==> 31 = 3 + 2^2 + 2^3 + 2^4

my idea was: if a I prove that every single prime could be written as a sum of a prime and a power of 2 (and extract the exacly reason why some of then couldn't), maybe I could derive some properties of the distribution of primes in terms of the power of 2 series

If you generate such list that I am asking for (a prime as the minor prime possible plus some powers of 2), perhaps some interesting pattern in the powers will shows up
 
  • #8
The minor prime possible is always 3 (or 2, if you allow 2^0), since the difference between 3 and the prime (or any positive integer, for that matter) can be expressed (uniquely) as a sum of powers of two; think of its binary representation.
 
  • #9
http://www.research.att.com/~njas/sequences/A065381 [Broken] are those primes that cannot be represented in this way. A list of the first 1000 such primes is here:
http://www.research.att.com/~njas/sequences/b065381.txt [Broken]

See also http://www.research.att.com/~njas/sequences/A078687 [Broken], the number of ways to represent each prime as p + 2^k.
 
Last edited by a moderator:
  • #10
Up to 10 million there are 664,579 primes, of which 102,613 cannot be represented in this way. Up to 50 million there are 4,77,446 primes, of which 477,446 cannot be represented in this way.
 
  • #11
CRg. do you know who was the first to have the same insight?

I was speculating about goldbach's conjeture just for curiosity and this insight came to me, was very nice to see a possible pattern coming out!

Will it be that anybody knows a proof for that?
 
  • #12
Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes
 
Last edited:
  • #13
al-mahed said:
CRg. do you know who was the first to have the same insight?

I was speculating about goldbach's conjeture just for curiosity and this insight came to me, was very nice to see a possible pattern coming out!

Will it be that anybody knows a proof for that?

What insight? What do you want a proof of? I just gave some totals, which are proved by direct computation.

al-mahed said:
Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes

I expect that the number will fluctuate depending on how far the primes are from a power of 2, but the prime number theorem combined with the divergence of the harmonic series suggests that 'most' primes should be represented that way, and that for N(n) = the number of primes < n not representable in the form p + 2^k,
lim N(n)/pi(n) = 0.

What does everyone think? I'm curious about the cardinality of A065381: is it finite?
 
  • #14
I think that you did not see that I had open the thread, I'm saying that I have this insight of represent primes as a prime plus 2^n once when I was studying goldbach's conjeture. Could be not a big deal, but I had this "insight" and now I see that someone had the same insight, I just asked you about more information of that.

Nothing is proved by direct computation, as you know, in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

regards
 
Last edited:
  • #15
al-mahed said:
nothing is proved by direct computation in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

So what insight were you referring to that I had when you said "CRg. do you know who was the first to have the same insight?"?
 
  • #16
I edited, read above, I mean that I have the insight... sorry, my english is not so good...
 
  • #17
Call S the set of primes that can be represented in the form p + 2^k.

al-mahed said:
I'm saying that I have this insight of represent primes as a prime plus 2^n once when I was studying goldbach's conjeture.

It's been studied -- there are half a dozen or so sequences in the OEIS -- but I haven't found any sources beyond those listed in the sequences above.

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

al-mahed said:
Nothing is proved by direct computation, as you know, in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

I do think it might be possible to prove results about the cardinality or cocardinality of the set by direct computation, yes. I don't have a method at the moment, though.
 
Last edited:
  • #18
Ok, cardinality is another thing as you know...

I was just thinking on how to prove that S is infinite... I have a clue... but, infortunally twin primes conjecture ==> S is infinite, not <==, i.e., a proof of the infinity of S do not implies that the twin prime conjecture is true.
 
  • #19
al-mahed said:
I was just thinking on how to prove that S is infinite... I have a clue... but, infortunally twin primes conjecture ==> S is infinite, not <==, i.e., a proof of the infinity of S do not implies that the twin prime conjecture is true.

Of course if your conjecture implied the twin prime conjecture (which it does not, as you pointed out) one might take that as evidence that your conjecture was 'hard', probably too hard to solve. Still, it won't be easy -- a proof of the conjecture that S is infinite might be the biggest step toward a proof of the twin prime conjecture since Chen's theorem 35 years ago.
 
  • #20
You are right, we can see that somehow the two problems are connected !

We may be able to make some progress if we write the primes a little bit different ... can you see how?
 
  • #21
in fact, w don't need to prove that S is infinite, by Dirichlet:

if n, a and b are positive whole numbers, b > 0, gcd(a,b)=1

the arithmetical progression (a + bn) shows infinite primes


so we should write a = p (prime), b = 2 and n = 2^x, and we will know that S is infinite
 
  • #22
OK, here's a heuristic. Take Cramer's model where each number n has a 1/log(n) chance of being prime. Then the expected chance that p-2 is prime is 1/log(p-2), the chance that p-4 is prime is 1/log(p-4), and so on. Estimate each of these probabilities but the last by 1/log(p) because log(p-2^k) is about log(p) when 2^k is small compared to p, and estimate it by 3/log(p) for the last (since you expect that losing the first bit will make a number smaller by a factor of 2 or 4 with roughly equal chance). Estimate the total probability by adding these directly*, which gives (lg (p) + 2) / log(p), which limits toward a constant as p -> infty. Since this constant is large we expect S to be infinite.

* Instead of taking the product of 1 - pr_k for each, hoping that the overlap will be small. It's not, unfortunately, but this still makes the case that S should be large.
 
  • #23
That's not what the theorem says. You can choose a and b, but n just ranges over the integers. You could set a = p, b = 2^k for some k, but that will just show that there are infinitely many primes of the form
p + n * 2^k
which isn't what you want.
 
  • #24
A better heuristic, though one that still needs some work, suggests that in the limit 23.7% of primes cannot be represented in this form and the remainder can be. This uses a slowly-growing function that converges to a power of the limit form of e.
 
  • #25
CRGreathouse said:
That's not what the theorem says. You can choose a and b, but n just ranges over the integers. You could set a = p, b = 2^k for some k, but that will just show that there are infinitely many primes of the form
p + n * 2^k
which isn't what you want.

you right, find a condition to n be 2^x is probably the same problem that I was working on

the problem with probabilities is that we only have evidences in these cases, not a prove, but I will read your message more carefuly at night!

regards
 
  • #26
al-mahed said:
the problem with probabilities is that we only have evidences in these cases, not a prove, but I will read your message more carefuly at night!

More than just evidence, less than a proof: it's a heuristic based on the known distribution of the primes. The Cramer probability that p - 2^k is prime is roughly (slightly more than) 1 - 1/log(p), so the chance that an number has no such form is (1 - 1/log(p))^(lg p) where lg is the binary logarithm.

Actually the Cramer-Maier model would be more appropriate, since we know that the numbers are odd. That would suggest probability (1 - 2/log(p))^(lg p) which limits toward 5.6%.
 
  • #27
consider the set [tex]S = (p_1, p_2, p_3,...p_r | p_i = p_j + 2^{n_k} \forall i,j,k =1,2,3 ...)[/tex] is finite

write N such that [tex]N = p_1*p_2*p_3*...*p_r + 2^x ==> gcd(N,p_i) = 1 \forall i = 1,2,3,...,k[/tex] ==>

==> [tex]N = q_1*q_2*q_3*...*q_s [/tex]


if consider that none of the primes q have the form p + 2^n => contradiction, S is not finite ==> S is infinite

the difficult is that there are primes we cannot write in this form
 
  • #28
a direct proof must show that there are allways at least one q of the form p + 2^n, pretty much more hard to do
 
  • #29
it is very clever in fact, but an absolute proof is our "everest"

CRGreathouse said:
More than just evidence, less than a proof: it's a heuristic based on the known distribution of the primes. The Cramer probability that p - 2^k is prime is roughly (slightly more than) 1 - 1/log(p), so the chance that an number has no such form is (1 - 1/log(p))^(lg p) where lg is the binary logarithm.

Actually the Cramer-Maier model would be more appropriate, since we know that the numbers are odd. That would suggest probability (1 - 2/log(p))^(lg p) which limits toward 5.6%.
 
  • #30
Here's another angle. The infinitude of http://www.research.att.com/~njas/sequences/A057732 [Broken]), would easily prove it.
 
Last edited by a moderator:
  • #31
CRGreathouse said:
Here's another angle. The infinitude of http://www.research.att.com/~njas/sequences/A057732 [Broken]), would easily prove it.

the same cardinality?
 
Last edited by a moderator:
  • #32
I expect that both A057732 and your S are countably infinite, giving them the same cardinality [itex]\aleph_0[/itex].
 
  • #33
I notice another thing:

let S be the set of primes of the form p+2^n

if there are infinite primes of the form p - 2^n must be at least one prime of the form p + 2^n

let p = q - 2^n ==> p +2^n = q - 2^n + 2^n ==> q = p + 2^n ==>

==> for every prime of the form p - 2^n there is a prime of the form p + 2^n

of course this is not a prove that S is infinite, but we have another angle to attack:

if a prime that is not of the form p + 2^n is of the form p - 2^n (we must prove this statement), both sets are infinite because they have the same cardinality
 
  • #34
Call S the set of primes of the form p + 2^k and S' the set of primes of the form p - 2^k.

If S' is infinite and S is finite, then there is some s in S which is of the form p + 2^k for an infinite number of integers k. Since this is impossible (primes are finite, and we're not considering negative numbers prime), if S' is infinite only if S is infinite.
 
  • #35
yes, S' infinite <==> S infinite, but to prove S' infinity seems to be as difficult as the original problem... if we prove that we could put all the primes into these two sets:

1. S is infinite ==> S' is infinite *
2. S' is infinite ==> S is infinite

* S infinity ==> S' infinity because if q = p + 2^n, q > 2^n ==> q - 2^n = p positive
 
Last edited:
<h2>1. What is a conjecture?</h2><p>A conjecture is a statement or idea that is proposed to be true, but has not been proven or verified yet. It is essentially an educated guess or hypothesis in the field of mathematics or science.</p><h2>2. How do you come up with a conjecture?</h2><p>Conjectures can be inspired by observations, patterns, or previous research. They can also be formed through logical reasoning and critical thinking.</p><h2>3. What is the process of proving or disproving a conjecture?</h2><p>The process of proving or disproving a conjecture involves using deductive reasoning and mathematical or scientific methods to gather evidence and reach a conclusion. This may involve conducting experiments, analyzing data, or using logical arguments.</p><h2>4. Can a conjecture ever be proven to be true?</h2><p>Yes, a conjecture can be proven to be true if there is sufficient evidence and logical reasoning to support it. However, there is always the possibility that new evidence or research may disprove it in the future.</p><h2>5. How are conjectures important in the scientific community?</h2><p>Conjectures play a crucial role in the scientific community as they drive research and discovery. They serve as a starting point for further investigation and can lead to the development of new theories and advancements in our understanding of the world.</p>

1. What is a conjecture?

A conjecture is a statement or idea that is proposed to be true, but has not been proven or verified yet. It is essentially an educated guess or hypothesis in the field of mathematics or science.

2. How do you come up with a conjecture?

Conjectures can be inspired by observations, patterns, or previous research. They can also be formed through logical reasoning and critical thinking.

3. What is the process of proving or disproving a conjecture?

The process of proving or disproving a conjecture involves using deductive reasoning and mathematical or scientific methods to gather evidence and reach a conclusion. This may involve conducting experiments, analyzing data, or using logical arguments.

4. Can a conjecture ever be proven to be true?

Yes, a conjecture can be proven to be true if there is sufficient evidence and logical reasoning to support it. However, there is always the possibility that new evidence or research may disprove it in the future.

5. How are conjectures important in the scientific community?

Conjectures play a crucial role in the scientific community as they drive research and discovery. They serve as a starting point for further investigation and can lead to the development of new theories and advancements in our understanding of the world.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
990
  • General Math
Replies
3
Views
529
  • Precalculus Mathematics Homework Help
Replies
3
Views
765
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
914
  • General Math
Replies
24
Views
2K
  • General Discussion
Replies
4
Views
2K
Back
Top