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

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

 

[D H]

Why would you think that? 2ⁿ and 2ⁿ+2n get too close to one another in a logarithmic sense as n gets ever larger.

 

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

 

[D H]

I would think that basically your idea is "almost certainly false"

Subtract "almost" and you have it exactly right. It's easy to disprove, and I know next to nothing with regard to number theory.

 

[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?

 

[D H]

Your conjecture fails for n = 54, 55, 62, 65, 85, 99, 100, …

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

 

[arildno]

It's easy to disprove, and I know NEXT to nothing with regard to number theory.

That's a lot more than my exact nothingness.

 

[goldust]

Checked n = 41.

 

[D H]

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

 

[goldust]

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

Many thanks. This is a really useful tool.

 

[goldust]

This is one awesome tool! http://www.wolframalpha.com/input/?i=NextPrime Many thanks for providing the link.

 

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

 

[goldust]

Checked up to 2 ^ 1000.

 

[Office_Shredder]

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

 

[goldust]

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

It's another statement that has a much bigger range.

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}]

 

[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?

 

[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 ?

 

[goldust]

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 ?

The statement has been modified, as per his suggestion. 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.

 

[Office_Shredder]

So is your new claim something like there is a prime number between 2^k and 2^k+2kⁿ for some n? (changing it from a linear range in k to a polynomial in k)

 

[goldust]

So is your new claim something like there is a prime number between 2^k and 2^k+2kⁿ for some n? (changing it from a linear range in k to a polynomial in k)

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.

 

[D H]

Checking with small numbers such as all integers between 2 and 2¹⁰⁴⁰ is no guarantee that your conjecture is true for all numbers. If your new conjecture is that there is a prime between 2^k and 2^k+2*k², that's essentially a variant on Cramer's conjecture. This conjecture has been tested for against much larger numbers than your 2¹⁰⁴⁰ 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.

 

[arildno]

Checking with small numbers such as all integers between 2 and 2¹⁰⁴⁰ is no guarantee that your conjecture is true for all numbers. If your new conjecture is that there is a prime between 2^k and 2^k+2*k², that's essentially a variant on Cramer's conjecture. This conjecture has been tested for against much larger numbers than your 2¹⁰⁴⁰ 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.

Cramér's conjecture, not Cramer's conjecture.

 

[goldust]

My conjecture is that, for any n > 1, there is a prime between n and n + how many prime factors n has \times 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 2^k, the range would be between 2^k and 2^k + 2 k², 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. It's essentially of the same nature as Bertrand's postulate.

It seems to me that the range between 2^k and 2^k + 2 k² 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 = 2¹⁰⁰⁰, 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?

 

[goldust]

Checked with my prof on this. He says it could be considered an original conjecture. 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 2^k, 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.

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 (2^k , 2^{k + 1}) whose range size is less than that of 2^k. The range size of a number n is how many prime factors n has \times the sum of n's prime factors. The range size of 2^k is therefore 2k².

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 2³¹.

 

[goldust]

There is also a Firoozbakht's conjecture, which is of the same nature as Cramér's conjecture.

http://en.wikipedia.org/wiki/Firoozbakht’s_conjecture

Legendre's conjecture and Oppermann's conjecture are of the same nature.

http://en.wikipedia.org/wiki/Legendre's_conjecture

http://en.wikipedia.org/wiki/Oppermann's_conjecture

I suppose my first conjecture is of the same nature as Bertrand's postulate.

http://en.wikipedia.org/wiki/Bertrand's_postulate

 

[goldust]

I formulated my original first conjecture into a weak conjecture and a strong conjecture. The weak one is the same as my original first conjecture. The strong one is that, for any n > 1, the number of primes in the range (n , n + how many prime factors n has × the sum of n's prime factors) \geq how many prime factors n has.

Now it should be good enough for publication in a journal as an interesting amateur home project.

 

[goldust]

Interestingly, it appears that, for any k > 0, the number of primes in the range (2^k , 2^k + 2 \times k²) \geq k. The difference between 2^k + 2 \times k² and the kth prime above 2^k appears to be a non monotonically increasing function of k and that only when k = 1 do these two values equal each other. So far, I've checked up to k = 400 using Mathematica. This is a special case of my strong conjecture when n takes the form of 2^k.

 

[Robert1986]

I don't understand why you would want to publish your problem so that other people can solve it? You came up with the problem; don't let someone else solve your problem for you. Publishing a conjecture in some kind of journal might be nice, but working hard to solve it and then publishing the proof is even better. And, so far, you haven't even worked very long on it (since you only came up with it a few days age.)

 

[goldust]

I don't understand why you would want to publish your problem so that other people can solve it? You came up with the problem; don't let someone else solve your problem for you. Publishing a conjecture in some kind of journal might be nice, but working hard to solve it and then publishing the proof is even better. And, so far, you haven't even worked very long on it (since you only came up with it a few days age.)

If it's so easy to prove, I wouldn't have considered it worthy of being a conjecture. When n is prime, my conjecture reduces to Bertrand's postulate when n is prime. It's what happens when n is composite that makes my conjecture interesting. I won't publish anything unless I'm quite certain it is true.

In increments of a million, I look at how the smallest of the (n + how many prime factors n has \times the sum of n's prime factors) - the (how many prime factors n has)th prime above n values change. I see a non monotonic increasing trend in these values as n gets larger. I haven't tested too many numbers so far, only up to about 28 million, where these values have increased from 1 to about 400. When n is a power of 2, I have tested to 610 as the exponent, and by now I'm quite certain of the non monotonic increasing nature of the difference when n is a power of 2, since the difference has increased from 1 to nearly 500,000.

 

[goldust]

So far, tested my strong conjecture, which is a strengthening of Bertrand's postulate, to 655 million less 1, where the smallest difference has increased from 1 to 527. As for n being powers of 2, so far, tested using Mathematica to the exponent being 700 where the difference has increased from 1 to over 600,000. I have recorded all of my experimental results.

 

[mfb]

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 (2^k , 2^{k + 1}) whose range size is less than that of 2^k. The range size of a number n is how many prime factors n has \times the sum of n's prime factors. The range size of 2^k is therefore 2k².

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 2³¹.

Proof: For k>2, 2^k is divisible by 8 and the "range size" (never heard of that before, but I have no idea about number theory) of 9/8 * 2^k is 2k(k-1) < 2k². The number is in your range, as 1<9/8<2.
Between 2^k and 2^k + 2 k², we expect 2 k/ln(2) primes. Neglecting correlations, the probability of finding a prime is $\displaystyle p(k) \approx 1-\exp\left(-\frac{2k}{ln(2)}\right)$. The product over all k should converge to some finite value, so the non-existence of a small counterexample is a good argument that could be no such gap. It is not a proof, of course.