【Project Euler】Problem 69: ファイ関数の最大値

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

問題：ファイ関数の最大値

原文 Problem 69:Totient maximum

問題の要約：　$n\leqq 10^6$ で $n/φ(n)$が最大になる$n$を求めよ

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

from sympy.ntheory import totient
N, npmax = 10**6, 0
for n in range(1,N+1):
  np = n / totient(n)
  if np > npmax:
    npmax, npmaxN = np, n
print(npmaxN, npmax)

そこで以下のファイ関数の定義に従って考えてみたいと思います。$n$の素因数を$p_k$とすると

$\displaystyle φ(n) = n \prod_{i=1}^{k}(1-\frac {1}{p_i}) =
n(1-\frac {1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})
$

従って

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

これを最大化するということは、以下のような条件が必要と思われます。

• なるべく小さな素因数を選ぶ
• １つの素因数は1回のみ使う（ファイ関数は2回以上同じ素因数を使っても変わらない）

従ってアルゴリズムはこのようになります。Pythonのコードも載せましたが、電卓でも計算できそうですね。

• 素数を小さい順に掛けていって$10^6$以下の最大値を求める。

from sympy import  nextprime
N = 10**6
p, n1, phi = 2, 2, 1
while n1 < N:
  n = n1
  phi *= p-1
  p = nextprime(p)
  n1 *= p 
print(f"n = {n}, phi = {phi}, n/phi = {n/phi}")