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

from Crazy import primes
def permutation(n,m):
    return sorted(str(n))==sorted(str(m))
def p70():
    x=primes(10000)
    t,s=0,3
    xa=[]
    for i in x:
        for j in x:
            if j<i:
                continue
            if permutation(i*j,(i-1)*(j-1)) and i*j/((i-1)*(j-1))<s:
                print(i,j)
                t,s=i*j,i*j/((i-1)*(j-1))
                xa.append(i*j)
            if i*j>10**7:
                break
        if i*i>10**7:
            break
    return t
print(p70())
