ケンプナー関数

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

定義

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

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


$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28
$S(n)$	0,1	2	3	4	5	3	7	4	6	5	11	4	13	7	5	6	17	6	19	5	7	11	23	4	10	13	9	7

歴史

ケンプナー関数は、1883年、リュカによって初めて言及された^[4]。その後は、1887年のヨーゼフ・ノイベルグのジャーナルMathesisにも見られた^[5]。1918年、オーブリー・J・ケンプナーが最初に正しい計算アルゴリズムを与えた^[1]。またケンプナーは $S(1)=0$ としている。

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

性質

$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$ の最大の素因数と一致する事がエルデシュによって指摘された^[9]。この問題は1911年にThe American Mathematical Monthly（英語版）で発表され1994年に解決された。

Tutescuは $S(n)\neq S(n+1)$ と予想している^[10]。

4以上の整数 $x$ について、素数計数関数とガウス記号とケンプナー関数について以下の式が成り立つ。

$\pi (x)=-1+\sum _{k=2}^{x}\left\lfloor {\frac {\mu (k)}{k}}\right\rfloor$

計算複雑さ

任意の整数 $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$ の最大公約数は非自明である。ゆえに、ケンプナー関数の計算は一般的に、素因数分解より簡単でない。

級数

ケンプナー関数に関する級数には以下のようなものがある^[11]^[12]^[13]^[14]^[15]。総じてスマランダチェ定数（ドイツ語版）と呼ばれる。

$\sum _{n=2}^{\infty }{\frac {1}{S(n)!}}=1.09317\ldots$

$\sum _{n=2}^{\infty }{\frac {S(n)}{n!}}=1.71400629359162\ldots$ （無理数であることが知られている）

$\sum _{n=2}^{\infty }{\frac {1}{\prod _{i=2}^{n}S(i)}}=0.719960700043\ldots$

$\sum _{n}S(n)^{-\alpha }{S(n)!}^{-1/2}<\infty ,\,{\text{ con }}\alpha >1.$

類似物

Pseudosmarandache Function

Pseudosmarandache Function $Z(n)$ は、 $s$ 番目の三角数が $n$ を割り切るとき、最小の $s$ を出力する関数である^[16]^[17]。以下のような性質を持つ。

${\sqrt {n}}<Z(n)\leq 2n-1$
$Z(n)\leq n-1$ （奇数の場合）
$Z(2^{k})=2^{k+1}-1\,$
$n$ についての方程式 ${\frac {n}{Z(n)}}=k\;(k\in \mathbb {Z} ,k\geq 2)$ は無限個の解を持つ。
$\sum _{n=1}^{\infty }{\frac {1}{Z(n)^{\alpha }}}$ は $\alpha >1$ ならば収束する。
${\frac {Z(n+1)}{Z(n)}},{\frac {Z(n-1)}{Z(n)}},{\frac {Z(2n)}{Z(n)}}$ は発散する。

Smarandache-double factorial Function

Smarandache-double factorial Function $\mathrm {Sdf} (n)$ は $s!!$ （二重階乗）が $n$ を割り切るとき、最小の $s$ を出力する関数である^[18]。

Smarandache Near-to-Primorial Function

Smarandache Near-to-Primorial Functionは、 $s\#$ （素数階乗）または $s\#\pm 1$ のいずれかが $n$ を割り切るとき、最小の $s$ を出力する関数である^[19]。

スマランダチェ-ワグスタッフ関数

スマランダチェ-ワグスタッフ関数（Smarandache-Wagstaff Function） $\mathrm {Sw} (n)$ は1から $s$ 番目までの階乗数の和が $n$ を割り切るとき、最小の $s$ を出力する関数である^[20]。0から $s$ 番目までとしたものはスマランダチェ-クレパ関数（Smarandache-Kurepa Function）と呼ばれる^[21]。

Smarandache Ceil Function

Smarandache Ceil Function $S_{k}(n)$ は、 $s^{k}$ が $n$ を割り切る最小の整数 $s$ を出力する関数である^[22]。 $k=1$ では、 $S_{1}(n)=n$ である。

$x^{k}\equiv 0\quad (\mathrm {mod} \ n)$ の解の個数を $M_{k}(n)$ として $S_{k}(n)={\frac {n}{M_{k}(n)}}$ としても表される。

出典

^ ^a ^b ^c ^d Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see Sloane, N.J.A. (ed.). "OEIS (home page)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 2024年7月6日閲覧。
^ “Polynomial analogue of the Kempner function”. arXiv. 2024年7月6日閲覧。
^ “A Faster Algorithm For Testing Polynomial Representability Of Functions Over Finite Integer Rings”. arXiv. 2024年7月6日閲覧。
^ Lucas, E. (1883). “Question Nr. 288”. Mathesis 3: 232.
^ Neuberg, J. (1887). “Solutions de questions proposées, Question Nr. 288”. Mathesis 7: 68–69.
^ Weisstein, Eric W.. “Smarandache Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。
^ “Properties and Problems related to Smarandache Type Functions”. arXiv. 2024年7月6日閲覧。
^ “SMARANDACHE FUNCTION”. R. Muller. 2024年7月6日閲覧。
^ Erdős, Paul; Kastanas, Ilias (1994). “The smallest factorial that is a multiple of $n$ (solution to problem 6674)”. The American Mathematical Monthly 101: 179. doi:10.2307/2324376. JSTOR 2324376. .
^ I. Prodanescu, L. Tuțescu (2000). On A Conjecture Concerning The Smarandache Function
^ I.Cojocaru and S. Cojocaru (1996). “The First Constant of Smarandache”. Smarandache notions journal (vol 7). https://fs.unm.edu/SNJ7.pdf.
^ E. Burton (1995). “On Some Series Involving the Smarandache Function”. Smarandache Function Journal vol 6. https://fs.unm.edu/SFJ6.pdf.
^ “A048799 - OEIS”. oeis.org. 2024年7月6日閲覧。
^ “A048834 - OEIS”. oeis.org. 2024年7月6日閲覧。
^ “A048835 - OEIS”. oeis.org. 2024年7月6日閲覧。
^ Weisstein, Eric W.. “Pseudosmarandache Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。
^ “A011772 - OEIS”. oeis.org. 2024年7月6日閲覧。
^ “A007922 - OEIS”. oeis.org. 2024年7月6日閲覧。
^ Weisstein, Eric W.. “Smarandache Near-to-Primorial Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。
^ Weisstein, Eric W.. “Smarandache-Wagstaff Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。
^ Weisstein, Eric W.. “Smarandache-Kurepa Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。
^ Weisstein, Eric W.. “Smarandache Ceil Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

参考文献

Kenichiro Kashihara　COMMENTS AND TOPICS ON SMARANDACEE NOTIONS AND PROBLEMS
SMARANDACHE NOTIONS JOURNAL vol7,vol8,vol9,vol10,vol11,vol12,vol13

この記事は、クリエイティブ・コモンズ・ライセンス表示-継承 3.0 非移植のもと提供されているオンライン数学辞典『PlanetMath』の項目Smarandache functionの本文を含む

[oeis-1] Called the Kempner numbers in the Online Encyclopedia of Integer Sequences: see Sloane, N.J.A. (ed.). "OEIS (home page)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 2024年7月6日閲覧。

[2] “Polynomial analogue of the Kempner function”. arXiv. 2024年7月6日閲覧。

[3] “A Faster Algorithm For Testing Polynomial Representability Of Functions Over Finite Integer Rings”. arXiv. 2024年7月6日閲覧。

[history1-4] Lucas, E. (1883). “Question Nr. 288”. Mathesis 3: 232.

[history2-5] Neuberg, J. (1887). “Solutions de questions proposées, Question Nr. 288”. Mathesis 7: 68–69.

[6] Weisstein, Eric W.. “Smarandache Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[7] “Properties and Problems related to Smarandache Type Functions”. arXiv. 2024年7月6日閲覧。

[8] “SMARANDACHE FUNCTION”. R. Muller. 2024年7月6日閲覧。

[9] Erdős, Paul; Kastanas, Ilias (1994). “The smallest factorial that is a multiple of $n$ (solution to problem 6674)”. The American Mathematical Monthly 101: 179. doi:10.2307/2324376. JSTOR 2324376. .

[10] I. Prodanescu, L. Tuțescu (2000). On A Conjecture Concerning The Smarandache Function

[11] I.Cojocaru and S. Cojocaru (1996). “The First Constant of Smarandache”. Smarandache notions journal (vol 7). https://fs.unm.edu/SNJ7.pdf.

[12] E. Burton (1995). “On Some Series Involving the Smarandache Function”. Smarandache Function Journal vol 6. https://fs.unm.edu/SFJ6.pdf.

[13] “A048799 - OEIS”. oeis.org. 2024年7月6日閲覧。

[14] “A048834 - OEIS”. oeis.org. 2024年7月6日閲覧。

[15] “A048835 - OEIS”. oeis.org. 2024年7月6日閲覧。

[16] Weisstein, Eric W.. “Pseudosmarandache Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[17] “A011772 - OEIS”. oeis.org. 2024年7月6日閲覧。

[18] “A007922 - OEIS”. oeis.org. 2024年7月6日閲覧。

[19] Weisstein, Eric W.. “Smarandache Near-to-Primorial Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[20] Weisstein, Eric W.. “Smarandache-Wagstaff Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[21] Weisstein, Eric W.. “Smarandache-Kurepa Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[22] Weisstein, Eric W.. “Smarandache Ceil Function” (英語). mathworld.wolfram.com. 2024年7月6日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]