Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I made the following conjecture

  1. Dec 17, 2007 #1
    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. jcsd
  3. Dec 17, 2007 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Dec 17, 2007 #3
    how did you figure that out?
     
  5. Dec 17, 2007 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

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

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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 :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 (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
  7. Dec 17, 2007 #6
    I was thinking on positive whole numbers
     
  8. Dec 17, 2007 #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
     
  9. Dec 17, 2007 #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.
     
  10. Dec 17, 2007 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Last edited: Dec 17, 2007
  11. Dec 17, 2007 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Dec 17, 2007 #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?
     
  13. Dec 17, 2007 #12
    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
  14. Dec 18, 2007 #13

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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?"?
     
  17. Dec 18, 2007 #16
    I edited, read above, I mean that I have the insight... sorry, my english is not so good...
     
  18. Dec 19, 2007 #17

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  21. Dec 19, 2007 #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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: I made the following conjecture
  1. Collatz Conjecture (Replies: 9)

  2. Goldbach conjecture (Replies: 7)

Loading...