###
Generalized Legendre Conjecture:

Is there a prime between *n*^{s} and (*n*+1)^{s} for *s* < 2?

Equipped with the functions `isPrime(n)`

and `nextPrime(n)`

,
we can now easily test hypotheses and conjectures about primes.
(A *conjecture* is a statement we believe to be true but have not proved;
when someone eventually proves a conjecture, it becomes a *theorem*.)
Here are some interesting conjectures – all of them apparently true:
[Click to show or hide discussion.]

**Legendre's conjecture.**
*For each integer n* > *N*_{2} = 0, *there is a prime **p* between n^{2} *and* (*n*+1)^{2}.

Here the prime *p* may be 2, 3, 5, 7,..., i.e. *p* may be any prime.
As far as we know, *prime gaps* are never big enough to fully contain the interval [*n*^{2}, (*n*+1)^{2}],
so Legendre's conjecture holds, at least up to 18-digit primes. We can safely say so because *the largest gap*
between any primes up to 18 digits is only 1442; this gap happens
between the primes 804212830686677669 and 804212830686679111.
The interval [*n*^{2}, (*n*+1)^{2}] is *wider* than 1442 when *n* > 720,
so Legendre's conjecture is not in danger.)
Adrien-Marie Legendre was right 200 years ago –
but no one has been able to prove this conjecture, as of 2010.

**The ***n*^{5/3} conjecture.
*For each integer n* > *N*_{5/3} = 0, *there is a prime **p* between n^{5/3} *and* (*n*+1)^{5/3}.

Here, again, *p* might be any prime; no *prime gaps* are big enough to fully contain the interval [*n*^{5/3}, (*n*+1)^{5/3}].
Exhaustive checks for the first *million* values of *n* do not yield counterexamples.
Any prime gaps become relatively smaller and smaller, compared to the intervals
[*n*^{5/3}, (*n*+1)^{5/3}] for large *n*.
Therefore, the lower bound for this conjecture is *N*_{5/3} = 0;
the *n*^{5/3} conjecture appears to be true for all positive integers *n*.
We can consider it verified up to 18-digit primes, or *n* up to 10^{12}.

**The ***n*^{8/5} conjecture.
*For each integer n* > *N*_{8/5} = 0, *there is a prime **p* between n^{8/5} *and* (*n*+1)^{8/5}.

Here, once again, *p* may be any prime.
Exhaustive checks for the first *million* values of *n* reveal no counterexamples,
while any prime gaps become relatively smaller, compared to the intervals
[*n*^{8/5}, (*n*+1)^{8/5}] for large *n*.
The *n*^{8/5} conjecture appears to be true for all positive integers *n*.
We can consider it verified up to 18-digit primes, or for *n* up to 10^{12}.

**The ***n*^{3/2} conjecture.
*For each integer n* > *N*_{3/2} = 1051, *there is a prime **p* between n^{3/2} *and* (*n*+1)^{3/2}.

Here, *p* turns out to be *at least* 34123. Below that,
the intervals [*n*^{3/2}, (*n*+1)^{3/2}] are too small – so small that
*prime gaps* are occasionally bigger than some intervals [*n*^{3/2}, (*n*+1)^{3/2}]. For example,
the prime gap [31,37] contains the entire interval [10^{3/2}, 11^{3/2}],
the prime gap [89,97] contains the interval [20^{3/2}, 21^{3/2}], and
the prime gap [34061,34123] contains [1051^{3/2}, 1052^{3/2}].
The latter prime gap gives us the greatest counterexample *N*_{3/2} = 1051 –
exhaustive checks for each *n* *from one to ten million* reveal no other counterexamples,
while any prime gaps become relatively smaller, compared to the intervals
[*n*^{3/2}, (*n*+1)^{3/2}] for large *n*.
Therefore, based on our computational verification – combined with the knowledge of
maximal prime gaps up to 18-digit primes –
the *n*^{3/2} conjecture is apparently true for *n* > *N*_{3/2} = 1051.
We can consider it verified up to 18-digit primes, or for *n* up to 10^{12}.

**The ***n*^{4/3} conjecture.
*For each integer n* > *N*_{4/3} = 6776941,
*there is a prime **p* between n^{4/3} *and* (*n*+1)^{4/3}.

Here the prime *p* is at least 1282463543.
Below that,
*prime gaps* are occasionally bigger than some intervals [*n*^{4/3}, (*n*+1)^{4/3}].
For example,
the prime gap [7, 11] contains the interval [5^{4/3}, 6^{4/3}],
the prime gap [555142061, 555142307] contains the interval [3616622^{4/3}, 3616623^{4/3}], and
the prime gap [1282463269, 1282463543] contains the interval [6776941^{4/3}, 6776942^{4/3}].
The latter appears to be the largest counterexample.
(This has been checked by a computation for each *n* up to 57000000, as well as
a set of known large prime gaps after that. Combining this result with the existing data on
maximal prime gaps up to 18-digit primes,
we can consider this conjecture to be verified up to at least 18-digit primes.)

**The ***n*^{5/4} conjecture.
*For each integer n* > *N*_{5/4} ≥ 50904310155,
*there is a prime **p* between n^{5/4} *and* (*n*+1)^{5/4}.

Here *p* needs to be at least 24179270588903. Below that, there are many counterexamples, e.g.
the prime gap [7, 11] contains the entire interval [5^{5/4}, 6^{5/4}],
the prime gap [13, 17] contains the entire interval [8^{5/4}, 9^{5/4}], and
the prime gap [24179270588173, 24179270588903] contains the interval [50904310155^{5/4},50904310156^{5/4}].
The latter appears to be the largest counterexample.
(Is it in fact the largest? That still needs additional verification; hence the ≥ sign in this conjecture.)

**The ***n*^{6/5} conjecture.
*For each integer n* > *N*_{6/5} ≥ 833954771945899,
*there is a prime **p* between n^{6/5} *and* (*n*+1)^{6/5}.

In this conjecture, the prime *p* must be at least 804212830686679111. Below that, there are many counterexamples, e.g.
the prime gap [5, 7] contains the interval [4^{6/5}, 5^{6/5}],
the prime gap [7, 11] contains the interval [6^{6/5}, 7^{6/5}],
the prime gap [8775815387922523, 8775815387923457] contains the interval [19322926364254^{6/5}, 19322926364255^{6/5}],
and the prime gap [804212830686677669, 804212830686679111] contains the interval [833954771945899^{6/5}, 833954771945900^{6/5}].
The latter is the largest counterexample known to the author, as of May 2011.
(Is it in fact the largest? That still needs additional verification; hence the ≥ sign in this conjecture.)
To test the *n*^{6/5} conjecture further,
we would need to work with at least 19-digit primes.
JavaScript variables cannot store odd integers over 2^{53} = 9007199254740992,
so the *n*^{6/5} conjecture is not easily testable without
some library like `BigInt.js`

supporting larger numbers.
Thus, JavaScript is less suitable for such tests than languages with better support of extended precision arithmetic.

The above statements are verifiable up to at least 18-digit primes. (The existing knowledge of
maximum prime gaps up to low 19-digit numbers
simplifies the verification; beyond that, the verification becomes less practical.)
These statements suggest the following generalization:

**The generalized Legendre conjecture.**

(A) *There exist infinitely many pairs* (*s*, *N*_{s}), 1 < *s* ≤ 2,
*such that for each integer* *n* > *N*_{s}
*there is a prime between n*^{s} *and* (*n*+1)^{s}. (Weak formulation.)
(B) *For each s* > 1, *there exists an integer **N*_{s} such that for each integer n > *N*_{s}
*there is a prime between n*^{s} *and* (*n*+1)^{s}. (Strong formulation.)

**Discussion. **
Some of the pairs (*s*, *N*_{s}) are the above special cases:
(2,0),
(5/3, 0),
(8/5, 0),
(3/2, 1051),
(4/3, 6776941).
*N*_{s} is a function of *s*; namely, *N*_{s} denotes the *greatest* counterexample for the *n*^{s} conjecture:
if we proceed from small to large *n*,
the last interval [*n*^{s}, (*n*+1)^{s}] containing *no* primes
happens to occur at *n* = *N*_{s};
and for each *n* > *N*_{s} there is at least one prime
between *n*^{s} and (*n*+1)^{s}.
We readily see that *s* > 1 is indeed a necessary condition.
(A short explanation for a younger reader:
should we have *s* ≤ 1, our intervals [*n*^{s}, (*n*+1)^{s}] would be
*way too narrow* to contain a prime – or *any integer* at all, in most cases).
Moreover, is it plausible that *s* > *s*_{min} > 1 should also be satisfied,
with a certain lower bound *s*_{min}> 1, in order for *N*_{s} to exist?
If so, part (A) would still be true, but part (B) would be invalidated for some *s* very close to 1.

Questions to explore further:

(1) Is *N*_{s} a monotonic function of *s*? (No, it is not – there are counterexamples.)

(2) What the lower bound *s*_{min} might be, for the *n*^{s} conjecture to still make sense?
(A tongue-in-cheek guess: less than 1.1. A more serious answer:
*s* > 1 is likely enough; no additional *s*_{min} is needed.
Here is a hint.)

(3) How is the *n*^{s} conjecture related to other known conjectures and theorems about the distribution of primes?
(The *n*^{s} conjecture follows from the Cramer-Granville conjecture when *n* is large enough.)

Here is a partial computational verification of
special cases of the generalized Legendre conjecture.

Copyright
© 2011, Alexei Kourbatov, JavaScripter.net.