コラッツ予想と２進数列ビット長の有界性について

はじめに

いなばなつきさんの『 有界予想 』に触発されて、２進法で有界性について考えてみました。

２進３倍繰上げルール

コラッツ予想を２進法で考える、っていう過去２つの私の記事を読んでくださったみなさん、ありがとうございます。
まだご覧いただいていない方、リンク貼っときますのでよかったらご笑覧ください。

コラッツ予想と２進法
コラッツ予想を２進法で探求するための準備

要するに何が言いたいかっていうと、

• コラッツ予想で出てくる数列を２進法でゼロイチ表示をモノクロ表示すると見やすくていいね。
• さらに、”２で割る”のをやめて、”３n＋１” の ”＋１” を、”最下位ビットの繰上げ” で代用すると、いろいろと面白い性質が見えて来るよ。

って感じですかね。
２つめの『・』で言ってるやり方を『２進３倍繰上げルール』って勝手に呼んでます。（もっと適切な言い回しがあればご教示ください。）

とりあえず、『２進３倍繰上げルール』で、悪名高き『初期値２７』について、その変化を図示します。
白は”０”、黒は”１”を表してます。

悪名高き『初期値２７』

初期値１０進法の２７って、２進法だと”１１０１１”ですね。
図の一番上の段、”１１０１１”から始まって、
２段目、”３×２７＋１＝８２”で２進法だと”１０１００１０”になってます。
そのまま２段目、最下位の”０”を無視すれば、”１０１００１”って、１０進法の８２を２で割った”４１”ってわけです。
以下、”３倍して右端の黒を繰り上げる”って操作を繰り返すことで、左右両端が黒のビット列が得られますが、それを１０進法に直すと”コラッツ変換の奇数列”が得られる、って寸法です。

初期値２７って、コラッツの手順で計算を繰り返すと、最大で９２３２なんていう馬鹿でかい数になって、電卓叩いていると不安になるんですよね。でも、そのうち２で割れることが増えてきて、『な〜んだ、やっぱり１になるじゃん』で終わるんですけど。

これをじーっと眺めていると、直角二等辺三角形の形に黒いやつが並んているところ、何ヶ所かありますよね。
これって、”３n＋１”をした次、”２で割る”ことは１回しかできないよ、ってことを表してるんですね。
これも私、勝手に『黒三角の定理』って呼んでますけど、何かいい呼び方、どなたかご提案ください。
(^_^;)

ビット長の変化について

ようやく本題。

コラッツの手順で計算を繰り返していると、”２で割る”が１回しかできなかったり、いきなり何回も”２で割り”続けることができたり、普通に１０進法の数を扱ってると、『なんじゃこりゃ！』って感じになりますよね。

けど、上の図のようなやつをいっぱい見てたら、『数値の大小より、ビット列の長さの方が大事じゃね？』って気持ちになって来たんです。

そこで、『コラッツの手順』で出てくる奇数を２進法表示した場合の、ビット列の長さが長くなるとき、短くなるときってどういうときか、整理してみました。

ある奇数を２進法で表したときのビット列の長さを$l$としますね。で、そのビット列に、『３n＋１』に相当する『２進３倍繰上げ』の操作をほどこしてできるビット列（両端が”１”）の長さを$l'$とします。このとき、ビット列の長さ（ビット長）の変化$d$を、$d=l'-l$で定義します。

上の『悪名高き初期値２７』の図を念頭に、次の表をご覧ください。

先に結論を言ってしまうと、表から分かるように『ビット長が長くなるのは④のときだけ』なんですよね。

ちょっと詳しく見てみましょう。

最上位ビット（左端の黒）って、左にしか動きませんけど、動いても１個(①・②・③)か２個(④・⑤・⑥)なんですよね。
さらに言うと、『２個（２ビット）動く』っていうのが連続するのも２回まで。（『初期値２７』の図の左端の黒の動きを追っかけてみてね。）
３回以上連続して２ビット動くのは、ビット長が１、つまり最終的な『１』になったときだけなんです。
この辺の事情、ちゃんと数式で説明することができるんでしょうけど、その辺りはみなさんにお任せします。コメントでお知らせいただけると嬉しいです。

じゃぁ、最下位ビット（右端の黒）はどうかって言うと、少なくとも１個は左に動く(①・④)んだけど、２個以上動く(②・③・⑤・⑥)ときって、ぜーったい、右端の黒の左隣は『０』なんですよね。しかも『０』と『１』の並び方によって『右端の黒が左に動く個数』が変わってくるってわけだ。

まぁ、下位のビット列が『$ \cdots $０１０１０１(←こいつが右端)』なんてなってた日にゃー、一気に『右端の黒』が左にいっぱい動いちゃう(③・⑥)わけですよ。これまた勝手に『しましましっぽの定理』と呼んでます。 前の記事 へのコメントでアレクサンダー鷹觜さんが上手いこと式にまとめてくれてました。アレクサンダー鷹觜さん、ありがとうございました。

ビット長の有界性？

いなばなつきさんの『 有界予想 』では、初期値の自然数と同じ数だけ『コラッツの手順』で変換を施す(『２で割る』も含めて)ってことが想定されているようですね。

私の『２進３倍繰上げルール』から得られる予想としては、『初期値のビット列の長さの数と同じ回数だけ『２進３倍繰上げ』をやると、ビット長は、長くなっても２倍までは行かないね』くらいしか言えないですね。ぜーんぜん、『有界』じゃないやー。

羊頭狗肉でごめんなさい。

でも、いなばなつきさんの『 有界予想 』で
『$ k=\lfloor\ln n\rfloor$としたときは有界ではありません』っていう議論は、要するに『１０進法で考えたときの桁数』を考えてる、ってことですかね。私の『ぜーんぜん、有界じゃないやー』という結論と一緒って思っていいかな？

よくわかんないのが『従って、(連続体仮説を仮定すれば)$k$のオーダーは代数関数程度になるだろうことが分かります』って辺りなんですが、勉強します。参考になりそうな書籍や記事等をご紹介いただけるとありがたいです。

お詫びに代えて

２進法で考えるとき、ビット列を『上位部分（左側の黒のかたまり）と下位部分（右側の黒のかたまり；黒三角）とそれ以外』に分けて考える必要があるのかな、と思ってます。つまり、『”あたま”と”おしり”と”おなか”』ですね。

そんなふうに考えさせられてしまうような画像を２つほどアップします。

初期値$2^{24}+1=16777217$

こいつの真ん中を１個だけ黒に置き換えると、下のようになります。

初期値$2^{24} + 2^{12} + 1=16781313$

下位ビットからの『繰上げ』がない限り、上位ビット列は『３の累乗』倍されるんだってこととか、『おなか』に『しましま』($ \cdots 01010101 \cdots $)があると、『おなか』に『白三角』ができたり、『黒三角』ができたりするのがわかりますね。

結び

ここまでお付き合いいただき、ありがとうございました。

『２進３倍繰上げルール』に興味を持っていただけた方、『初期値◯でやってみてー』などのリクエストがありましたら、コメント欄でお知らせください。

近いうちに えどがわさんの一般化 と、私の考えてた一般化『n進(n+1)倍繰上げルール』との比較を記事にしてみたいと思ってます。よかったらまたご覧ください。

ありがとうございました！m(_ _)m

追記

『黒三角』について、縦方向に規則性が見られるのも興味深いので紹介します。
初期値$2^{24}-1=16777215$です。

初期値$2^{24}-1=16777215$

『黒三角』も下のはじっこまで来ると、『しましま』が出て来たりして、一気にビット長が短くなったりするんですよね。

『コラッツ予想』、まだまだ先は長いねぇ。