A probabilistic coincidence: the set of primitive roots modulo a prime number p, when p > 61, contains two roots r1,r2 whose sum is the next prime to p

I wrote about this observation at Mathematics Stack Exchange, and basically it is the weirdest thing I have seen so far, but finally it is based on probabilities as one fellow at MSE explained!

Take the set of Primitive Roots Modulo p (link to definition here) of a prime number p, Pr(p). For those primes p > 61 there is always a pair of primitive roots r1 and r2 in Pr(p) whose sum is the next prime to the current prime p, I will call it N(p).

I have tested this with Python, in the interval [62,7000] being always true. E.g.:

For p∈[1,61] there are only five counterexamples: {2,3,5,7,61} and for the rest of primes the observation is true as well.

A prime number generator algorithm based on x^2+(x-1)^2 that generates only primes.

(I wrote also a question about this in Mathematics Stack Exchange, here)

Update: a senior fellow at the Mathematics Stack Exchange clarified the reason why it works. It is just a trivial brute-force algorithm because for each value in [1..s] the algorithm is going through all f2(k+s) mod k until the first 0 congruent value is found, which turns to be a factor of f2(s) and then jumps to the next s. So basically finds for every f2(k) the first prime number that is a factor of f2(k). I did not see the forest for the trees. I am learning so much from them!

I think I could have found a prime number generator algorithm, but still I am not very sure, maybe this is an already known property of perfect square numbers, maybe not, but it looks amazing, so I wanted to share here the idea and the code.

The Python Code

# Elementary number theory
# -- Modular arithmetic (perfect square numbers)
# --- Computational number theory
# ----- Prime number generator function

# created by David @ Hobbymaths
# http://hobbymaths.blogspot.jp/

#import cProfile

def prime_number_generator():
    from math import floor, log, sqrt
    from gmpy2 import xmpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits

    # the execution takes around 50 minutes, depending on the computer
    def printTime():
        import time, datetime
        ts = time.time()
        st = datetime.datetime.fromtimestamp(ts).strftime('%Y-%m-%d %H:%M:%S')
        print(st+"\n")

    printTime()

    testlimit = xmpz(3000000)

    # insert all the f2 values in resfunc
    resfunc = []
    for n in range(1, testlimit):
        resfunc.append(add(sub(mul(50,mul(n,n)),mul(10,n)),1))

    totlist = []
    # shift S
    for s in range (0,50000):
        found = False
        # range K
        for k in range (1,testlimit-s-1):
            if (k!=1) and (resfunc[s+k]%k == 0 ):
                if (is_prime(k)):
                    totlist.append(str(k))
                else:
                    totlist.append("If this message appears the algorythm is wrong")
                found = True
                break
               
        #if not found:
            # if no prime number was found in the current range K[1..k] then append 0 if you want to know which shift s
            # does not find a prime number in the range K
            #totlist.append("0")
           
    mystr=""
    for l in totlist:
        mystr = mystr + l + "\t"

    # Will print the generated prime numbers
    print(mystr)

    printTime()
       
#cProfile.run('prime_number_generator()')
prime_number_generator()
       

1. How did I find it?

While I was studying the properties of perfect square numbers, I came across an observation about how some perfect square numbers were able to generate prime numbers when added to the previous or next perfect square. Specifically only those perfect squares of a natural number n = 5*k / k belongs to N, in other words, those perfect squares ending with "00" or "25", are able to generate prime numbers when added to the previous or next perfect square, and of course that happens only sometimes.

I focused on those who are able to generate two primes, with the previous and next perfect square.

For instance, these two samples:

n=(5*k)

n=(5*5=) 25+ (4*4=) 16(previous) = 41 (prime)
n=(5*5=) 25+ (6*6=) 36(next) = 61 (prime)

n=(30*30=) 900 + (29*29=) 841(previous) = 1741 (prime)
n=(30*30=) 900 + (31*31=) 961(next) = 1861 (prime)

...being the distance between those primes 4*k

Unfortunately, there is not a clear rule why some of the perfect squares only ending with "00" or "25" are able to obtain prime numbers.

For that reason, I wanted to learn more about the functions that are generating the above mentioned results, which are f1=x^2+(x+1)^2 and f2=x^2+(x-1)^2, but applied to x = 5*k and there was a great surprise in the results of that study.

2. The prime number generator algorithm (only generates primes):

First I wrote the same functions replacing x = 5*k:

f1(k)=50k^2+10k+1 and f2(k)=50k^2-10k+1.

I just wanted to know the relationship between k, f1(k) and f2(k), so I started to play with modular arithmetic, it was easier to use first f2, calculating some congruences series in the following way:

1) (shift s=1) Calculated the congruences serie [f2(k+1) mod k] for a range K [1..k], and I found out that there are only two k numbers whose congruence is 0, one of them is k=1 and the other was a prime number, k=41.

2) (shif s=2) Then, I did the same calculation of the congruences serie but shifting one number to the right, so now I calculated the congruences serie [f2(k+2) mod k] for all k, and again the two k numbers congruent with 0 were k=1 and in this case a new prime, k=181.

3) (shift s) I extended the calculation of congruence series shifting up from 3 to s=50000 to the right, and always in the congruences serie associated to the current s, the non trivial (I consider k=1 the trivial solution) k number that is congruent with 0 is always a prime number, when I have been able to find that number in the limits of the range of number K [1..k] I am using for the tests(*).

(*) Sometimes I cannot find the prime number, because, depending on the shift s, the 0 congruent primer number appears later, because it might be very big, and does not appear in my current defined K[1..k] range (of my Python test code) or it would be possible also that for certain s values there is no 0 congruent number in the congruences serie.

My tested range was K[1..50000] and S[1..50000] and it was able to find 40357 prime numbers inside the K range, but for some S values, the prime number still not appears inside the K range (in this test case S=50000 so 50000 - 40357 = 9643 primes are not found for a certain s shift value).

The greater prime found is 489061 and the smaller is 13, and they appear unordered along the shifting of S.

So according to the results, it seems possible to generate a list of only prime numbers by calculating f2(k+s) into a specifig range of K [1..k] and finding the first non trivial 0 congruent k which turns to be a prime number, applying it for a shifting S [1..s] (**). Each [f2(k+s) mod k] congruences serie provides a prime number for the final list of primes (when the prime number which is congruent to 0 is found inside K).

(**)I did not make the setup for f1 because is easier to work with f2.

The generated prime numbers list has repeated elements and the primes appear unordered, but it seems to provide only primes inside the range K[1..k].

The first k elements of the list are (for s=1, s=2, s=3...):

k=41,181,421,761, 1201, 1741, 2381, 3121, 17, 13, 13, 73, 53, 9661, 17, 12641, 14281, etc.

I did not find any reference in OEIS.

I am trying to understand why it works, but it is very promising. Please if somebody has some ideas about why the algorithm is working (or if there is a counterexample I did not see), please let me know.

I wonder if this is new or somehow it was already known, or I am wrong...
David

Fibonacci - Catalan deterministic prime number sieve

This text is related with the following topics:

# Elementary number theory

# - Combinatorial Number Theory

# -- Sieve methods (Fibonacci, Catalan)

# --- Computational number theory

# ----- Primality-testing (deterministic)

As I was learning about the properties of the Pascal's triangle, I came across a probably well known property of the prime numbers, but I did not find much information about it on Internet, online papers, or books. Basically, playing with the properties of the triangle, I was able to prepare a prime number sieve based on the Fibonacci and Catalan numbers, both included in the triangle that seems to be a deterministic sieve, this means that the set of pseudoprimes generated by the Fibonacci primality rule and the Catalan primality rule are disjoint sets, so the combination of both rules provides a deterministic prime sieve. I will write more about the reasons why I decided to prepare this type of sieve in a former post. 

There are two well known primality tests using Fibonacci and Catalan numbers. It is possible to find several online papers of several universities about the primality properties of Fibonacci (Lucas) and Catalan sequences and general information about them in the Wikipedia and other sources of information. Both primality tests are able to generate prime numbers but also there are sets of pseudoprimes (false candidates) that verifiy the primality rules in both tests.

E.g.: "Catalan numbers, primes and twin primes" paper of Christian Aebi and Grant Cairns,

of College Calvin and the Department of Mathematics of La Trobe University (Melbourne, Australia) respectively.

(In Google usually the pdf is available in the first link that appears in the results page)

Basically my observation (computational, non theoretical) is that the Fibonacci pseudoprimes and the Catalan pseudoprimes are disjoint sets, so it is possible to create a sieve by using both primality rules as a two step primality filter. 

For that purpose I have created a prime number sieve (in Python) able to obtain the prime numbers applying the Fibonacci and Catalan primality rules. I have run tests in the range N = (4, 10,000,000) and no pseudoprimes appeared, all the candidates that verify both rules are true prime numbers. So the sieve seems to be a deterministic sieve.

It is not competitive in terms of computing time as the usual probabilistic sieves, the point here is to verify that the pseudoprimes associated to the Catalan prime sieve and the pseudoprimes associated to the Fibonacci (Lucas) prime sieve are disjoint sets. About this point I did not find a clear source of information in Internet, and I find it very interesting.

The following is the explanation of the algorithm and the Python code, so anyone can run it. 

Python 3.4.2, gmpy2 and Cython are required to run the tests.

THE ALGORITHM

It is based on two properties of the prime numbers.

It sieves the primes inside a selected N range = (4, test_limit),

(2,3,5) are included by default.

1. Fibonacci numbers primality, calculation of the Fibonacci number associated to the current integer n.

For every n in N, the following association is done (is a shifting of Fibonacci to optimize the computing time):

n=4, fib = 2

n=5, fib = 3

n=6, fib = 5

n=7, fib = 8

n=8, fib = 13

etc.

(where 2,3,5,8,13 is the Fibonacci sequence)

PRIMALITY RULE (1):

n is a Fibonacci prime (candidate) if its associated Fibonacci number mod n is = 0 or = 1 (is congruent 0 or 1 mod n) 

(the current Python version uses gmpy2.c_mod function, so the congruences are negative, so some operation is performed to recover the corrent number,

but the applied rule is the above mentioned rule)

2. Catalan numbers primality, (related with Wilson Theorem)

http://en.wikipedia.org/wiki/Wilson%27s_theorem

2.1 For every n ODD inside N:

The Catalan number C(((n-5)/2)+1) is associated to n.

The calculation of the associated Catalan number recursively is as follows:

The Catalan number C(((n-5)/2)+1) is associated to n and C(((n-5)/2)+1) = (Catalan_number_associated_to_n-2_in_previous_recursive_step * (n-4) * 4)//(n-1)

// means integer division

The first odd number inside N is 5 and for this value its associated Catalan number is 1.

E.g, here are some samples of the recursive calculation:

(n,(((n-5)/2)+1))

n=5, will be associated to the Catalan number 1

n=7, will be associated to the Catalan number 2

n=9, will be associated to the Catalan number 5

n=11, will be associated to the Catalan number 14

n=13, will be associated to the Catalan number 42

etc.

(where 1,2,5,14,42 is the Catalan Numbers sequence)

PRIMALITY RULE (2):

n is a Catalan prime number (candidate) if its associated Catalan Number mod n when is multiplied by 4 is equal exactly to (n-1) or (n+1), so it is (n-1) or (n+1) congruent.

In other words: 4*Catalan_number_associated_to_n is (n-1) o (n+1) congruent (mod n).

In the code I am appliying the (Catalan mod n)*4 approach.

FINAL PRIMALITY FILTER

A n candite of (4,N) is a prime number if and only if PRIMALITY RULE (1) and PRIMALITY RULE (2) are passed. 

This is because the Fibonacci pseudprimes (false candidates passing rule 1) and the Catalan pseudoprimes (passin rule 2) are disjoint sets (there are not pseudoprimes n that at the same time are Fibonaaci and Catalan pseudoprimes) 

The Python code verifies first the Fibonnaci primality rule because the computing time is lower than the Catalan rule computing time, so in case that a candidate n does not verify the Fibonacci rule it is not neccessary to calculate the Catalan primality rule. 

The FibCat Algorithm:

Basically is as follows:

Loop n in (4, test_limit)

a) Calculate the associated Fibonacci number of the current candidate n

b) If n is even continue loop (next n)

c) Calculate the associated Catalan number of the current candidate n (n is a odd number)

d) Avoid basic prime composites: if n is a multiple of 3,5,7,11,13,17,19, or the next odd number after a cuple of twin primes located in (n-4,n-2), or a perfect square continue loop (next n)

e) If primality rule (1) is verified and primality rule (2) is verified, then the candidate n is prime. 

In the Python code there are more details and optimizations, some of them derived of using Python as the programming language, but with the above explanation, it is possible to rewrite the code in any language.

THE PYTHON CODE

# This code was created by David
# http://hobbymaths.blogspot.jp/

# Elementary number theory
# - Combinatorial Number Theory
# -- Sieve methods (Fibonacci, Catalan)
# --- Computational number theory
# ----- Primality-testing (deterministic)

#import cProfile

def fibcatSieve():
    from gmpy2 import xmpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits

    set_cache(1000,16384)

    def printTime():
        import time, datetime
        ts = time.time()
        st = datetime.datetime.fromtimestamp(ts).strftime('%Y-%m-%d %H:%M:%S')
        print(st+"\n")

    printTime()

    test_init, test_limit = xmpz(4), xmpz(1000000)

    def Multiple(n,a):
        return (not c_mod(n,a)) and (n>a)

    falsecand = []

    catalan_number, prcounter, totalcounter, tpflag, quarterlimit, divisible_four = xmpz(1),xmpz(3),xmpz(3),0,test_limit>>2, True
    quarterlist, quartercheck = [0,mul(quarterlimit, 3),mul(quarterlimit, 2)], quarterlimit

    fv = [xmpz(0),xmpz(1),xmpz(1)]

    #prlist = [xmpz(2),xmpz(3),xmpz(5)]
    #print(2)
    #print(3)
    #print(5)

    for n in range(test_init, test_limit):

        fv[0] = fv[1]
        fv[1] = fv[2]
        fv[2] = fv[0]+fv[1]

        if (not n & 1):
            if (n == quartercheck):
                print("Current position: "+str(n))
                quartercheck = quarterlist.pop()
            continue

        catalan_number = divexact(mul(catalan_number, sub(n,4)), xmpz(n)>>2) if divisible_four else divexact(mul(catalan_number, sub(n,4)), xmpz(n)>>1)<<1
        divisible_four = not divisible_four
        if (Multiple(n,3) or (n>5 and str(n)[-1:]=="5") or Multiple(n,7) or Multiple(n,11) or Multiple(n,13) or Multiple(n,17) or Multiple(n,19) or (tpflag == 2) or (is_square(n))):
            tpflag = 0
            continue

        fmod = c_mod(fv[2],n)

        if ( (not fmod or (fmod == -~-n)) and (abs(add(c_mod(catalan_number, n)<<2,add(n<<1,n))) == 1) ):
            #print(str(n))
            #prlist.append(n)

            totalcounter = add(totalcounter, 1)

            if is_prime(n):
                prcounter = add(prcounter, 1)
                tpflag += 1
            else:
                falsecand.append(n)
                print("If this message appears then the algorithm is wrong!")
            continue

        tpflag = 0

    print("Test Checkout"+"\n"+"n"+"\t"+"Total :"+"\t"+"Primes: "+"\t"+"False candidates (pseudoprimes):"+
    "\n"+str(test_limit)+"\t"+str(totalcounter)+"\t"+str(prcounter)+"\t"+str(totalcounter - prcounter))

    strfalse = ""
    for myfkey in falsecand:
        strfalse = strfalse + str(myfkey)+"\t"
    print("Pseudoprimes list: "+"\n"+strfalse)

    printTime()

#cProfile.run('fibcatSieve()')
fibcatSieve()

I am comparing my results with gmpy2.is_prime(n) function, which uses a probabilistic primality test. To be sure that there are no errors, I am double checking the results versus a Excel list of prime numbers taken from the famous "The Prime Pages" website. Special thanks to my friend Ignacio for the good tips to enhance the computing time of the algorithm.

If somebody has some ideas to enhance the code, or some comments about this please write freely, probably the properties above mentioned are well known, or are direct result of the pseudoprime classification of the Catalan and Fibonacci pseudoprimes. I am very interested in learning more about this.