Thursday, April 30, 2015

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).

Tuesday, April 14, 2015

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.