Totient permutation
Problem 70
Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
# https://en.wikipedia.org/wiki/Euler%27s_totient_function
# https://codegolf.stackexchange.com/questions/26739/super-speedy-totient-function/26753#26753
def totient_gen(limit):
phi = (limit + 1) * [0]
phi[1] = 1
yield 1
for n in range(2, limit):
if phi[n] == 0:
phi[n] = n - 1
for j in range(2, int(limit / n)):
if phi[j] != 0:
q = j
f = n - 1
while q % n == 0:
f *= n
q //= n
phi[n * j] = f * phi[q]
yield phi[n]
def run(limit=10000000):
min_ratio = 10 # big initial value
n = 0
min_min_ratio = 100
number = 0
for phi in totient_gen(limit):
n += 1
if n / phi < min_ratio:
if sorted(str(phi)) == sorted(str(n)):
if n > 1:
new_min_ratio = n / float(phi)
if new_min_ratio < min_min_ratio:
min_min_ratio = new_min_ratio
number = n
return number