【くどー問題】 理論的にわかること

はじめに

本記事では「くどー問題」を扱います。くどー問題の内容、および本記事で用いられる表記については以下をご参照ください（項目をクリックすると展開されます）

${}$
また、関連記事にRefs.kudoprob_01kudoprob_02kudoprob_03kudoprob_04があります。

数値計算でわかること

本記事では「くどー問題」の理論的な解析に関して述べます。その前に本章では数値計算からわかっていることを記します。そしてこれらの事実を理論的な観点からどれだけ説明できるかを示します。

まず現在のところ、$3\le n\le 10000$において、最後まで削除可能な$n$は$n=3,6$しか見つかっていません。

図1が$3\le n\le 10000$に対する$\mathrm{mmax}(n)$のグラフです（$\mathrm{mmax}$に関しては「表記」の項目参照のこと）：

$n$ vs $\mathrm{mmax}(n)$のグラフ。青い点は計算が終わっているデータ。黄色い三角は計算が終わっておらず、$\mathrm{mmax}(n)$の下限値を示している。緑の直線は$\mathrm{mmax}(n)=n-2$であり、これにデータが乗ればその数は最後まで削除可能。

黄色い三角の点は計算量が多くなるため計算が未完了な$n$に関する$\mathrm{mmax}(n)$の下限です。緑の線は$\mathrm{mmax}(n)=n-2$です。これにデータが乗ればその$n$は最後まで削除可能です。上の図のデータにアクセスできるインタラクティブな図は以下です：

この図は拡大・縮小することができ、データ点にカーソルを合わせると$(n,\mathrm{mmax}(n))$が表示されます。また、削除列に関する特徴の解説が 「くどー問題」再び の「$\mathrm{Delete}(n;m)$の$m$依存性」の章にあるのでご参照ください。

これらのデータから明らかにわかることが4つほどあります：

1.2.は上に挙げた図から、3.4.は削除列を見ることでわかります。以下これらを（ある程度）理論的に説明します。

理論的にわかること

m=1,2で削除できる数に関して

$m=1,2$で削除可能な数に関して考察します。

$n$を4で割った余りで分類します。このとき以下が示せます：

1.2.は具体的に代入すればすぐに証明できますし、3.4.も簡単にわかると思います。

ここで$n$が大きい時、

【仮定1】 $m=1$ではほとんどの場合$n/2$ or $(n+1)/2$しか削除できない
【仮定2】 上に示した$n=4k+2,4k+3$における$m=1,2$の削除列は殆どの場合途切れ、$m=3$では削除可能な数字が存在しない

を仮定します。公式1および【仮定1】【仮定2】は
\begin{align} \mathrm{mmax}(n)=0,0,2,2,0,0,2,2,\ldots \ \ \ \ \mathrm{for\ large\ }n \end{align}
という、数値計算でわかっている振る舞いを導きます。

【仮定1】【仮定2】が成立する理由は今のところちゃんとはわかっていません。ただしわかっていることもあります。【仮定1】に関連し、Y.K.さんの以下の証明が存在します：

これらの仮定に関してはもうすこし考察の必要がありそうです。

「数値計算からわかる事実」の2.4.に関して

本章では、前記した「数値計算からわかる事実」の2.4.が密接に関連しており、説明が可能であることを述べます。すなわち$\mathrm{mmax}(n)\simeq n/2$となる一群の$n$の存在と削除列に連続した整数が並ぶことの関係とその説明を与えます。

前回の記事 でY.K.さんに教えて頂いたくどー問題の数値計算法に関して説明しました。実はこの方法で計算すると、$d_m$と$k_m^{(\mathrm{diff})}$の間に著しい特徴があることに気付きます（記号の意味に関しては「表記」参照のこと）。例えば$n=1322$の削除列の最初の方を見てみましょう：

      #########
n: 1322
- m: 1
(diffk,list_d): [(331, [661])]
- m: 2
(diffk,list_d): [(32, [661, 32]), (331, [661, 662])]
- m: 3
(diffk,list_d): [(33, [661, 32, 33])]
- m: 4
(diffk,list_d): [(34, [661, 32, 33, 34])]
- m: 5
(diffk,list_d): [(35, [661, 32, 33, 34, 35])]
︙
##########
    

丸括弧内の最初の数値は$k_m^{(\mathrm{diff})}$です。$k_m^{(\mathrm{diff})}$の隣の角括弧の中の数字が削除列です。$m=1$で削除可能な数は$661$のみです。$m=2$では削除可能な数が2つ、$32$と$662$が存在します。削除列$[661,662]$の次に削除できる数字が存在しないため、$m=3$では削除列は1つに戻ります。

この結果を見ると
\begin{align} k_{m}^{(\mathrm{diff})}=d_{m} \end{align}
が$m=2$の1つ目の削除列で成立し、その後ずっとこの関係が保たれるという著しい特徴があることがわかります。実はある程度$\boldsymbol{\mathrm{mmax}(n)}$が大きくなる$\boldsymbol{n}$では、多くの場合、$\boldsymbol{m=2,3,4}$のどれかからこの関係が成立する削除列が存在します。その理由は以下の事実によります：

定理1からわかるのは、ある$m$で$k_m^{(\mathrm{diff})}=d_m$が成立するなら、($m+1$)回目の削除では$d_{m+1}=d_m+1$が削除可能であり、かつ$k_{m+1}^{(\mathrm{diff})}=d_{m+1}$が成立するということです。これが削除列に連続した整数が存在する理由かと思います。公式1が成立することは
\begin{align} k_m-(a+1)^2=k_{m-1}+a-(a+1)^2=k_{m-1}-a^2-(a+1)\\ =S_{m-1}-a-(a+1)\\ \therefore \frac{k_m-(a+1)^2}{S_m-(a+1)}=\frac{S_{m-1}-a-(a+1)}{S_{m-1}-a-(a+1)}=1 \end{align}
からすぐにわかります。

さらにこのことから$\mathrm{mmax}(n)\simeq n/2$となる一連の$n$が存在することもわかります。なぜなら$\mathrm{mmax}$が大きくなる$n$に関して$n/2$ or $(n+1)/2$は多くの場合最初に削除されてしまっているので、$d$がこの値まで到達すると連鎖が途切れるからです。

また、たとえ最初に$n/2$ or $(n+1)/2$が削除されていなかったとしても、最初に$k_m^{(\mathrm{diff})}=d_m$が成立する$d_m$が$m$より2以上大きいなら、すべての数字が削除されることはなく、この削除列は必ず途切れます。すなわちこのような削除列はそれ単独で最後の数字まで削除できるということはないです。

ちなみに最後まで削除可能な$n=3,6$における$d$と$k^{(\mathrm{diff})}$は以下のようになります:
\begin{align} n=3: & \ d_1=2, k_1^{(\mathrm{diff})}=1\\ n=6: &\ d_1=3, k_1^{(\mathrm{diff})}=2\\ &\ d_2=4, k_2^{(\mathrm{diff})}=2\\ &\ d_3=5, k_3^{(\mathrm{diff})}=0\\ &\ d_4=2, k_4^{(\mathrm{diff})}=6\\ \end{align}
これらの$n$では$d_m=k_m^{(\mathrm{diff})}$が成立することはないです。

計算が終わってない$n$におけるinf(mmax)の改善

前章の考察から、計算が重く探索の終わっていない$n$（図1の黄色い三角の点）の$\mathrm{mmax}$の下限を改善することができます。

上記した$n=1322$の削除列の連続した整数がどこまで続くか考えると、$661$が最初に削除されているため$660$まで続いて途絶えます。ということは、この削除列は$m=660-32+2=630$まで続くことになります。これは$\mathrm{mmax}$の下限です。これ以外の系列の削除列が存在する可能性はありますし、$n=1322$では実際存在します。

このようにして計算が終わっていない$n$に対して$\mathrm{mmax}$の下限を改善した図が以下です：

図1において、理論的な考察から計算が未完了のデータ（黄色い三角の点）の$\mathrm{mmax}(n)$の下限の改善を行ったもの

対応するインタラクティブなグラフは以下です：

計算の終わってない$n$のうちひとつだけ、$n=1456$の$\mathrm{mmax}$の下限に関しては、理論的な考察よりも現在完了している数値計算による下限の方が大きな値を与えます。

まとめ

本記事では、くどー問題に関して理論的にわかっていることを述べました。$\mathrm{mmax}(n)$が$n$の大きいところで$0,0,2,2,0,0,2,2,\ldots$という繰り返しの構造を持つこと、削除列が連続した整数から構成されること、さらに$\mathrm{mmax}(n)\simeq n/2$となる一群の$n$が存在する理由に関して（大雑把に）説明を与えました。

ここまで行った考察以外に、理論的にも数値的にもできることとして、「逆方向の探索」があります。これは$\{1,n\}$から始め、「3乗和/1乗和が整数となる」ように数を追加していく方法です。コメント欄でtanuさんにご指摘頂いたのですが、これを考察すると、順方向の探索において「最後まで残しておかなければならない数」（＝「追加する数の列」の全てに共通して存在する数）が見つかるかもしれません。順方向の探索でどの削除列にもこの数が存在するなら、その$n$において最後まで削除することは不可能です。特に数値計算が重くなる$n$に対してこの考察をすることは有益かと思います。

おしまい。${}_\blacksquare$