8

I know that there exists a prime between $n$ and $2n$ for all $2\leq n \in \mathbb{N}$ . Which number is the fourth number that has just one prime in its gap? First three numbers are $2$ , $3$ and $5$ . I checked with computer until $15000$ and couldn't find next one. Maybe, you can prove that there is no other number with this condition?

Also, when I say, a number $n$ has one prime in its gap it means the set $X = \{x: x$ is prime and $n<x<2n\}$ has only one element.

Thanks for any help.

aeyalcinoglu
  • 534
  • Why such a low limit on your test? What prime-testing algorithm are you using? Are you counting $2 < 3 <4$ or $3 < 5 < 6$ as the first two examples? – abiessu Aug 13 '13 at 19:44
  • @abiessu: I'm using a good "is_prime" function and testing numbers between $n$ and $2n$. I think this is not a good algorithm, can you recommend something? Also, yes I'm counting, I said $2$ , $3$ and $5$ are first three examples. – aeyalcinoglu Aug 13 '13 at 19:47
  • 2
    Try to estimate $|X|=\pi(2n)-\pi(n)$ with the prime number theorem. This strongly suggests, that it is very unlikely, that there are only few primes in this gap for large $n$. – Tomas Aug 13 '13 at 19:49
  • 2
    Why do you think there is another such number? This particular result is actually a very very crude result, which is why it was remarkable that it was so hard to prove... – Thomas Andrews Aug 13 '13 at 19:49
  • 2
    @ThomasAndrews: I don't think that. – aeyalcinoglu Aug 13 '13 at 19:51
  • 1
    It just seems to me that only testing ~10000 so far means there is a slow algorithm involved. Are you incrementing $n$ or finding each successive prime in your test? I think if you build a test where $n=p_{k-1}$ and you find $p_k$ and then search for $p_{k+1}$, you can search faster. – abiessu Aug 13 '13 at 19:52
  • 1
    When you say, "which number is the fourth..." that indicates you think there is another. If you asked, "Does there exist a fourth number, and if so, can we find it?" then we'd understand that you've considered the possibility that it doesn't exist. Questions communicate what you know and what you don't know. – Thomas Andrews Aug 13 '13 at 19:52

2 Answers2

29

There is no other such $n$.

For instance,

In 1952, Jitsuro Nagura proved that for $n ≥ 25$, there is always a prime between $n$ and $(1 + 1/5)n$.

This immediately means that for $n \ge 25$, we have one prime between $n$ and $\frac{6}{5}n$, and another prime between $\frac{6}{5}n$ and $\frac65\frac65n = \frac{36}{25}n < 2n$. In fact, $\left(\frac{6}{5}\right)^3 < 2$ as well, so we can be sure that for $n \ge 25$, there are at least three primes between $n$ and $2n$. As you have already checked all $n$ up to $25$ (and more) and found only $2$, $3$, $5$, we can be sure that these are the only ones.

The number of primes between $n$ and $2n$ only gets larger as $n$ increases: it follows from the prime-number theorem that $$ \lim_{n \to \infty} \frac{\pi(2n) - \pi(n)}{n/\log n} = 2 - 1 = 1,$$ so the number of primes between $n$ and $2n$, which is $\pi(2n) - \pi(n)$, is actually asymptotic to $\frac{n}{\log n}$ which gets arbitrarily large.

Glorfindel
  • 3,955
ShreevatsaR
  • 41,374
5

There is a nice and rather easy proof of Bertrand's postulate (due to Erdős), which can be found here for example. At some point in the proof, one obtains: $$4^{\frac{1}{3}n}\leq (2n)^{\sqrt{2n}+1}\cdot\prod_{n<p<2n}p$$ To prove Betrand's postulate, one would assume to the contrary, that this product is empty and conclude a contradiction for $n$ large enough.

But, more precise: $$\prod_{n<p<2n}p\geq \frac{4^{\frac{1}{3}n}}{(2n)^{\sqrt{2n}+1}}\quad\Rightarrow\quad|X|\geq \log_{2n}\left(\frac{4^{\frac{1}{3}n}}{(2n)^{\sqrt{2n}+1}}\right)$$ I leave further simplifications to you. I am sure, that you can show, that this is bigger than $2$ for $n$ large enough.

Tomas
  • 4,534