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₂ = 0, there is a prime p between n² and (n+1)².
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², (n+1)²], 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², (n+1)²] 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¹².

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¹².

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¹².

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⁵³ = 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.