import itertools
import functools
# n以下の素数リスト
# エラトステネスのふるい
# 参考:http://q...content-available-to-author-only...a.com/neko_the_shadow/items/4ebad619564a48f5a97f
def primes(n):
plist = [i for i in range(n + 1)]
plist[0] = 0
plist[1] = 0
for p in plist:
if p == 0:
continue
if p * p > n:
return [p for p in plist if p != 0]
for a in range(2 * p, n + 1, p):
plist[a] = 0
# xとyが置換可能
def replaceable(x, y):
if sorted(str(x)) == sorted(str(y)):
return True
return False
N = 10000000
plist = primes(4000)
min = float('inf')
min_n = float('inf')
for l in itertools.combinations(plist, r = 2):
# nは選んだ2つの素数の積
n = int(l[0]) * int(l[1])
if n > N:
continue
# φ(n)
phi = (int(l[0]) - 1) * (int(l[1]) - 1)
if min > (n / phi) and replaceable(n, phi):
min = n / phi
min_n = n
print(min_n)
aW1wb3J0IGl0ZXJ0b29scwppbXBvcnQgZnVuY3Rvb2xzCgojIG7ku6XkuIvjga7ntKDmlbDjg6rjgrnjg4gKIyDjgqjjg6njg4jjgrnjg4bjg43jgrnjga7jgbXjgovjgYQKIyDlj4LogIM6aHR0cDovL3EuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEuY29tL25la29fdGhlX3NoYWRvdy9pdGVtcy80ZWJhZDYxOTU2NGE0OGY1YTk3ZgpkZWYgcHJpbWVzKG4pOgogICAgcGxpc3QgPSBbaSBmb3IgaSBpbiByYW5nZShuICsgMSldCiAgICBwbGlzdFswXSA9IDAKICAgIHBsaXN0WzFdID0gMAoKICAgIGZvciBwIGluIHBsaXN0OgogICAgICAgIGlmIHAgPT0gMDoKICAgICAgICAgICAgY29udGludWUKICAgICAgICBpZiBwICogcCA+IG46CiAgICAgICAgICAgIHJldHVybiBbcCBmb3IgcCBpbiBwbGlzdCBpZiBwICE9IDBdCgogICAgICAgIGZvciBhIGluIHJhbmdlKDIgKiBwLCBuICsgMSwgcCk6CiAgICAgICAgICAgIHBsaXN0W2FdID0gMAoKCiMgeOOBqHnjgYznva7mj5vlj6/og70KZGVmIHJlcGxhY2VhYmxlKHgsIHkpOgoKICAgIGlmIHNvcnRlZChzdHIoeCkpID09IHNvcnRlZChzdHIoeSkpOgogICAgICAgIHJldHVybiBUcnVlCgogICAgcmV0dXJuIEZhbHNlCgoKTiA9IDEwMDAwMDAwCnBsaXN0ID0gcHJpbWVzKDQwMDApCgptaW4gPSBmbG9hdCgnaW5mJykKbWluX24gPSBmbG9hdCgnaW5mJykKZm9yIGwgaW4gaXRlcnRvb2xzLmNvbWJpbmF0aW9ucyhwbGlzdCwgciA9IDIpOgogICAgIyBu44Gv6YG444KT44GgMuOBpOOBrue0oOaVsOOBruepjQogICAgbiA9IGludChsWzBdKSAqIGludChsWzFdKQogICAgaWYgbiA+IE46CiAgICAgICAgY29udGludWUKCiAgICAjIM+GKG4pCiAgICBwaGkgPSAoaW50KGxbMF0pIC0gMSkgKiAoaW50KGxbMV0pIC0gMSkKCiAgICBpZiBtaW4gPiAobiAvIHBoaSkgYW5kIHJlcGxhY2VhYmxlKG4sIHBoaSk6CiAgICAgICAgbWluID0gbiAvIHBoaQogICAgICAgIG1pbl9uID0gbgoKcHJpbnQobWluX24pCg==