4

Is there is metric to know how far we are from the nearest prime number. For example if my number is 38, then we are 3 numbers away from 41?

If such a metric doesn't exist, is there an upper bound saying that we must find a prime number before (say) the next 300 numbers?

hardmath
  • 37,015
TheChetan
  • 199
  • 3
    Do you mean the "nearest" prime number, or the "next" prime number? I ask because $37$ is closer to $38$ than $41$ is. – G Tony Jacobs May 18 '16 at 17:40
  • 5
    There is no global upper bound. For example, the numbers $n! + 2, \ldots, n! + n$ are $n - 1$ consecutive composite numbers, and obviously we can choose $n$ to make $n - 1$ as large as we want. – Travis Willse May 18 '16 at 17:41
  • 1
    For large numbers, the nearest prime is very difficult to determine. And from some magnitude on, it is not feasible in practice. For example, for $10^{10^{100}}$ – Peter May 18 '16 at 17:42
  • There are bounds on how far away the next prime number can be, but these are not "sharp" bounds as normally formulated (i.e. they give a range, not the exact next prime). – hardmath May 18 '16 at 17:42
  • @GTonyJacobs, The next one. (But I would be interested in the other case as well) – TheChetan May 18 '16 at 17:42
  • 3
    We know the average distance, but getting firm limits has proved difficult. There has been no radical improvement on Bertrand's postulate as far as I know. – almagest May 18 '16 at 17:43
  • 1
    @almagest: Bertrand's postulate has been vastly improved upon. Google for prime gaps upper bound. – hardmath May 18 '16 at 17:45
  • http://arxiv.org/abs/1410.1083 – Count Iblis May 18 '16 at 17:50
  • 1
    @hardmath These are bounds that hold for all sufficiently large $N$. That is interesting theoretically, but not the same as a Bertrand-type bound. – almagest May 18 '16 at 17:55

1 Answers1

8

For concrete bounds on prime gaps that improve upon "Bertrand's postulate", which (in a slightly weakened form) states:

$$ \forall n \ge 3 \;\exists p \text{, a prime s.t. } n < p < 2n $$

see a brief summary on the Prime Pages. In particular:

$$ \forall n \ge n_0 \;\exists p \text{, a prime s.t. } n < p < (1+\epsilon) n $$

holds for $\epsilon = 1/16597$ and $n_0 = 2010760$, proved by Schoenfeld in 1976. The citation given is to P. Ribenboim's The new book of prime number records, 3rd edition (Springer-Verlag, 1995). This has surely been improved upon as far as reducing $\epsilon \gt 0$.

Added: Pierre Dusart has proven concrete bounds of the form:

$$ \forall n \ge n_0 \;\exists p \text{, a prime s.t. } n < p < (1+e(n)) n $$

where $e(n)$ tends to zero as $n\to \infty$. In this arXiv.org paper from 2010 he shows that we can take $n_0 = 396738$ and the function:

$$ e(n) = \frac{0.04}{\ln^2 n} $$

hardmath
  • 37,015
  • 1
    $\forall n \ge 2$, indeed. – TonyK May 18 '16 at 19:06
  • @TonyK: Yes, for the bound $n \lt p \lt 2n$. But see the article linked for stronger form $n \lt p \lt 2n-2$, which requires $n \gt 3$. I settled on the weak form of bound and $n \ge 3$ for petty consistency with "improved" statements, and now we could use $n \ge 2$ at top. – hardmath May 18 '16 at 19:14