1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is it really true that, for any n > 0 , there is a prime between 2 ^ n

  1. Nov 8, 2013 #1
    and 2 ^ n + 2 * n? I have checked it for n from 1 to 39. At n = 40, 2 ^ n is over a trillion, and I no longer have the resources to continue checking. I believe this statement is true. As n gets to 40 or more, would this statement become more probable or less probable by the Prime Number Theorem? Much thanks. :biggrin:
     
  2. jcsd
  3. Nov 8, 2013 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Why would you think that? 2n and 2n+2n get too close to one another in a logarithmic sense as n gets ever larger.
     
  4. Nov 8, 2013 #3

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    I would think that basically your idea is "almost certainly false", and it might possibly be directly be disproven in that it would be in direct violation of already proven results concerning, say, prime density as n gets large.

    If it happens to be true, it would be extremely fascinating.

    Mind you, though:
    I don't know anything about number theory, just giving my own initial thoughts on it.
     
  5. Nov 8, 2013 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Subtract "almost" and you have it exactly right. It's easy to disprove, and I know next to nothing with regard to number theory.
     
  6. Nov 8, 2013 #5
    I'm not so sure it would necessarily be false. By the Prime Number Theorem, the proportion of primes under n is approximately 1 / ln (n), which decreases very very slowly as n increases. The range 2 * n increases as n increases, which might be able to compensate for the reduction in the proportion of primes between 2 ^ n and 2 ^ n + 2 * n.

    Anyone by any chance know of a link that gives primes that are over a trillion?
     
    Last edited: Nov 8, 2013
  7. Nov 8, 2013 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Last edited: Nov 8, 2013
  8. Nov 8, 2013 #7

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    That's a lot more than my exact nothingness. :smile:
     
  9. Nov 8, 2013 #8
    Checked n = 41.
     
    Last edited: Nov 8, 2013
  10. Nov 8, 2013 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    It fails for n=54.
    $$\begin{aligned}
    2^{54}+2 \cdot 54 &= 18014398509482092 \\
    \operatorname{NextPrime}(2^{54}) &= 18014398509482143
    \end{aligned}$$
     
  11. Nov 8, 2013 #10
    Many thanks. This is a really useful tool. :biggrin:
     
  12. Nov 8, 2013 #11
    Last edited: Nov 9, 2013
  13. Nov 9, 2013 #12
    I showed this to my prof, and he was really impressed by it. :biggrin: He suggested I use a bigger range. He says he would like to help me publish it in a journal. So far I've checked it up to 2 ^ 450.
     
    Last edited: Nov 10, 2013
  14. Nov 10, 2013 #13
    Checked up to 2 ^ 1000. :biggrin:
     
    Last edited: Nov 10, 2013
  15. Nov 10, 2013 #14

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Checked what? 54 is a counterexample, the statement isn't true.
     
  16. Nov 10, 2013 #15
    It's another statement that has a much bigger range. :tongue2:

    I found it surprising that, as 2 ^ n gets bigger, adding 2 * n to the range does a pretty good job at compensating for the reduction in the probability that any given number is a prime. The probability that a prime is between 2 ^ n and 2 ^ n + 2 * n almost didn't budge as n increased from 50 to nearly 1000. When a number is multiplied by 2, does the Prime Number Theorem state that adding a constant value to the range compensates for the drop in probability that a number is prime? Not a mathematician myself. Any explanation would be greatly appreciated! :smile:

    This is between 2 ^ 51 and 2 ^ 100 http://www.wolframalpha.com/input/?i=Table[NextPrime[2^k]>(2^k+2*k),+{k,51,100}]

    This is between 2 ^ 940 and 2 ^ 950 http://www.wolframalpha.com/input/?i=Table[NextPrime[2^k]>(2^k+2*k),+{k,940,950}]

    This is between 2 ^ 970 and 2 ^ 980 http://www.wolframalpha.com/input/?i=Table[NextPrime[2^k]>(2^k+2*k),+{k,970,980}]
     
    Last edited: Nov 10, 2013
  17. Nov 10, 2013 #16
    I think I kinda figured it out. When the exponent n doubles in 2 ^ n, the probability that a number is prime is halved. For example, when the exponent n increases from 14 to 28, the probability goes from about 0.10 to about 0.05. That means, in order to compensate for the drop in probability, my range has to double when the exponent n in 2 ^ n doubles. Is this correct?
     
  18. Nov 11, 2013 #17
    Your statement, in its current form, is definitely false, and you have been shown many counterexamples that are easy to obtain.

    I am afraid that, unless you modify it, you and your professor are going to have a hard time getting it published.

    Why don't you try to fix it, instead of checking it for bigger and bigger n ?
     
  19. Nov 11, 2013 #18
    The statement has been modified, as per his suggestion. :tongue: The new statement has been tested to 2 ^ 1040.

    In the initial statement, the range was 2 * n. When n = k, the range was 2k. When the exponent n doubles from k to 2k, the range became 2 * (2k) = 4k, which is exactly twice the previous range. At the same time, the probability that any given number under 2 ^ n being prime is halved. Does this mean, by the Prime Number Theorem, the probability that a prime is located in the range of the original statement does not change as the exponent n increases? Not exactly a math wizz myself. :blushing: Still need a bit of help on this.

    It turns out, for any n > 1, the range in the original statement is 2 * n - 1, because the range is exclusive of the two values at the start and the end. When the exponent n doubles, the range more than doubles, though the increase over doubling logarithmically decreases to 0 as n increases.
     
    Last edited: Nov 11, 2013
  20. Nov 11, 2013 #19

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So is your new claim something like there is a prime number between 2k and 2k+2kn for some n? (changing it from a linear range in k to a polynomial in k)
     
  21. Nov 11, 2013 #20
    :approve: That's exactly right. n must be more than 1, of course. :biggrin:

    This time, as the exponent n in 2 ^ n doubles, the probability that any randomly picked number under 2 ^ n is prime halves, and the range more than doubles. Therefore, the statement becomes more probable to being true as n increases.

    So far, 2 ^ 1040 checks out. Would be cool if I can publish this result in a journal as an interesting little project I done, especially considering I'm only 18 years old. :cool:
     
    Last edited: Nov 11, 2013
  22. Nov 11, 2013 #21

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Checking with small numbers such as all integers between 2 and 21040 is no guarantee that your conjecture is true for all numbers. If your new conjecture is that there is a prime between 2k and 2k+2*k2, that's essentially a variant on Cramer's conjecture. This conjecture has been tested for against much larger numbers than your 21040 and it still stands as a conjecture. Checking against a finite subset will never prove a universal statement about an infinite set. Checking can disprove the statement, but it can't prove it.
     
  23. Nov 11, 2013 #22

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Cramér's conjecture, not Cramer's conjecture.
     
  24. Nov 11, 2013 #23
    My conjecture is that, for any n > 1, there is a prime between n and n + how many prime factors n has [itex]\times[/itex] the sum of n's prime factors. When n is prime, the range would be between n and 2n, which has been proven. When n is of the form 2k, the range would be between 2k and 2k + 2 k2, which, as D H pointed out, is a variant on Cramér's conjecture.

    So far, I've checked from 2 to 700,000. It seems more likely to be true as n gets bigger, because the range seems to be growing much faster than the growth of prime gap and seems to exceed the biggest prime gap as a function of n. Not sure if my conjecture could be considered original? I'll have to check with my prof on this one. :tongue: It's essentially of the same nature as Bertrand's postulate.

    It seems to me that the range between 2k and 2k + 2 k2 is sufficiently large to be true, because the range should be able to exceed the biggest prime gap as a function of n by the time n gets big enough. At n = 21000, the range is 1,999,999. Anyone by any chance know how big the biggest known prime gap is?

    If the range as a function of n grows faster than and always exceeds the biggest prime gap as a function of n, wouldn't it be proof that the statement is true?
     
    Last edited: Nov 11, 2013
  25. Nov 12, 2013 #24
    Checked with my prof on this. He says it could be considered an original conjecture. :tongue: However, because I'm still in high school, I can only publish it in a journal. He said my conjecture is fairly interesting in that it sort of unifies Bertrand's postulate (actually a theorem), Cramér's conjecture, and prime factorization. Under the special cases of n being prime and n being of the form 2k, my conjecture reduces to Bertrand's postulate (actually a theorem) and a variation on Cramér's conjecture, respectively. Because my prof is a relative of mine, he says he could pull some strings and there's a good chance it can get published in a particular university journal as an interesting home project. :cool:

    This morning, while thinking over my first conjecture, I came up with a second conjecture, which is closely related to my first conjecture and which could lend more substance to my first conjecture. My second conjecture is that, for any k > 2, there is always a composite number in the range (2k , 2k + 1) whose range size is less than that of 2k. The range size of a number n is how many prime factors n has [itex]\times[/itex] the sum of n's prime factors. The range size of 2k is therefore 2k2.

    So far, I've tested my second conjecture up to k = 30. I would need more than unsigned int to handle powers of 2 over 231.
     
    Last edited: Nov 12, 2013
  26. Nov 12, 2013 #25
    Last edited: Nov 12, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook