自作巨大関数を解析する
はじめに
今回は自分が一番最初に作った巨大関数について考えていこうと思います。そこまで強い関数ではないはずですが、他の関数や表記とは異なる挙動を示すと思うので、解析をすることで今後の参考になればと思います。
この記事は、グーゴロジストの社交場というdiscordサーバーに書き込んだ際の議論を下敷きとしています。そのことを前提とした表現があるのでご注意ください。
定義
$x,y$は共に正の整数とする。
$$
f(x,y)=\begin{cases}
\frac yx&(x|yの時)\\
f(x+1,(y+1)^x)&(その他)
\end{cases}
$$
$$g(x)=f(2^x,1)$$
関数$f$は、帰納的定義にしては珍しく、二つの引数が共に増加します。停止性に関してはわかっていません。
また、各$x$に対して、$f(2^x,1)$が停止する際の一つ目の引数の値を調べると、次のようになりました。
| $x$ | 一つ目の引数 |
|---|---|
| $1$ | $9$ |
| $2$ | $27$ |
| $3$ | $27$ |
| $4$ | $27$ |
| $5$ | $99$ |
| $6$ | $99$ |
| $7$ | $243$ |
| $8$ | $539$ |
| $9$ | $539$ |
| $10$ | $2187$ |
| $11$ | $2187$ |
| $12$ | $5369$ |
| $13$ | $8737$ |
| $14$ | $18689$ |
| $15$ | $35927$ |
| $16$ | $66209$ |
| $17$ | $149669$ |
| $18$ | $275429$ |
| $19$ | $540857$ |
| $20$ | $1174019$ |
※
ソースコード
(python,C++)
(okkuuさんから頂いたコードを参考にしました。ありがとうございます！)
また、$f(2,1)$の二つ目の引数がどのように増加するかがOEISに登録されていたということを
喇さん
が言及していたので紹介しておきます。
https://oeis.org/A116944
停止性に関して
さて、停止性に関しては分かっていないと書きましたが、停止条件は次の通りになるはずです。
$x+1$の素因数がすべて$y+1$の素因数でもある$\Leftrightarrow x+1|(y+1)^x$
$(\Leftarrow)$は自明。
$(\Rightarrow)$
$x+1$の素因数がすべて$y+1$の素因数でもあるとする。この時、$x+1$を素因数分解したときの指数がすべて$x$以下であればこれは成り立つ。つまり、$x+1\leq2^x$である時、成立する。$x$は正の整数より、この不等式は自明。よって示された。
そして、この定理を使うと、次も示すことができます。
$(2^n+2,(y+1)^{2^n}+1),\cdots,(2^{n+1}+1,(y+1)^{2^n}+2^n)$の$2^n$個の組のうち、一つ目の素因数がすべて二つ目の素因数でもある組が存在する時、$f(2^n,y)$は停止する。
証明は省略しますが、$a$をよしなにして、$f$の一つ目の引数が$2^n+a$となった時、二つ目の引数を因数分解すると$(y+1)^{2^n}+a-1$が因数となるということを根拠としています。
さて、定理2が成り立つということは、次の予想が証明できればこの問題は解決するのでは？と思うかもしれません。
任意の$n\in\mathbb N$において、差が$n$である正の整数の組$(x,y)\in\mathbb N^2$の内、$x$の素因数がすべて$y$の素因数でもあるものが存在する。
しかし、$a^{2^n}+1$は$a+1$を因数として持たないため、$f$の一つ目の引数が$2^n+1$から$2^n+2$になる時は定理2は使えません。そのため、この方法では停止性は証明できません。
また、定理2は停止するときの十分条件なので、そのほかの場合でも停止する場合があります。そちらの方も考えてはみたいですが、巨大関数ということもあり、あまりに指数が大きく複雑になるので、また今度とさせてください。
おわりに
自作の巨大関数の停止性を証明しようと思いましたができませんでした。しかし、その中で停止条件を見つけることができました。もし停止性に関していいアイデアがある方がいらっしゃったら、お知らせください。
