6
$\begingroup$

I know that it is known that for every integer $n>1$ there is always a prime $p$ such that $n<p<2n$ (Bertrand´s postulate).

Also, I guess that it is still not known whether there is at least one prime between $n^2$ and $(n+1)^2$, for every positive integer $n$ (Legendre´s conjecture).

What about this:

Is there always at least one prime in the closed interval $[2^n,2^n+n]$ for every positive integer $n$?

I just checked for the first few $n$ by heart and found no counterexample although sometimes primes are at the endpoints of these closed intervals. Maybe first counterexample, if it exists, is not far away, but somebody will, I hope, check that.

$\endgroup$
2
  • $\begingroup$ just for your reference, for some state of the art regarding Legendre's conjecture see Matomäki's work: math.stackexchange.com/a/2323054/189215 $\endgroup$
    – iadvd
    Commented Dec 22, 2017 at 7:04
  • 1
    $\begingroup$ Your conjecture, judging just by the length of the interval, is a lot stronger than Legendre's conjecture (if we ignore anything special about powers of two); for instance, Legendre's conjecture says there is a prime in $[4^n,4^n+2^{n+1}+1]$. Your conjecture says there is a prime in $[4^n,4^n+2n]$, which is a way smaller interval. $\endgroup$
    – Milo Brandt
    Commented Dec 22, 2017 at 17:23

2 Answers 2

Reset to default
16
$\begingroup$

The first counterexample:

For $n = 13$, $2^n = 8192, 2^n + n = 8205$.

There does not exist any prime in $[8192,8205]$, though $8191$ is a prime.

The second counterexample:

For $n =14, 2^n = 16384, 2^n + n = 16398$.

There does not exist any prime in $[16384,16398]$.

Checked with this list.

$\endgroup$
3
  • $\begingroup$ Do you think there would be counterexamples if we change interval into $[2^n-n ,2^n+n]$? Probably would. $\endgroup$
    – user480281
    Commented Dec 22, 2017 at 6:05
  • 1
    $\begingroup$ @AntoinePalAdeen I think this will interest you: primes.utm.edu/lists/2small $\endgroup$
    – user371838
    Commented Dec 22, 2017 at 6:10
  • 1
    $\begingroup$ For concreteness, $25$ and $27$ are the first two counterexamples for $[2^n-n ,2^n+n]$. $\endgroup$
    – B. Mehta
    Commented Dec 23, 2017 at 0:16
11
$\begingroup$

Wikipedia references a theorems that put a lower bound on the size of gaps you can expect. For any positive constant $C$, there exists infinitely many integers $n$ such that the interval

$$ (n, n + C \log n) $$

does not contain any primes at all.

You're asking about gaps of size $\log_2 n$; consequently, your conjecture can be summed up as

The powers of 2 are very rare; maybe we get lucky and they never land near the beginning of such a wide gap?

Still, one might ask if your conjecture is plausible. Heuristically, assuming primes are distributed "randomly", the odds that an interval $(n, n + \log_2 n)$ doesn't contain a prime is roughly

$$ \left( 1 - \frac{1}{\log n} \right)^{\log_2 n } \approx \exp\left(-\frac{1}{\log 2} \right) \approx 0.2363$$

as $n$ grows large. Consequently, you'd expect roughly one in every four values of $n$ to serve as a counterexample.

Even if you amend your conjecture to account for finitely many counterexamples, it is implausible without some rationale suggesting there's a causal reason the intervals you've chosen should be special in some fashion.

$\endgroup$

You must log in to answer this question.