Euler #70

def factorize(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = int(n/2)
    for b in range(3, int(n**0.5) + 1, 2):
        while n % b == 0:
            n = int(n/b)
            factors.append(b)
    if n > 2:
        factors.append(int(n))
    return set(factors)


def totient(n):
    coprimes = n
    for x in factorize(n):
        coprimes *= (1-(1/x))
    if sorted(str(int(coprimes))) == sorted(str(n)):
        return coprimes
    return 1

bestratio, best = 10**10, 0
for y in range(2, 10**7):
    print(y)
    if y/totient(y) < bestratio:
        bestratio = y/totient(y)
        best = y
print(best)