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

1. Nov 8, 2013

goldust

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.

2. Nov 8, 2013

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.

3. Nov 8, 2013

arildno

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.

4. Nov 8, 2013

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.

5. Nov 8, 2013

goldust

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
6. Nov 8, 2013

Staff: Mentor

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

arildno

That's a lot more than my exact nothingness.

8. Nov 8, 2013

goldust

Checked n = 41.

Last edited: Nov 8, 2013
9. Nov 8, 2013

Staff: Mentor

It fails for n=54.
\begin{aligned} 2^{54}+2 \cdot 54 &= 18014398509482092 \\ \operatorname{NextPrime}(2^{54}) &= 18014398509482143 \end{aligned}

10. Nov 8, 2013

goldust

Many thanks. This is a really useful tool.

11. Nov 8, 2013

goldust

Last edited: Nov 9, 2013
12. Nov 9, 2013

goldust

I showed this to my prof, and he was really impressed by it. 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
13. Nov 10, 2013

goldust

Checked up to 2 ^ 1000.

Last edited: Nov 10, 2013
14. Nov 10, 2013

Office_Shredder

Staff Emeritus
Checked what? 54 is a counterexample, the statement isn't true.

15. Nov 10, 2013

goldust

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!

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
16. Nov 10, 2013

goldust

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?

17. Nov 11, 2013

mnb96

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 ?

18. Nov 11, 2013

goldust

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. 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
19. Nov 11, 2013

Office_Shredder

Staff Emeritus
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)

20. Nov 11, 2013

goldust

That's exactly right. n must be more than 1, of course.

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.

Last edited: Nov 11, 2013