Problems & Puzzles:
Conjecture 8. Andricas Conjecture
Another conjecture related with
consecutive primes is the one from Dorin Andrica :
(sqrt(pn+1) - sqrt(pn))<1
for all n.
which has been verified for Dan
Grescu for pn<106 .
(Ref. 2, p. 21)
adds this by e-mail, on August 4, 1998 :
"In December 1996 I
verified this for pn < 2^26. I just checked
it to 2^31, and it still holds up.
Mr. Marek Wolf
writes us at 15/11/98 and says: "I have checked that
Andrica's conjecture is true up to
2^42=4398046511090, the computer is still running, I plan
to reach 2^44.
Dr. M.L.Pérez (12/2/99)remaind
us that the Andrika's conjecture has been generalizaded
by Smarandache. Please see: http://www.gallup.unm.edu/~smarandache/conjprim.txt
Imran Ghory has pushed up the limit of
verification by an indirect method. Here is it according to an email sent
"I've managed to find a way which lets me
verify Andrica’s Conjecture up to 1.3002*10^16 (roughly 2^53),
it works like this, If we have the primes p and q, where q is the next
prime after p. We have, sqrt(q)-sqrt(p) < 1 We can say, q=x+s and
p=x, and by entering them into the equation and rearranging we can get,
sqrt(x+s)-sqrt(x) < 1
=> sqrt(x+s) < 1+sqrt(x)
=> x+s < 1+(2*sqrt(x))+x
=> s < 1+(2*sqrt(x))
=> (s-1) < 2*sqrt(x)
=> ((s-1)/2)^2 < x
As s is the gap between the two primes, we can say if for the
first occurrence of that gap when put into the equation ((s-1)/2)^2, is
less than the first prime where it occurs then it is below all of the
other primes where the gap occurs.
We can find the first occurrence of gaps between primes from the
table at http://www.trnicely.net/gaps/gaplist.html
putting the values from the table into the equation we find that the
equation holds true for every gap given in the table.
As the table includes all the gaps below 1.3002*10^16, this leaves
us with no more possible values of s to make the equation false for any
value of x below 1.3002*10^16. Which means that Andrica’s
Conjecture is true for all values of p below 1.3002*10^16(roughly 2^53)".
Jim Fougeron wrote (4/11/01):
Conjecture 8 states: (sqrt(p(n+1)) - sqrt(p(n)))<1
for all n.
1. The gap needed to go from p(n) to p(n+1) is ceil(2*sqrt(p(n))+1).
This formula is derived by: (p(n) is represented by p0 for
the remainder of this email)
Assume sqrt(p0+gap) - sqrt(p0) >= 1
then sqrt(p0+gap) >= sqrt(p0) + 1
>> p0 + gap >= 2*sqrt(p0) + p0 + 1
>> gap >= 2*sqrt(p0) + 1
>> since p0 will never be a perfect square (it is prime of
course), 2*sqrt(p0)+1 will never be integer, thus a ceil(2*sqrt(p0)+1)
will render a gap of sufficient size. This number may still be one
short, but for this example, that fact will be ignored.
2. Prime numbers will be found at an average distance from each other at
roughly ln(N) distance apart. (simplification of PNT)
3. The value D will be used as a "simple" measure of how far
away from "average a certain gap is. A value of D = 1 is a
gap right at expected value, a value of D = .01 is a gap which is pretty
small (possibly a prime twin), a gap of D=100 is a huge gap which is 100
times the size of a single expected gap. D is defined as
gap/ln(p0) which has been shown for this conjecture to be required to be
at least ceil(2*sqrt(p0))+1)/ln(p0)
4. ceil(2*sqrt(p0))+1)/ln(p0) diverges to infinity as p0 approaches
5. Fact: It has been shown by prior example (within the Conjecture 8
page of Prime Puzzles) that there are no gaps less than 2^53 which
disprove Conjecture 8.
6. Fact: at p0 = 2^53, D = 5166822, so at p0=2^53 we are looking for a
gap that is roughly 5 million times larger than average. (a gap of
at least 189812533).
7. Fact: (I can not prove this however), there is no possible prime gap
which is 5 million times larger than average, and this is the smallest
possible gap which would disprove the conjecture.
This is certainly not a solid proof, but it does show (with item 4) that
at most there is a finite number of gaps which could disprove this
conjecture, and that finite number is almost certainly zero.