Oppermann's conjecture

In this article, we have explored Oppermann's conjecture and implemented a program in an attempt to prove or disprove it. This is an important conjecture for prime numbers.

Table of contents

1. Definitions
2. Algorithm
3. Time complexity
4. A way of implementation

1. Definitions

A conjecture is synonymous with hypothesis and consists in having no proof yet to be verified as true of false. It starts from a real fact and it has a rule for it.

A prime number is a number that is only divisible to 1 and itself.

The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 …

Notice that 1 is not part of this series.

Back in 1877, Danish mathematician Ludvig Oppermann announced in an unpublished lecture his thoughts about the distribution of the prime numbers by saying that:

for every integer x > 1, there is at least one prime number between \(x^2 − x\ and\ x^2\), and at least another prime between \(x^2\ and\ x^2 + 1\).

If the conjecture is true, then the gap size would be on the order of \(g_{n} < \sqrt{p_{n}}\)

Obs. Notice that we can easily apply the square root to the conjecture but in that case the conjuecture will not be valid anymore, meaning it will not be any prime number in the range of \((x-\sqrt{x}, x)\ and\ (x,x+\sqrt{x})\).

2. Algorithm

Since the Oppermann's conjecture is a formula that is using the prime numbers, the only thing that we need to implement is to generate the prime numbers series.

If you are a beginner in programming if you want to check if a number is prime you might want to use a simple loop to check for all numbers between 2 and the square root of it !

    procedure isPrime(n)
        loop
            i <- 2..sqrt(n) 
            if (n mod i == 0) return false
        end loop
        return true

This check might be time consumming and double checking. Why ? because you start checking from number 2 and continue until you reach the square root number. But in this subset there might be other numbers that are divided with other prime numbers so there is no need to check for them again !

To avoid this situation we can use an array to store the previous checked prime numbers, i.e. we only divide the given number to the prime numbers before it, this method is called memorization.

procedure isPrime(array p, n)
    i <- 0
    while p[i] <= sqrt(n)
        if (n mod p[i] == 0) return false

    return true

procedure generatePrime(n)
    array p
    j <- 0

    for i <- 3..n-1
        if (isPrime(p, i)) 
            {
            p[j] <- i
            j <- j + 1
            }

Another way is to use the sieve of Eratosthenes , the sieve of Sundaram or the sieve of Atkin

3. Time complexity

Since we check all the numbers the generatePrime function will be O(N).
For the isPrime function we check only for the prime numbers before the square root of N, which depends on the size of the subset of the prime numbers which means usually O(log N)
So, generating the prime series will be O(N logN)

4. A way of implementation

    #include <iostream>
    #include <math.h>

    using namespace std;

    bool isPrime(int *p, int n)
    {
        int sqrtn = sqrt(n), i=0;

        while ( p[i] <= sqrtn )
            if(n%p[i++] == 0) return false; 

        return true;
    }

    int & generatePrime(int n, int &size)
    {
        int *p, i, j; 
        p = new int[n];

        j=0;
        p[j++]=2;

        for (i=3; i < n; i++)
            if(isPrime(p, i)) p[j++] = i;

        size = j;   

        return *p;
    }

    void checkOppermannConjecture(int n)
    {
        int i, size;

        int *p = &generatePrime(n*n,size);

        for (i = n*n - n; i <= n*n; i++)
            if (isPrime(p,i)) cout << i <<" prime in range x(x-1)" << endl;

        for (i = n*n; i <= n*n + n; i++)
            if (isPrime(p,i)) cout << i <<" prime in range x(x+1)" << endl;

    }

    int main()
    {
        int n = 5;

        checkOppermannConjecture(n);

        return 0;
    }

Output n = 5:

23 prime in range x(x-1)
29 prime in range x(x+1)

Output n = 25:

601 prime in range x(x-1)
607 prime in range x(x-1)
613 prime in range x(x-1)
617 prime in range x(x-1)
619 prime in range x(x-1)
631 prime in range x(x+1)
641 prime in range x(x+1)
643 prime in range x(x+1)
647 prime in range x(x+1)

As we can see from the above output, in every range there is at least one prime number, and more than that there could be more than 1 and different in number. We can call this the prime-counting function:
\(π(x^2 − x) < π(x^2) < π(x^2 + x)\ for\ x > 1\)

With this article at OpenGenus, you must have a strong idea of Oppermann's conjecture.