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
 Blog Entries: 5 Recognitions: Homework Help Science Advisor 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.

 Quote by 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.
how did you figure that out?

Blog Entries: 5
Recognitions:
Homework Help

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.
 Blog Entries: 5 Recognitions: Homework Help Science Advisor 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 (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

 Quote by 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.
I was thinking on positive whole numbers
 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
 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.
 Recognitions: Homework Help Science Advisor A065381 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 See also A078687, the number of ways to represent each prime as p + 2^k.
 Recognitions: Homework Help Science Advisor 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.
 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?
 Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes

Recognitions:
Homework Help
 Quote by 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?
What insight? What do you want a proof of? I just gave some totals, which are proved by direct computation.

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

Recognitions:
Homework Help
 Quote by al-mahed 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?"?
 I edited, read above, I mean that I have the insight... sorry, my english is not so good...

Recognitions:
Homework Help