Problems & Puzzles: Conjectures

Conjecture 8. Andrica’s 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) 


Jud McCranie 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:


Imran Ghory has pushed up the limit of verification by an indirect method. Here is it according to an email sent the 15/11/2000:

"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 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 infinity.

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.



Records   |  Conjectures  |  Problems  |  Puzzles