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

  • Thread starter goldust
  • Start date
  • Tags
    Prime
In summary, the new statement is that there is a prime number between 2k and 2k + 2kn for some n, where n must be greater than or equal to 1. The range in the original statement, 2 * n, also changes to 2 * n - 1 when n doubles, and the probability of a prime being located within this range does not change as n increases.
  • #1
goldust
89
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:
 
Mathematics news on Phys.org
  • #2
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
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
arildno said:
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.
 
  • #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:
  • #7
D H said:
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. :smile:
 
  • #8
Checked n = 41.
 
Last edited:
  • #9
It fails for n=54.
$$\begin{aligned}
2^{54}+2 \cdot 54 &= 18014398509482092 \\
\operatorname{NextPrime}(2^{54}) &= 18014398509482143
\end{aligned}$$
 
  • #10
D H said:
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. :biggrin:
 
  • #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:
  • #13
Checked up to 2 ^ 1000. :biggrin:
 
Last edited:
  • #14
Checked what? 54 is a counterexample, the statement isn't true.
 
  • #15
Office_Shredder said:
Checked what? 54 is a counterexample, the statement isn't true.

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:
  • #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?
 
  • #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 ?
 
  • #18
mnb96 said:
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. :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:
  • #19
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
Office_Shredder said:
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)

: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:
  • #21
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.
 
  • #22
D H said:
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.
Cramér's conjecture, not Cramer's conjecture.
 
  • Like
Likes 1 person
  • #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:
  • #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:
  • #25
Last edited:
  • #26
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) [itex]\geq[/itex] how many prime factors n has.

:approve: Now it should be good enough for publication in a journal as an interesting amateur home project.
 
Last edited:
  • #27
Interestingly, it appears that, for any k > 0, the number of primes in the range (2k , 2k + 2 [itex]\times[/itex] k2) [itex]\geq[/itex] k. The difference between 2k + 2 [itex]\times[/itex] k2 and the kth prime above 2k 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 2k.
 
Last edited:
  • #28
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.)
 
  • #29
Robert1986 said:
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. :wink: 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. :cool: 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 [itex]\times[/itex] 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.
 
Last edited:
  • #30
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. :tongue:
 
Last edited:
  • #31
goldust said:
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.
Proof: For k>2, 2k is divisible by 8 and the "range size" (never heard of that before, but I have no idea about number theory) of 9/8 * 2k is 2k(k-1) < 2k2. The number is in your range, as 1<9/8<2.
Between 2k and 2k + 2 k2, 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.
 

1. Is there a specific formula or method to determine if there is a prime between 2^n?

There is no known formula or method to determine if there is a prime between 2^n. This is known as the "Twin Prime Conjecture" and it remains an unsolved problem in mathematics.

2. Can this statement be proven or is it just a hypothesis?

This statement is known as the "Bertrand's Postulate" and it has been proven to be true for all values of n up to 3 x 10^18. However, it has not been proven for all values of n and is still considered a hypothesis.

3. What is the significance of this statement in mathematics?

This statement is significant because it provides insight into the distribution of prime numbers. It suggests that as n increases, the likelihood of finding a prime number also increases.

4. Are there any exceptions to this statement?

There are no known exceptions to this statement. However, it has not been proven for all values of n, so there is a possibility that there may be exceptions.

5. How does this statement relate to other famous unsolved problems in mathematics?

This statement is related to other famous unsolved problems in mathematics such as the Goldbach's Conjecture and the Riemann Hypothesis. These problems all involve the distribution of prime numbers and have not been proven for all values.

Similar threads

Replies
6
Views
785
  • General Math
Replies
23
Views
3K
Replies
35
Views
3K
  • General Math
Replies
5
Views
1K
  • General Math
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
Replies
4
Views
1K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
16
Views
3K
Back
Top