マッカーシーの91関数は $101$ 以下の整数が与えられたとき必ず $91$ を返す関数として有名ですが、ふと返す整数を自由に変えられたらいいのになと思いました。あ、もちろん定数関数とか簡単な関数じゃなくてですよ。
この記事では何か意味ありげなんだけど実はある条件下では指定した整数を返すような関数をつくる過程で得られた知識をご紹介します。なお本記事では厳密な証明は省略します。
まずは成果物
とりあえず、成果物をば。
おぉ！ものの見事に（ほぼ）全てFになってますね！
それではこの関数のからくりについて順に追って見ていきましょう！
マッカーシーの91関数の定義
良く知られているマッカーシーの91関数（McCarthy 91 function）の定義は
f(x) = \begin{cases}
x - 10 & (x > 100) \\
f(f(x+11)) & (otherwise)
\end{cases}
となっています。
この関数が返す値は先述の通り、$x \leq 101$ のとき $91$ です（$x > 101$ のときは $x - 10$ を返します）。
実際にその通りになっているのか？
手計算で確かめるのは大変なのでプログラムを書いてみましょう。
f = ->x{x>100 ? x-10 : f[f[x+11]]}
さて、いかがでしょう。見事に $91$ が続いていますね！
これはこれで面白いのですが、任意の整数が出せるようになったらもっと面白くなると思いません？
それでは、任意の整数を返せるように準備をしていきます。
まずはマッカーシーの91関数の定義について見ていきましょう。このままでは扱いにくいので、次のようなより扱いやすい等価な関数に変形します。
f(x) = \begin{cases}
x - 10 & (x > 100) \\
f^{\circ91}(x+901) & (otherwise)
\end{cases}
なお、$f^{\circ91}$ は合成冪で
f^{\circ91}(x) = (\underbrace{f \circ \cdots \circ f}_{91 \ times})(x) =\underbrace{f(f( \cdots f(}_{91 \ times}x\underbrace{) \cdots ))}_{91 \ times}
といった意味になります。
プログラムにするとこんな感じですかね。
f = ->x{x>100 ? x-10 : 91.times.reduce(x+901){|r,_|r=f[r]}}
はい！はじめに定義した関数の戻り値と同じ結果になりましたね！
Donald E. Knuth によるマッカーシーの91関数の一般化
と少し大げさな節タイトルですが、ようはマジックナンバーを変数に置き換えただけです。定義は次の通りになります。
\begin{eqnarray}
g(x) = \begin{cases}
x-b & (x>a) \\
g^{\circ c}(x+d) & (otherwise) \\
\end{cases}\\
ただし，a は任意の整数，b, c, dは任意の自然数．
\end{eqnarray}
また、 $(c-1)b<d$ を満たすときこの関数は
g(x) = \begin{cases}
x-b & (x>a) \\
g(x+d-(c-1)b) & (otherwise) \\
\end{cases}\\
と合成冪を含まない関数に変形できます。
さらにこの関数はより簡単な
g(x) = \begin{cases}
x-b & (x>a) \\
a+d-cb-((a-x) \ mod \ (d-(c-1)b)) & (otherwise) \\
\end{cases}\\
といった closed-form に変形できます。
ここまでくると、与えた整数を任意の整数に変換する関数、すなわち ぼくのかんがえたさいきょうの$N$関数 が作れますね！
ぼくのかんがえたさいきょうのN関数
ぼくのかんがえたさいきょうのN関数 を作るために、新たな条件 $d-(c-1)b=1$ を付けたします。すると closed-form な一般化マッカーシーの91関数の法（$mod$ の後ろの数字）は $1$ 、つまり $(a-x) \ mod \ 1=0$ なので、
g(x) = \begin{cases}
x-b & (x>a) \\
a+d-cb & (otherwise) \\
\end{cases}\\
と、最初の定義はどこへやら。ものすごーく簡単な形になりました。
さらに新しい条件により、条件 $(c-1)b<d$ は
\begin{eqnarray}
& & (c-1)b<d \ \cap \ d-(c-1)b=1 \\
\iff & & (c-1)b<(c-1)b+1 \\
\iff & & 0 < 1
\end{eqnarray}
と自明な条件になったので、省略できることが分かりました。
これで全ての準備が整いました。条件を整理してみましょう！
ぼくのかんがえたさいきょうのN関数の定理
$a$ を任意の整数，$b, \ c$ を任意の自然数とする．任意の整数 $x$ に対し次の関数 $h(x)$ は $x>a$ のとき $N=a-b+1$ となる．
h(x) = \begin{cases}
x-b & (x>a) \\
h^{\circ c}(x+(c-1)b+1) & (otherwise) \\
\end{cases}\\
ぼくのかんがえたさいきょうのF関数
さて、冒頭で見せた（ほぼ）すべてがFになる関数のタネあかしです。
この関数を数式で表すと
f(x) = \begin{cases}
x-86 & (x > 100) \\
f^{\circ1919}(x+164949) & (otherwise)
\end{cases}
で、パラメータは $(a, \ b, \ c, \ d) = (100, \ 86, \ 1919, \ 164949)$ なので、きちんと $d-(c-1)b=(164949-(1919-1)86)=1$ を満たしており、$x \leq a = 101$ のとき $N=a-b+1=100-86+1=15=(f)_{16}$ となることが分かります。
マッカーシーの91関数っぽくこのf関数を表すなら
f(x) = \begin{cases}
x-86 & (x > 100) \\
f(f(x+87)) & (otherwise)
\end{cases}
になりますかね。
いやー、これであなたの考える最強のN関数が作れますね！