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.

  • $\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
    Dec 22 '17 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$ Dec 22 '17 at 17:23

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.

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy