コラッツ予想(3n+1)がなぜ収束するのかについて

このノートの主題
・コラッツ予想を２進法で考えてみたところ、３の累乗を２進数で表示したときに、「ある大きさから１の数を０の数が上回る」という特性があることに気づきました。
・コラッツ予想が「なぜ収束するのか？」について、それっぽいヒントになると思いましたので、いちおう公開します。

・２進法で考えるコラッツ予想

こちらは某ユーチューバーの鈴木先生がおっしゃっていたのですが、「コラッツ予想は２進法で表記すると直感的になにが起こっているのか分かりやすい」ということで、まずは２進法でコラッツ予想をとらえるところから解説したいと思います。
知っているという方は読み飛ばして差支えないです。

まずは、適当な数字を二進法で表記すると、以下のような形になります。
１１０１００
この表記のすばらしい点は、どんな数字に対しても「2^kの約数がひと目で分かる」点です。
１１０１００
↑太線で示したところが、この数の２＾ｋの約数となります。
この例で言えば、下数桁を見れば、この数はM×２＾２の形でくくれるのが一目で分かる、ということです。

本題に戻って、そもそもコラッツ予想の操作は

偶数なら２で割る、奇数なら３倍して１を足す

という単純なものですが、2進数で表記すれば「２で何回割れるのか？」が一目瞭然、ということです。

１１０１００
２で割ると
１１０１０
２で割ると
１１０１

になります。2で２回割れます。

さらに、「３倍して１を足す」という操作も2進数なら直感的に分かりやすくなります。

３＝２＋１なので、ある数を３倍するという操作を２進法で表記すると、「位が１つあがった数をもとの数に足しこむ」という単純な動作になります。どういうことかと言うと

　　　１１０１
　＋１１０１０
＝１００１１１

が3倍の操作です。コラッツ予想ではこれに１を足すわけですから、
　１００１１１
＋　　　　　１
　１０１０００

となり、またこの数を構成する最小の2^kから何回２で割るかが一目瞭然、というわけです。
これが２進法で表記する利点です。

・２で割るのをやめると何が見えてくるか？

いよいよこのブログの本題です。
この操作を何度かやっていて、「２で割る動作をやめてもコラッツ予想は成立するのではないか？」という風に思いついたので、成立するようにやってみました。

つまり、ある数を以下のように２進数で表記します

K(a)2^a + K(b)2^b + K(c)2^c + …. + K(z)2^z

(K(a)~K(z)=0,1)

2で割りきれるまで割るということは、この中から最小となる2^kで全体を割るのと同じことです。
それをやめつつ、コラッツ予想と矛盾することなく操作を続けるにはどうするか。
以下のような変形コラッツ予想を考えました。

《変形コラッツ予想》
すべての自然数Xに対して
3X + 2^k
（2^kはその時のXの約数）
を繰り返していくと、その数は２の乗数（1000….000)に収束する。

つまり、Xを２^kで割ってから、３倍して１を足す（x/2^k）×3+1のですから、Xを3倍して2^kを足してやって、あとで２^kで割っても同じじゃないか{(x)×3+2^k}/2^kということです。

もっというと2進数で表記すれば「別に割らなくても分かる」じゃないか、ということです。

・本当に２の乗数（100…000)に収束するのか？

変形コラッツ予想をしばらく動かしていると、「+ 2^k」の操作のあと、次の「+ 2^k'」は絶対に前の値より大きくなるはずです。

当然といえば当然です。「+ 2^k」する相手が「2^k」を最小の構成要素として持っているので、足して出来る数は2^(k+1)以下の構成要素を持たないからです。
その後、３倍するという操作でも、「+ 2^k'」するという操作でも、2^(k+1)以下の数にはまったく影響をあたえません。

また前回、３Ｘ＋１のかわりに、１Ｘ＋１ならコラッツ予想が成立することを証明しましたが、これにも同様の変形操作をためしてみたところ、当然ながら最終的に２の累乗に収束していました。
二進法で変化をよく見ると、１Ｘ＋１なので、掛け算のパートでは数はまったく変化しません。
ですが、「+ 2^k」するたびに一番下の位からどんどん1が0になってゆく変化のみ起きます。もはやどんな数でも自明に100…000に収束すると言って差し支えないでしょう。

これから考えると、３Ｘ＋１でなくとも、１と０の割合によって収束するかどうかを判別できる可能性があります。

いままで私は、この０をズバッとぜんぶ削除して、完全に２で割って何かを論じようとしていました。
けれど、この０を残してみると、もっと根本的な問題があるような気がします。

「２の乗数（100…000)に収束する」ということは、言い換えると「この計算を繰り返していくと、２進数表記の１がどんどん減って、最終的にただ１個に収束する」ということです。

つまり、変形コラッツ予想の操作を繰り返しながら、０と１の割合をじっと観察していれば、どんどん１が減って０が増えていくはずです。

かいつまんで言うと、
「何回も３倍する＝３の累乗にそもそも０が増えて１が減る傾向があるのが原因じゃないのか？」
というところまで分かったよ、という話です。

（６月５日追記：３の累乗は（２＋１）＾ｎの形になるので、因数分解すると２^n+Cb2^(n-1)＋・・・＋Cz2＋１・・・①の形になり、ｎが無限に大きくなるとどんどん２＾ｎに近づいていきます。
　さらに、２進法にしたときの構成要素である最低数の２＾ｋ（ｋ＝０含む）を加えるため、①は式の右の方からどんどん消えていくことになります。たぶんこれが原理ですが、それが全部だとすると５も2^2k+1なので２の累乗に収束しそうな気がします。実は５Ｘ＋１は別記しますが別の収束点があります。どうしてなのか？　を今後考えていきたいです）

ただ、その詳細なメカニズムがまだ分かっていないです。
以下は、自分の所感ですが、いちおう書いておきます。

ある２進数を０と１の数字の塊として考えます。
１を０で分割されるまでの連続回数でとらえると、
1が単独である場合、３倍すると
　　１
＋１
＝１１

となり、１の数が１個増える。
しかし、１が連続である場合、３倍すると
　　　１１１・・・１１１
　＋１１１・・・１１１
＝１０１１１・・１１０１
となり、１の数は同じだが、０の数が２個増える。

また、「１が連続である場合、その直下の位から１が繰り上がってきたとき、１の連続回数ぶん０が増え、１が減る」。

　　１１１・・・１１１１
　＋　　　　　　　　　１
＝１０００・・・００００

１．３倍して１が増えるのは、0に挟まれた単独の１がある場合のみ。そのとき連続の１になる。
２．しかし、連続した１がある場合は1の数は増えず、０が２個増える。
３．おまけに連続した１は下からの繰り上がりがあると、いきなり１個に減り、そのぶんだけ０は爆発的に増える。

これらの要素があわさって、２進法表記の３の累乗は０の割合が増え、１の割合が減るのだと思われます。

実際に、プログラムを組んでやってみたのですが、（Excellだと１０進数→２進数変換関数が数桁ぶんしか対応していないので、いちからVBAで作らないといけなくてちょっとしんどい）
だいたい３の１１乗くらいが１のピークで
１対０＝１３：５（個）
と圧倒的優位だったのが、３の１２乗で
１対０＝１０：１０（個）
以降は１が優勢になる場面はみられず、２５乗で
１対０＝１０：３０（個）
になっていました。
（Ｅｘｃｅｌでは３０乗でオーバーフローした）

・結論と今後の課題

今回分かったことはここまでです。あとはネットの海に投げて、個人的に楽しもうと思います。

原理的には、コラッツ予想とは１を足す操作（繰り上がり）によって、２進法の最小の位の１が常に繰り上がり続けているため、ｎ倍する操作によって１の集合が減る傾向にあるか、あるいは数がまったく変化しないような場合に、どんどん上の位へと圧縮される、というのが収束の原理になると思います。

ところで、『５Ｘ＋１は１３に収束するループがあります』。

この収束ループがなんで生まれるのか、３の累乗の０対１の割合はどこまで増加するのか、今後はこういった事を調べていきたいと思います。

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