# I made the following conjecture

1. Dec 17, 2007

### al-mahed

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

2. Dec 17, 2007

### CompuChip

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. Dec 17, 2007

### ice109

how did you figure that out?

4. Dec 17, 2007

### CompuChip

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. Dec 17, 2007

### CompuChip

Actually, here is an ugly (but effective) one
Code (Text):

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
(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 (Text):
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 (Text):

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 (Text):
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: Dec 17, 2007
6. Dec 17, 2007

### al-mahed

I was thinking on positive whole numbers

7. Dec 17, 2007

### al-mahed

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. Dec 17, 2007

### dodo

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. Dec 17, 2007

### CRGreathouse

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: May 3, 2017
10. Dec 17, 2007

### CRGreathouse

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. Dec 17, 2007

### al-mahed

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. Dec 17, 2007

### al-mahed

Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes

Last edited: Dec 17, 2007
13. Dec 18, 2007

### CRGreathouse

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

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. Dec 18, 2007

### al-mahed

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: Dec 18, 2007
15. Dec 18, 2007

### CRGreathouse

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. Dec 18, 2007

### al-mahed

I edited, read above, I mean that I have the insight... sorry, my english is not so good...

17. Dec 19, 2007

### CRGreathouse

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

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.

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: Dec 19, 2007
18. Dec 19, 2007

### al-mahed

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. Dec 19, 2007

### CRGreathouse

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. Dec 19, 2007

### al-mahed

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?