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.

Hobbymath's wanderings #6

Legendre symbol.

Phibonacci Numbers (Euler's Totient function - related).

Anders Bager on Phibonacci Numbers.

Definition of Primorials.

Double Mersenne number.

OEIS double Mersenne number.

OEIS n*sigma(n).

Introduction to Analytic Number Theory (U. illinois).

Relationship between Euler's Totient function, Mobius and Divisor functions (Dineva).

Lehmer's Totient problem.

OEIS Abundant numbers.

OEIS Merten's function (Mobius accumulated sum).

Randomness Tests (Wikipedia).

Bunyakovsy conjecture (Wikipedia).

List of probabilistic proofs of non-probabilistic theorems (Wikipedia).

Euler's Theorem (Wikipedia).

OEIS A completely multiplicative function example.

Artin's conjecture on primitive roots.

Conjecture about the product of the primitive roots modulo a prime number

Related with my previous post, I found a similar property in the product of the primitive roots modulo p, I will call them, Pr_p, where p is a prime number. 

Let P(n) be the previous prime smaller than n, then:

And N(n) be the next prime greater than n, then:

So it seems that the product of the primitive roots modulo a prime p is at a distance d1 of its previous closer prime and a distance d2 of its closer next prime, being d1 and d2 = 1 or a prime number.

(*) Notice that in the sample by chance d1 and d2 incidentally are exactly the previous and next prime numbers of the original p = 17.

I asked about this possible property, and the answer I received from one of the fellows at Mathematics Stack Exchange was very amazing, you can see here the question and the answer.

I have tested it in the interval of primes in [1,1000]. This is the Python code:

#import cProfile

def primitive_roots():
    import fractions
    from sympy import divisor_count, totient, mobius, is_primitive_root, nextprime, prevprime
    from math import floor, log, sqrt
    from gmpy2 import mpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits, div, gcd

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

    def prim_root_prod(value):
        calprod = 1
        for i in range (1,value):
            if is_primitive_root(i,value)
               calprod = calprod * i
        return calprod

              
    printTime()

    print("N(Pr_p) TEST")   
    n=nextprime(1)
    while n<1000:
        calprod = prim_root_prod(n)
        res = nextprime(calprod)-calprod
        if is_prime(res) or (res == 1):
            print("Success for " + str(n) + " , d2 is " + str(res))
        else:
            print("If this message appears, then the conjecture is false for " + str(n) + " because the distance d2 is not a prime number: " + str(res))
   
        n=nextprime(n)

      
    print("P(Pr_p) TEST")   
    n=nextprime(3)
    while n<1000:
        calprod = prim_root_prod(n)
        res = calprod-prevprime(calprod)
        if is_prime(res) or (res == 1):
            print("Success for " + str(n) + " , d1 is " + str(res))
        else:
            print("If this message appears, then the conjecture is false for " + str(n) + " becase the distance d1 is not a prime number: " +  str(res))
   
        n=nextprime(n)
   
    printTime()
       
#cProfile.run('primitive_roots_test()')
primitive_roots_test()
 

About Fortunate numbers and other similar expressions

Recently I stumbled upon a very interesting question in the Mathematics Stack Exchange (here). It turned out to be an already known conjecture, that I did not know at all, and is really amazing. 

Let N(n) be the next prime greater than or equal to n. The conjecture states that N(n!)-n! is either 0 (case n = 2), 1 or a prime number. It has been tested for the first 2000 terms only.

As one of the fellows at MSE said, the origin of it is the Fortunate numbers, using for the above expression the primorials instead of the factorials. And so far, the known expressions E(n) that are able to comply with the expression N(E(n))-E(n) is 0,1,or Prime, are the Fortunate numbers and the n! version stated by Amarnath Murthy in the OEIS page (link here).

In my humble opinion, I think that the rule might be generalized to something like this (1):

Where E(n) is a function or expression based on n, Natural number.

I have been trying other expressions and the following ones seem to comply as well (maybe they are known, but I just did some trial-error). I tested both over the interval [1,600] with Python:

I wondered if it was possible to find an expression E(n) < n! and the following one seems to work as well! (at least up to 600, my computer takes time for the factorial tests in Python).

I found other expressions E(n) < E2(n) that seem also to comply with the original rule, but I am still testing them. The topic is really amazing. I tried also for instance Catalan numbers, but they do not comply.

So the interesting point about those conjectures would be:

This is the Python code I used for testing:

# Elementary number theory
# -- Computational number theory
# --- Prime number generator function
# ---- Fortunate numbers variations
# by David M. @ https://hobbymaths.blogspot.com

#import cProfile

def fortunate():

    import fractions
    from sympy import divisor_count, totient, factorial, nextprime
    from math import floor, log, sqrt
    from gmpy2 import mpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits, div, gcd

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

    printTime()

    lop1 = []
    lop2 = []
    lop3 = []


    # Factorial version
    print("Factorial variation")
    for n in range(1,600):
        myf = factorial(n)
        np = nextprime(myf)
        if is_prime(int(np-myf)) or (np-myf==1) or (np-myf==0):
            lop1.append(np-myf)
        else:
            print("If this message appears, the conjecture is false")

    str1 = ""
    for i in lop1:
        str1 = str1 + str(i) + "\t"
    print(str1)

    # 2^i*i! version
    print("Power * factorial")
    num = 1
    for n in range(1,600):
        num = factorial(n) * (2**n)
        den = 1
        res = num//den
        np = nextprime(res)
        if is_prime(int(np-res)) or (np-res==1) or (np-res==0):
            lop2.append(np-res)
        else:
            print("If this message appears, the conjecture is false")

    str1 = ""
    for i in lop1:
        str1 = str1 + str(i) + "\t"
    print(str1)

   
    # i!/2^(i//2) version
    print("Factorial / power")
    num = 1
    for n in range(1,300):
        num = factorial(n)
        den = 2**(n//2)
        res = num//den
        np = nextprime(res)
        if is_prime(int(np-res)) or (np-res==1) or (np-res==0):
            lop3.append(np-res)
        else:
            print("If this message appears, the conjecture is false")
   
    str1 = ""
    for i in lop1:
        str1 = str1 + str(i) + "\t"
    print(str1)

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

I will update if I find new expressions like the ones above. If somebody knows more about the topic, please let me know.

UPDATE: I published at OEIS an example of this kind of sequences! (A257886 click here).

Euler's Totient phi(n) and divisors count function d(n) relationship

Related with my former post, I found the following statement also very interesting:

When both the totient, phi(n), value (a) and the divisors count (b) function, d(n) or tau(n), of n are factors of n, if both are multiplied, they are exactly the value of n, so a*b=n.

There is only one isolated counterexample at n=30, and I did not test over n>1000000, so it could be possible that other counterexamples were greater than 1000000.

I also asked about this question at the Mathematics Stack Exchange (link here). It might be trivial, but I do not see a single specific pattern in the values of n to justify it. Any hints are welcomed! 

UPDATE: finally it was proved by a kind fellow at MSE !!! (link here).

Euler's Totient function statement proposal

While I was learning about Euler's Totien function, I found the book "Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to Google books sample), there is a list of the open problems about the Totient function. I did my own try-outs of other combinations like the one referred as CMB34, regarding the divisibility of the Totient function phi(n), and I did find myself one that is very interesting, indeed I did not find any open conjecture or open problem about it, so here is my (initially) own proposed statement (1):

It means that for any integer greater or equal to 3, if its Totient value phi(n) divided by 2, plus one, p=((phi(n)/2)+1),  divides n, then p=((phi(n)/2)+1) is a prime number.

And it really seems to work! I have made a Python test in the interval [1..50000] and the statement is always true, no counterexamples. I have asked a question in Mathematics Stack Exchange, so I hope somebody will help me to understand why it is always true, and to know if it is a trivial statement or it is already known, etc. Initially I did not find any reference to my statement so it might be original. And there was a confirmation of a positive test up to 10^7.

Update (2015/04/16): The following statement also seems to be true always (2):

There are two differences with my main statement: in this case, n can only be an even number greater or equal to 3, so it can be divided by 2, and the relationship is true when a factor of n/2 is found (instead of a factor of n). I will update the post if I find more successful combinations. Tested in the interval [1,  10^9].

Update (2015/04/22): The list of the numbers n following the statement (1) has been accepted and published at OEIS! (link here).

This is the Python code I have used to test the main statement:

The Python code

# Elementary number theory
# -- Totient function
# --- Computational number theory
# ---- Prime number generator function
# By David @ http://hobbymaths.blogspot.jp/

#import cProfile

def div_Totient():
    from math import floor, log, sqrt
    from gmpy2 import mpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits, div, gcd

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

    printTime()

    # Brute force Totient calculation
    def calc_totient(n):
        tot = 0
        for l in range (1,n):   
            if gcd(n,l)==1:
                tot = tot + 1
        return tot
   
    for n in range (3,5000):

        tot = calc_totient(n)
           
        if (n%((tot//2)+1))==0:
            if is_prime(mpz((tot//2)+1)):
                print("SUCCESS n is " + str(n) + " and phi(n) is: " + str(tot) + " and hits the prime " + str((tot//2)+1) )
            else:
                # if this message appears, then the statement is false
                print("ERROR n is " + str(n) + " and phi(n) is: " + str(tot) + " and does not hit any prime ")
       
    printTime()
       
#cProfile.run('div_Totient()')
div_Totient()
        
It could be possible that I can not see the wood for the trees, and my statement is trivial, or already known, or nonsense, so I would appreciate any hints to understand those results.

Hobbymath's wanderings #5

Apéry's constant.

Collatz conjecture.

Chebyshev's bias.

Strong Law of Small Numbers.

Brahmagupta–Fibonacci identity.