#Project Euler Question 70
#Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

import math

def pf_set(x):
    sieve = [True] * (x+1)
    for n in range(3, int(math.sqrt(x)+1), 2):
        if (sieve[n]):
            for i in range(n*n, x+1, 2*n):
                sieve[i] = False
    prime_list = [2] + [n for n in range(3, x+1, 2) if sieve[n]]
    return (prime_list)


def prime_dic(x):
    prime_list = pf_set(x)

    prime_map = {}
    lastprime = 'REMOVE ME'

    for x in prime_list[::-1]:
      prime_map[x] = lastprime
      lastprime = x

    del prime_map[prime_list[-1]]

    return prime_map

def prime_fact(x, prime_list):
    factors = set()
    n = x
    factor = prime_list[2]
    while factor * factor <= n:
        if n % factor == 0:
            factors.add(factor)
            n //= factor
        else:
            factor = prime_list[factor]
    if n in prime_list:
        factors.add(n)
        return factors
    return {2}

def func_pf(x):
    prime_list = prime_dic(x)
    smallest_nun = 2
    largest_n = 0
    largest_un = 0
    for n in range(3, x+1, 2):
        if n in prime_list:
            continue
        pf1 = prime_fact(n, prime_list)
        un = n
        for f in pf1:
            un = int(un * (1 - 1/f))
        if sorted(str(n)) != sorted(str(un)):
            continue
        nun = n / un
        if nun < (smallest_nun):
            smallest_nun = nun
            largest_n = n
            largest_un = un
    return largest_n
            
print(func_pf(10000000))