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.
