ケンプナー関数

数論において、ケンプナー関数（けんぷなーかんすう、英: Kempner function） $S(n)$ ^[1] は正整数 $n$ について定義される関数である。

定義

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

この関数は、素数においては一次関数的に成長し、階乗数では対数関数的成長を見せる、一貫性がない成長率（英語版）をもつ。

歴史

ケンプナー関数は、1883年、リュカによって初めて言及された^[2]。その後は、1887年のヨーゼフ・ノイベルグのジャーナルにも見られた^[3]。1918年、オーブリー・J・ケンプナー（英語版）が最初に正しい計算アルゴリズムを与えた^[1]。

1980年にスマランダチェが再発見したことからスマランダチェ関数（Smarandache function）とも呼ばれる^[1]。

性質

$n!$ は $n$ を約数に持つため、 $S(n)$ は常に $n$ より小さい。 $n$ が4より大きい素数であることと $S(n)=n$ が成り立つことは同値である^[1]。つまり $S(n)$ ができるだけ大きくなるとき $n$ は素数である。逆に、できるだけ小さくする場合は $n$ を階乗数にすればよい（ $k\geq 1$ について $S(k!)=k$ となる）。

$S(n)$ は係数が整数である、出力された整数値がすべて $n$ で割り切れるモニック多項式の最小次数となる。例えば $S(6)=3$ について、以下の三次関数が出力する整数値は6で割り切れる（6を法として0である）。 $x(x-1)(x-2)=x^{3}-3x^{2}+2x,$ しかし二次また一次のモニック多項式で、その出力された整数値が常に6で割り切れるものは存在しない。

ほとんどすべての整数 $n$ （漸近密度（英語版）が0という意味）で、 $S(n)$ が $n$ の最大の素因数と一致する事がエルデシュによって指摘された^[4]。この問題は1911年にThe American Mathematical Monthly（英語版）で発表され1994年に解決された。

計算複雑さ

任意の整数 $n$ のケンプナー関数 $S(n)$ は、 $n$ の素因数の素数冪 $p^{e}$ の中で、 $S(p^{e})$ の最大値である。 $n$ が $p^{e}$ 自身であるとき、そのケンプナー関数は、 $p$ の倍数の中でその階乗の約数が $p$ の十分な倍数を持つものを見つける、という手順程度の計算時間量（英語版）で見つけられる。同様のアルゴリズムを任意の $n$ に拡張すると、 $n$ のそれぞれ素因数で、 $p^{e}$ と同様の手順を行い、最も大きい値が $S(n)$ の値となる。

素数 $p$ と $p$ より小さい $x$ で、 $n=px$ と表せるとき $S(n)$ は $p$ である。したがって、半素数のケンプナー関数の計算は、その素因数分解と同等の難しさであることを示唆している。より一般的に、 $n$ が合成数ならば、 $S(n)$ を繰り返し評価して $n$ が素因数分解できたとしても、 $S(n)$ と $n$ の最大公約数は非自明である。ゆえに、ケンプナー関数の計算は一般的に、素因数分解より簡単でない。