ケンプナー関数（Kempner function）

ケンプナー関数

Wikipediaによるとケンプナー関数とは、

階乗 $s!$を$n$が割り切るとき$s$の最小値を与える関数である。例えば、$8$ならば、$ 1!,2!,3!$は8で割り切ることはできないが、$4!$は割り切ることができる。つまり$K(8)=4$である。

ケンプナー関数を実装する

といってもOEIS A002034にコードが紹介されていたのでそのまま使います。アルゴリズムは、

1. まず$n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k} (p_iは素数)$のように素因数分解する
2. 各々の素数のべき乗$p_i^{e_i} $に対して$K(p_i^{e_i})$を求める
3. $K(n)=max(K(p_1^{e_1}), K(p_2^{e_2}) \cdots K(p_k^{e_k}))$となる

プログラムは、

import sympy as sp
def valp(n, p):
    s = 0
    while n: n //= p; s += n
    return s
def K(p, e):
    if e <= p: return e*p
    t = e*(p-1)//p*p
    while valp(t, p) < e: t += p
    return t
def Kempner(N):
  return max(K(p, e) for p, e in sp.factorint(N).items())

N = 12345678
print(f"Kempner({N}) = {Kempner(N)}")

（開発環境：Google Colab）

この考え方は以下のProject Eulerの問題を解くのに役に立ちます

• Problem 549: Divisibility of Factorials
• Problem 320: Factorials Divisible by a Huge Integer