【Project Euler】Problem 70: アナグラムのファイ関数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題：アナグラムになるファイ関数の最小値

原文 Problem 70:Totient permutation

問題の要約：　$1<n<10^7$、$φ(n)$が$n$のアナグラムになるもので $n/φ(n)$が最小になる$n$を求めよ

ここでいうアナグラムとは元の数字を並べ替えて同じになるもので、例として$φ(87109)=79180$があげられています。

これを素直にインプリすると、以下のようになりますがPythonでは約20分かかってしまいました。

from sympy.ntheory import totient

def isPermSame(n1,n2):
  return sorted(str(n1)) == sorted(str(n2))

npmin, npminN = 99999, 0
for n in range(2,10**7):
  phi = totient(n)
  if isPermSame(n, phi):
    np = n/phi
    if np < npmin:
      npmin, npminN = np, n
print(f"n = {npminN}, n/phi = {npmin}")

そこで前回のように ファイ関数の定義に戻ると$n/φ(n)$は、

$\displaystyle n/φ(n) = \frac{p_1}{p_1-1}*\frac{p_2}{p_2-1}*...*\frac{p_k}{p_k-1}$

なのでなるべく小さくするには前回と逆で、

• なるべく大きな素因数を選ぶ
• 素因数の数は少ないほど良い。ただし素数のように素因数が１つの時は$φ(n)=n-1$となりアナグラムにならないので、素因数の数が2つの物がが候補となる。

従ってアルゴリズムは以下のようになります。

• $\sqrt 10^7$の前後ある幅の素数をリストする。
• そこから2つの組み合わせを選んで$φ(n)$がアナグラムかチェックして$n/φ(n)$が最小となる$n$を探す

これをインプリしたコードです。2つの素数は$\sqrt 10^7$が約3162なので[2000,4000]で選びました。実行時間は1秒未満です。

import itertools
from sympy import primerange

N = 10**7
pl = list(primerange(2000,4000))
npmin, npminN = 99999, 0
for (p1,p2) in itertools.combinations(pl,2):
  if p1*p2 > N: continue
  n, phi = p1*p2, (p1-1)*(p2-1)
  if isPermSame(n, phi):
    np = n/phi
    #print(p1, p2, n, phi, n/phi)
    if np < npmin:
      npmin, npminN = np, n
print(f"n = {npminN}, n/phi = {npmin}")