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

  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. D H

    Staff: Mentor

    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. arildno

    arildno 12,015
    Science Advisor
    Homework Helper
    Gold Member

    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. D H

    Staff: Mentor

    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. 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. D H

    Staff: Mentor

    Last edited: Nov 8, 2013
  8. arildno

    arildno 12,015
    Science Advisor
    Homework Helper
    Gold Member

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

    Staff: Mentor

    It fails for n=54.
    $$\begin{aligned}
    2^{54}+2 \cdot 54 &= 18014398509482092 \\
    \operatorname{NextPrime}(2^{54}) &= 18014398509482143
    \end{aligned}$$
     
  11. Many thanks. This is a really useful tool. :biggrin:
     
  12. Last edited: Nov 9, 2013
  13. 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. Checked up to 2 ^ 1000. :biggrin:
     
    Last edited: Nov 10, 2013
  15. Office_Shredder

    Office_Shredder 4,499
    Staff Emeritus
    Science Advisor
    Gold Member

    Checked what? 54 is a counterexample, the statement isn't true.
     
  16. 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. 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. 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. 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. Office_Shredder

    Office_Shredder 4,499
    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. :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
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted