Tackling Andrica's conjecture

Andrica's conjecture is one of those mathematical statements which are extremely easy to formulate, but complicated to prove. In fact it hasn't been proved yet, to be more precise. Here we go, for all consecutive prime numbers \(p_{n}\) and \(p_{n+1}\), it happens that:

1. The first attempt

Let's start with an analogy, here is an inequality \(p_{n+1} < 2\cdot p_{n}\) which is a direct result from Bertrand's postulate, proved by Chebyshev. As a result of this inequality, we have:

But what is the relationship between natural logarithm and square root functions?

Well, let's have a look at the following function: \(f_{1}(x)=\sqrt{x} - \ln(x)\). First derivative of this function is \({f_{1}}'(x) = \frac{1}{2\cdot \sqrt{x}} - \frac{1}{x}=\frac{1}{x}\cdot \left ( \frac{\sqrt{x}}{2} -1\right )\geq 0\), for \(\forall x\geq 4\). This means that\(f_{1}(x)\) is ascending for \(\forall x\geq 4\). As a result, for \(\forall p_{n}\leq p_{n+1}\), \(n\geq 3\) (because \(p_{3}=5\))

or

Finally:

As we can see, the analogy isn't of any use really, though we have a nice inequality.

2. The second attempt

Let's have a look at another function: \(f_{2}(x)=\frac{x}{\ln(x)} - \sqrt{x}\). Its first derivative is

For the first term we have:

for \(\forall x> 0\).

Let's check the second term:

and we are not done yet. Using \(a^{2}-b^{2}=(a-b)\cdot (a+b)\), we have:

What we have so far:

• \(\ln(x)-1 \geq 1\), for \( \forall x \geq e^{2}\)
• \( \sqrt{x}-1 \geq 1\), for \( \forall x \geq 4\)
• \( \sqrt{x}-\ln(x)>0\), for \( \forall x \geq 4\), this is, by the way, \( f_{1}(x)\), so \( f_{1}(x)\geq f_{1}(4)>0\)

Altogether:

for \(\forall x\geq e^{2}\).

This means \({f_{2}}'(x)\geq 0\) and \(f_{2}(x)\) is ascending, for \(\forall x\geq e^{2}\). As a result, for \(\forall p_{n}\leq p_{n+1}\), \(n\geq 3\) (the cases for \(p_{3}=5\), \(p_{4}=7\) and \(p_{5}=11\) can be verified with a calculator)

Final result is:

2.1 A negative result of the second attempt

It is worth mentioning that function \(\frac{x}{\ln(x)}\) has a special role in the number theory. According to the Prime Number Theorem:

where \(\pi (x)\) is the prime counting function.

Obviously \(\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n})}{p_{n}/\ln(p_{n})}=1\) and \(\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n+1})}{p_{n+1}/\ln(p_{n+1})}=1\) as sub-sequences. Also \(\pi (p_{n})=n\) and

If we put all these together, does it mean that \(\displaystyle\smash{\lim_{n \to \infty }} \left ( \frac{p_{n+1}}{\ln(p_{n+1})} - \frac{p_{n}}{\ln(p_{n})} \right )=1\)?

Nope, it doesn't, check this link for more details.

2.2 A positive result of the second attempt

According to the following article, in 2005 it was proved that \(\displaystyle\smash{\lim_{n \to \infty }}\inf \frac{g_{n}}{\ln(p_{n})}=0\), where \(g_{n}=p_{n+1}-p_{n}\) or the n-th gap.

It is also obvious that

(because \(p_{n} < p_{n+1}\) and \(\ln(p_{n}) < \ln(p_{n+1})\)). As a result:

Or

This means that Andrica's conjecture is true for an infinity pairs of \(p_{n}\) and \(p_{n+1}\). It doesn't prove the conjecture though, which states "it is true for all \(p_{n}\) and \(p_{n+1}\)".

3. The third attempt

How about the following function \(f_{3}(x)=\pi (x) - \frac{x}{\ln(x)}\)? Well, for this case I used the following Python code:

import math
import matplotlib.pyplot as plt

cache_prime = {}
cache_prime[1] = False
cache_prime[2] = True
cache_prime[3] = True

def is_prime(n):
    if n in cache_prime:
        return cache_prime[n]

    print "calculate",n
    l = int(math.sqrt(n)) + 1
    for i in xrange(2,l):
        if (n % i) == 0:
            cache_prime[n] = False
            return False
    cache_prime[n] = True
    return True

def p(x):
    ret = 0
    i = 2
    while i <= x:
        if is_prime(i):
            ret += 1
        i += 1
    return ret

def f(x):
    return p(x) - x/math.log(x)
    #return p(x) - math.sqrt(x)

START = 0
N = 40000
step = 0.25
x = []
y = []
x1 = []
y1 = []

n = START + 1.5
for i in xrange(START, N):
    val = f(n)
    x.append(n)
    y.append(val)
    
    n_n = int(n)
    if (abs(n_n - n) <= 0.0001) and is_prime(n_n):
        x1.append(n_n)
        y1.append(val)
    
    n += step

plt.plot(x, y)
plt.plot(x1, y1)
plt.show()

First of all, \(f_{3}(23)=1.66463325521 > f_{3}(29)=1.38774807317\). So, \(f_{3}(x)\) is not ascending. The general tendency of \(f_{3}(x)\) seems to be ascending though, according to this graphic (click to expand):

At least, for the areas where the function is ascending for consecutive primes (update the program to plot just plt.plot(x1, y1), i.e., primes and values of the function for the prime arguments), Andrica's conjecture is true, because if

then (also consider (2))

Still, this is not a proof.

4. What's next?

Well, probably the next logical thing is to analyse the function \( f_{4}(x)=\pi (x) - \sqrt{x}\). At least, it seems to be ascending for prime arguments.

But the work is still in progress...