Some days ago I did a question on MSE about the following: why do the distances of every natural n to the following non-adjacent coprimes (smaller or greater, it does not matter) are always a prime number?.
To my surprise (due to my lack of knowledge) it was a very well known property of the prime numbers and the coprimes. Indeed the prime number that is found will be always the smallest prime number that does not divide n.
Thinking about it, then the distance to the next non-adjacent coprime to n! is exactly the next prime to n so a totally useless (but theoretically correct) primality test would be calculating every n!, and then finding the distance to the next non-adjacent coprime to n! because that distance is the next prime to n. Useless but correct. Indeed the user that kindly answered my question commented that a similar (and marginally more efficient test) would be (1) to take the product of the first n primes (primorial), then find the nearest non-adjacent coprime number. That distance would be the n+1th
prime.
So I did that test, and indeed it is required the primorial of the odd numbers, no need to multiply by 2, just (p(n)#/2) meaning the product of the primes up to the nth prime divided by 2 (because 2 is not really necessary for the property (1) be true.
And here is the Python code that looks for the nth prime:
def primality_primorials_coprimes():
from sympy import gcd
from gmpy2 import mpz,mul,sub,add,is_prime, divexact
def printTime():
import time, datetime
ts = time.time()
st = datetime.datetime.fromtimestamp(ts).strftime('%Y-%m-%d %H:%M:%S')
print(st+"\n")
printTime()
loop_advance = 1
lop=[]
lop.append(2)
lop.append(3)
# modify this to look for the nth prime
nth_prime = 1000
times = sub(nth_prime,2)
while times > 0:
n= mul(loop_advance,lop[-1])
j=add(n,lop[-1]+2)
while not gcd(n,j)==1:
j=add(j,mpz(2))
lop.append(int(sub(j,n)))
loop_advance = mul(loop_advance,lop[-2])
lop.remove(lop[-3])
times = sub(times,1)
print("Prime("+str(nth_prime) + ")=" + str(lop[-1]))
print()
printTime()
primality_primorials_coprimes()
Be aware that I am not using the primorial
function from sympy because it is better to reuse the variable that
contains the former primorial and multiply for the next prime that was
found than multiplying again all the primorials every time the next prime
is searched.
When I was reviewing the theory behind this my first thought was that from all the definitions of prime numbers, no one explains the fight between the "partial randomness" and the order of the prime numbers so well than this one. I mean: all the sieves and primality tests look for primes in a way that does not show this order behind the prime numbers, pseudo primes appear, etc. In the other hand, finding the prime numbers in the distance to the next non-adjacent coprime shows an incredible order and logic, it is easy to follow and understand (once somebody guides you through the idea!).
There is order in the prime numbers, even if the kind of order they have is not good enough to be able to calculate them quickly. That is the reason why the randomness of the primes is a partial randomness. It is possible to find them ordered like in am algorithm as above, but in a second level they are still random.
For instance in the algorithm of primorials, it is possible to jump up from n=p(n)# to p(n)#+(last_prime_found) and start looking for the first non-adjacent number coprime to p(n)# jumping two numbers up to the moment the next coprime is found, because we know that there is an order and the next prime to be found must be greater than the previous prime that was found and also is an odd number. But in the other hand we do not know exactly how many numbers we need to verify until we will find from that point the next coprime (and thus, the next prime distance from the primorial to that coprime, which is the next prime we are looking for).
For instance in the algorithm of primorials, it is possible to jump up from n=p(n)# to p(n)#+(last_prime_found) and start looking for the first non-adjacent number coprime to p(n)# jumping two numbers up to the moment the next coprime is found, because we know that there is an order and the next prime to be found must be greater than the previous prime that was found and also is an odd number. But in the other hand we do not know exactly how many numbers we need to verify until we will find from that point the next coprime (and thus, the next prime distance from the primorial to that coprime, which is the next prime we are looking for).
