コラッツ予想派生問題コレクション(2)

どうも、チオールです。

某有名Vtuverが取り上げたことで話題のコラッツ予想の派生問題を紹介する記事、第2弾です。

本日20時より
実際に存在する、解けたら1億円もらえる「コラッツ予想」に挑戦します。１億円欲しいので、皆さんの知恵を是非貸してください。

【コラッツ予想】解けたら賞金１億円の問題に挑戦【にじさんじ/グウェル・オス・ガール】 https://t.co/O3zGCseWjh pic.twitter.com/bhHuA40TXd
— グウェル😎にじさんじ (@Gwelu_os_gar) 2022年1月23日

☟第1弾
hassium277.hatenablog.com

分岐の数を増やしてみる
次回
おまけ

分岐の数を増やしてみる

前回扱ったものはmod 2で分岐するものだけでしたが、今回はもう少し複雑なものを考えてみましょう。

mod 3

まずはこちら。

$a_{n+1}\begin{cases}\frac{a_n}{3}&\text{if}　a_n\equiv0　\pmod3\\5a_n+1&\text{if}　a_n\equiv1　\pmod3\\5a_n+2&\text{if}　a_n\equiv2　\pmod3\\\end{cases}$

a₀=10で計算すると以下のようになります。

10→51→17→87→29→147→49→246→82→411→137→687→229→1146→382→1911→637→3186→1062→354→118→591→197→987→329→1647→549→183→61→306→102→34→171→57→19→96→32→162→54→18→6→2→12→4→21→7→36→12→...

12が2回登場し、ループしたことがわかります。

上記の7を含むループのほかに、以下のようなループもあります。

8→42→14→72→24→8

1から10000までの自然数を総当たりで調べたところ、以下のようになりました。

「7」と「8」はループに入る初期値を表していて、「over」は計算途中の値が100000000を超えたものです。

なおover判定の初期値でも、扱える桁数の多い環境で計算させてみると7か8に辿り着くことがあるので、もしかしたらこのルールでも発散することは無いのかもしれません。

ところで、この「n/3,5n+1,5n+2ルール」は特に意味も無く適当に決めたものです。

3の倍数の時に3で割るのは自然な発想(?)ですが、他の2つの式は何でもいいわけです。

というわけで、まずはいくつかの式で発散する(ように見える)初期値の割合を調べました。

loopが多いルールとoverが多いルールにはっきりと分かれましたが、式だけ見ても何故違いが出るのかはよくわかりません。

実は、Wikipediaの記述をよく読むとヒントが載っています。

ja.wikipedia.org

厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察しよう。今、n が偶数ならば、次のステップで大きさは半分になる。また、n が奇数ならば、次のステップで 3n + 1 になるが、これは必ず偶数であるから、その次に (3n + 1)/2 になることまでは確定している。ここまでを一つのステップと解釈すれば、このステップで大きさは約 3/2 倍になる。1回のステップを経た後に偶数になるか、奇数になるかが半々であると考えると、1/2 の確率で数の大きさは 1/2 倍になり、残る 1/2 の確率で数の大きさは 3/2 倍になる。よって、1回のステップで、数の大きさは (1/2)1/2 × (3/2)1/2 倍になると期待される。これは 1 より小さな値であるから、ステップを経るごとに「確率的に」小さくなると考えられる。この意味で、いつかは 1 に到達するとの予想は確からしい。

$a_n$ は計算を進めると確率的な意味で $\sqrt{\frac{1}{2}×\frac{3}{2}}≒0.866$ 倍になるので、計算を繰り返すと値が小さくなる傾向が強いため発散はしにくい、という話です。

この考え方は、n/3,5n+1,5n+2数列にも応用できます。

まず、 $a_n$ が3の倍数のときは次のステップでちょうど $\frac{1}{3}$ 倍になります。

次に、 $a_n$ を3で割った余りが1、つまり $a_n=3m+1$ と表せるときは以下のように計算されます。

3m+1→15m+6→5m+2

3m+1が5m+2になるので、mが十分大きければ約 $\frac{5}{3}$ 倍になると言えます。

同様に、2余る場合には

3m+2→15m+12→5m+4

となって、 $\frac{5}{3}$ 倍になります。

これらの相乗平均は $\sqrt[3]{\frac{1}{3}×\frac{5}{3}×\frac{5}{3}}≒0.975$ で、1より小さいのでn/3,5n+1,5n+2ルールは発散しにくいと予想できます。

※なぜ相加平均ではなく相乗平均なのかわからない人は、以下の記事を読むといいかもしれません。
hassium277.hatenablog.com

以下、このような手順で求められる定数をそのルールの平均増加率と呼ぶことにします。

ということで、先程調べたルールの平均増加率を計算してみます。

なお、1より小さいか大きいかを調べるには $\frac{1}{3}$ 乗しなくてもいいので、各分岐先での増加率の積を求めるところまでで計算をやめることにします。

n/3,5n+1,5nルール
- 3m→m： $\frac{1}{3}$
- 3m+1→15m+6→5m+2： $\frac{5}{3}$
- 3m+2→15m+10→75m+51→25m+17： $\frac{25}{3}$
- $\frac{1}{3}×\frac{5}{3}×\frac{25}{3}=\frac{125}{27}＞1$

1を超えたので、n/3,5n+1,5nルールは発散しやすいと予想できます。

n/3,5n+1,5n+1ルール
- 3m→m： $\frac{1}{3}$
- 3m+1→15m+6→5m+2： $\frac{5}{3}$
- 3m+2→15m+11→75m+56→375m+281→1875m+3281→...： $\infty$

3で割って2余るケースから脱出できないので、平均増加率は無限大に発散してしまいました。

この場合、3で割った余りが2になった途端増加しかしなくなるので、確率がどうのこうのという話ではなく本当に発散します。

同様に、n/3,5n+2,5n+2ルールも平均増加率が無限大に発散します。

n/3,2n+1,5nルール
- 3m→m： $\frac{1}{3}$
- 3m+1→6m+3→2m+1： $\frac{2}{3}$
- 3m+2→15m+10→30m+21→10m+7： $\frac{10}{3}$
- $\frac{1}{3}×\frac{2}{3}×\frac{10}{3}=\frac{20}{27}＜1$

余りが2の時は2回連続で増加ルールに当たってしまいますが、係数が小さいので平均増加率は1を下回りました。

n/3,4n+2,7n+1ルール
- 3m→m： $\frac{1}{3}$
- 3m+1→12m+6→4m+2： $\frac{5}{3}$
- 3m+2→21m+15→7m+5： $\frac{7}{3}$
- $\frac{1}{3}×\frac{5}{3}×\frac{7}{3}=\frac{28}{27}＞1$

かなり僅差ですが、1を超えました。

先程の画像ではloopの方が多かったのですが、実は調査範囲を1000000まで増やすとoverの割合がかなり増えます。

念のため言っておくと、平均増加率による分析結果はあくまでも予想にすぎません。

平均増加率が1より小さいから発散しない/大きいから発散するという予測の真偽が証明された例は一件たりとも存在せず、ただ有限の実験結果と一致するというだけです。

平均増加率

ちょっと脱線しますが、平均増加率についてもう少し深堀してみたいと思います。

先程の説明では自然数のみを扱う数列しか出てきませんでしたが、実は平均増加率という概念は負の数やガウス整数を扱う場合にも応用できます。

そもそも発散するかどうかというのは0から遠ざかっていくかどうかと同じなので、 $a_n$ の係数ではなくその絶対値を計算に使えばいいだけです。

まず負の整数に拡張されたn/2,3n+kルールや-n/2,3n+kルールは、係数の絶対値が一緒なので平均増加率による分析・予測も同じ結果になります。

ちなみに平均増加率といえば、以下のようなルールも同じ平均増加率 $\sqrt{\frac{3}{4}}$ を持ちますが、n/2+j,3n+kルールと同じような「マル被り」が発生するので前回は無視していました。

$a_{n+1}=\begin{cases}3a_n+k&\text{if}　a_n\equiv0　\pmod2\\\frac{a_n+1}{2}+j&\text{if}　a_n\equiv1　\pmod2\end{cases}$
※ $k$ は奇数

次にガウス整数を扱う場合ですが、これも複素数の絶対値( $x+iy$ に対する $\sqrt{x^2+y^2}$ )を使うことで平均増加率を定義することができます。

例として、前回の最初の方に紹介したガウス整数版コラッツ数列の平均増加率を計算します。

定義は以下の通りでした。

$a_{n+1}=\begin{cases} \frac{a_n}{2}&\text{if}　a_n\equiv0　&\pmod2\\ 3a_n+1&\text{if}　a_n\equiv1　&\pmod2\\ (3+2i)a_n+i&\text{if}　a_n\equiv i　&\pmod2\\ \frac{a_n}{1+i}+1&\text{if}　a_n\equiv1+i　&\pmod2 \end{cases}$

ガウス整数を2で割った余り全パターンに対して数列を計算すると以下のようになります。

2m→m
2m+1→6m+4→3m+2
2m+i→(6+4i)m-2+4i→(3+2i)m-1+2i
2m+1+i→(1-i)m+2

後は各パターンのmの係数の比を求めて全部掛けて $\frac{1}{4}$ 乗するだけです。

2m→m： $\frac{1}{2}$
2m+1→3m+2： $\frac{3}{2}$
2m+i→(3+2i)m-1+2i： $\frac{\sqrt{13}}{2}$
2m+1+i→(1-i)m+2： $\frac{\sqrt{2}}{2}$
$\sqrt[4]{\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{13}}{2}×\frac{\sqrt{2}}{2}}≒0.989＜1$

1より小さいのでこのルールは発散しにくそうだ・・・

とは言えないっぽいです。

元々あのルールは平均増加率が1よりギリギリ小さくなるように計算して作ったのですが、その過程で以下のルールに辿り着きました。

$b_{n+1}=\begin{cases} \frac{1}{2}b_n&\text{if}　b_n\equiv0　&\pmod2\\ 3b_n+1&\text{if}　b_n\equiv1　&\pmod2\\ (3+2i)b_n+i&\text{if}　b_n\equiv i　&\pmod2\\ \frac{b_n}{1+i}&\text{if}　b_n\equiv1+i　&\pmod2 \end{cases}$

違うのは最後の1+i余るパターンのみで、完成版では1+iで割った後に1を足していたのがこのルールでは無くなっています。

このルールの平均増加率を計算するとさっきと同じ $\frac{3\sqrt{26}}{16}$ という値になるのですが、一方で数列の発散性は明らかに異なります。

☝±1000±1000iの範囲で発散する(ように見える)初期値としない初期値の割合

この違いは、平均増加率を細分化することで可視化することができます。

例えばWikipediaの説明では、平均増加率を2で割った余りをもとに計算していましたが、8で割った余りを使って以下のように計算することも可能です。

8m→4m→2m→m： $\frac{1}{8}$
8m+1→24m+4→12m+2→6m+1→18m+4→9m+2： $\frac{9}{8}$
8m+2→4m+1→12m+4→6m+2→3m+1： $\frac{3}{8}$
8m+3→24m+10→12m+5→36m+16→18m+8→9m+4： $\frac{9}{8}$
8m+4→4m+2→2m+1→6m+4→3m+2： $\frac{3}{8}$
8m+5→24m+16→12m+8→6m+4→3m+2： $\frac{3}{8}$
8m+6→4m+3→12m+10→6m+5→18m+16→9m+8： $\frac{9}{8}$
8m+7→24m+22→12m+11→36m+34→18m+17→54m+52→27m+26： $\frac{27}{8}$
$\sqrt[8]{\frac{1}{8}×\frac{9}{8}×\frac{3}{8}×\frac{9}{8}×\frac{3}{8}×\frac{3}{8}×\frac{9}{8}×\frac{27}{8}}≒0.650$

このように、より大きな数で割った余りを考え、より先ステップの項まで調べて平均増加率を求めることを「細分化」と呼ぶことにします。

コラッツ数列のmod2での平均増加率が約0.866であったのに対し、mod8に細分化すると約0.650になりました。

このように細分化を行うと平均増加率の値が変化することがありますが、細分化後の方がより細かい分析の結果であるため数列の性質を予測する根拠としてはより強いものであると考えられます。(もっとも、平均増加率による予測の正当性が未解決である以上、根拠としての強さなんてものは厳密には無意味です。)

さて、この考え方を応用して、ガウス整数版コラッツ数列の平均増加率をmod 4で計算すると以下のようになります。

4m→2m→m： $\frac{1}{4}$
4m+2→2m+1→6m+4→3m+2： $\frac{3}{4}$
4m+2i→2m+i→(6+4i)m-2+4i→(3+2i)m-1+2i： $\frac{\sqrt{13}}{4}$
4m+2+2i→2m+1+i→(1-i)m+2： $\frac{\sqrt{2}}{4}$
4m+1→12m+4→6m+2→3m+1： $\frac{3}{4}$
4m+3→12m+10→6m+5→18m+16→9m+8： $\frac{9}{4}$
4m+1+2i→12m+4+6i→6m+2+3i→(18+12i)m+14i→(9+6i)m+7i： $\frac{3\sqrt{13}}{4}$
4m+3+2i→12m+10+6i→6m+5+3i→(3-3i)m+5-i： $\frac{3\sqrt{2}}{4}$
4m+i→(12+8i)m-2+4i→(6+4i)m-1+2i→(18+12i)m-2+6i→(9+6i)m-1+3i： $\frac{3\sqrt{13}}{4}$
4m+2+i→(12+8i)m+4+8i→(6+4i)m+2+4i→(3+2i)m+1+2i： $\frac{\sqrt{13}}{4}$
4m+3i→(12+8i)m-6+10i→(6+4i)m-3+5i→(5-i)m+2+4i： $\frac{\sqrt{26}}{4}$
4m+2+3i→(12+8i)m+14i→(6+4i)m+7i→(10+24i)m-14+22i→(5+12i)m-7+11i： $\frac{13}{4}$
4m+1+i→(2-2i)m+2→(1-i)m+1： $\frac{\sqrt{2}}{4}$
4m+3+i→(2-2i)m+3-i→-2im+2-2i→-im+1-i： $\frac{1}{4}$
4m+1+3i→(2-2i)m+3+i→-2im+3-i→(-1-i)m+2-2i： $\frac{\sqrt{2}}{4}$
4m+3+3i→(2-2i)m+4→(1-i)m+2： $\frac{\sqrt{2}}{4}$
$\sqrt[16]{\frac{1}{4}×\frac{3}{4}×\frac{\sqrt{13}}{4}×\frac{\sqrt{2}}{4}×\frac{3}{4}×\frac{9}{4}×\frac{3\sqrt{13}}{4}×\frac{3\sqrt{2}}{4}×\frac{3\sqrt{13}}{4}×\frac{\sqrt{13}}{4}×\frac{\sqrt{26}}{4}×\frac{13}{4}×\frac{\sqrt{2}}{4}×\frac{1}{4}×\frac{\sqrt{2}}{4}×\frac{\sqrt{2}}{4}}\\=\frac{\sqrt[16]{2^3×3^7×13^3×\sqrt{13}}}{4}≒0.807＜1$

これが1より小さいというのは前と変わらない結果ですが、一方で発散しやすい方は以下の通りです。(変化した部分の内、平均増加率に影響する部分のみを赤で示した。)

4m→2m→m： $\frac{1}{4}$
4m+2→2m+1→6m+4→3m+2： $\frac{3}{4}$
4m+2i→2m+i→(6+4i)m-2+4i→(3+2i)m-1+2i： $\frac{\sqrt{13}}{4}$
4m+2+2i→2m+1+i→(1-i)m+1： $\frac{\sqrt{2}}{4}$
4m+1→12m+4→6m+2→3m+1： $\frac{3}{4}$
4m+3→12m+10→6m+5→18m+16→9m+8： $\frac{9}{4}$
4m+1+2i→12m+4+6i→6m+2+3i→(18+12i)m+14i→(9+6i)m+7i： $\frac{3\sqrt{13}}{4}$
4m+3+2i→12m+10+6i→6m+5+3i→(3-3i)m+4-i： $\frac{3\sqrt{2}}{4}$
4m+i→(12+8i)m-2+4i→(6+4i)m-1+2i→(18+12i)m-2+6i→(9+6i)m-1+3i： $\frac{3\sqrt{13}}{4}$
4m+2+i→(12+8i)m+4+8i→(6+4i)m+2+4i→(3+2i)m+1+2i： $\frac{\sqrt{13}}{4}$
4m+3i→(12+8i)m-6+10i→(6+4i)m-3+5i→(5-i)m+1+4i： $\frac{\sqrt{26}}{4}$
4m+2+3i→(12+8i)m+14i→(6+4i)m+7i→(10+24i)m-14+22i→(5+12i)m-7+11i： $\frac{13}{4}$
4m+1+i→(2-2i)m+1→(6-6i)m+4→(3-3i)m+2： $\frac{3\sqrt{2}}{4}$
4m+3+i→(2-2i)m+2-i→(10-2i)m+8+2i→(5-i)m+4+i： $\frac{\sqrt{26}}{4}$
4m+1+3i→(2-2i)m+2+i→(10-2i)m+4+8i→(5-i)m+2+4i： $\frac{\sqrt{26}}{4}$
4m+3+3i→(2-2i)m+3→(6-6i)m+10→(3-3i)m+5： $\frac{3\sqrt{2}}{4}$
$\sqrt[16]{\frac{1}{4}×\frac{3}{4}×\frac{\sqrt{13}}{4}×\frac{\sqrt{2}}{4}×\frac{3}{4}×\frac{9}{4}×\frac{3\sqrt{13}}{4}×\frac{3\sqrt{2}}{4}×\frac{3\sqrt{13}}{4}×\frac{\sqrt{13}}{4}×\frac{\sqrt{26}}{4}×\frac{13}{4}×\frac{3\sqrt{2}}{4}×\frac{\sqrt{26}}{4}×\frac{\sqrt{26}}{4}×\frac{3\sqrt{2}}{4}}\\=\frac{\sqrt[16]{2^3×3^9×13^4×\sqrt{26}}}{4}≒1.11＞1$

なんと、1を超えました。

このようなことが起きる理由はよくわかっていないのですが、おそらく2が合成数であることが影響しているのではないかと思います。

mod2で平均増加率を計算するとき、2を1+iで割った後は2で割った余りの情報が無くなるからと計算を止めていたのですが、どうも見えない形で何らかの情報が残るっぽいです。

複雑性

以下、今まで扱ってきた「剰余で分岐してそれぞれの一次関数を適用するやつ」を「コラッツシステム」と呼ぶことにします。

これまで紹介した-n/2,3n+1数列やn/3,2n+1,5n数列などは全てコラッツシステムの一種です。

これまで扱ったコラッツシステムは分岐が高々4つまでの単純なものでしたが、少し複雑なものとして以下のようなものについて考えましょう。

※一般のコラッツシステムでは「計算結果が整数ではなくなり、続きが計算できなくなる」というケースが発生することがあります。この記事ではあまり触れませんが、とりあえず「途中で終わることもある」という事は覚えておくとよいかもしれません。

$a_0=1296$
$a_{n+1}=\begin{cases} 0&\text{if}　a_n\equiv0 　&\pmod{30}\\ \frac{1}{5}a_n+\frac{14}{5}&\text{if}　a_n\equiv 1　&\pmod{30}\\ \frac{1296}{25}a_n-\frac{2542}{25}&\text{if}　a_n\equiv 2　&\pmod{30}\\ \frac{5}{81}a_n+\frac{76}{27}&\text{if}　a_n\equiv 3　&\pmod{30}\\ \frac{81}{25}a_n-\frac{224}{25}&\text{if}　a_n\equiv 4　&\pmod{30}\\ 0&\text{if}　a_n\equiv 5　&\pmod{30}\\ \frac{25}{81}a_n+1&\text{if}　a_n\equiv 6　&\pmod{30}\\ 0&\text{if}　a_n\equiv7 　&\pmod{30}\\ a_n-2&\text{if}　a_n\equiv 8　&\pmod{30}\\ \frac{282429536481}{25}a_n-\frac{2541865828104}{25}&\text{if}　a_n\equiv 9　&\pmod{30}\\ a_n-4&\text{if}　a_n\equiv 10　&\pmod{30}\\ \frac{25}{16}a_n-\frac{9}{25}&\text{if}　a_n\equiv 11　&\pmod{30}\\ 0&\text{if}　a_n\equiv12 　&\pmod{30}\\ \frac{81}{25}a_n-\frac{143}{25}&\text{if}　a_n\equiv 13　&\pmod{30}\\ 0&\text{if}　a_n\equiv14 　&\pmod{30}\\ a_n-9&\text{if}　a_n\equiv 15　&\pmod{30}\\ 0&\text{if}　a_n\equiv16 　&\pmod{30}\\ 0&\text{if}　a_n\equiv17 　&\pmod{30}\\ 0&\text{if}　a_n\equiv18 　&\pmod{30}\\ 0&\text{if}　a_n\equiv19 　&\pmod{30}\\ 0&\text{if}　a_n\equiv20 　&\pmod{30}\\ 0&\text{if}　a_n\equiv 21　&\pmod{30}\\ 0&\text{if}　a_n\equiv22 　&\pmod{30}\\ \frac{531441}{5}a_n-\frac{1594278}{5}&\text{if}　a_n\equiv 23　&\pmod{30}\\ 0&\text{if}　a_n\equiv24 　&\pmod{30}\\ 0&\text{if}　a_n\equiv25 　&\pmod{30}\\ \frac{1296}{25}a_n-\frac{1246}{25}&\text{if}　a_n\equiv 26　&\pmod{30}\\ 0&\text{if}　a_n\equiv27 　&\pmod{30}\\ 0&\text{if}　a_n\equiv28 　&\pmod{30}\\ 0&\text{if}　a_n\equiv29 　&\pmod{30}\\ \end{cases}$

分岐が30パターンあります。

所々にある0をまとめて見やすくすると以下のようになります。

$a_0=1296$
$a_{n+1}=\begin{cases} \frac{1}{5}a_n+\frac{14}{5}&\text{if}　a_n\equiv 1　&\pmod{30}\\ \frac{1296}{25}a_n-\frac{2542}{25}&\text{if}　a_n\equiv 2　&\pmod{30}\\ \frac{5}{81}a_n+\frac{76}{27}&\text{if}　a_n\equiv 3　&\pmod{30}\\ \frac{81}{25}a_n-\frac{224}{25}&\text{if}　a_n\equiv 4　&\pmod{30}\\ \frac{25}{81}a_n+1&\text{if}　a_n\equiv 6　&\pmod{30}\\ a_n-2&\text{if}　a_n\equiv 8　&\pmod{30}\\ \frac{282429536481}{25}a_n-\frac{2541865828104}{25}&\text{if}　a_n\equiv 9　&\pmod{30}\\ a_n-4&\text{if}　a_n\equiv 10　&\pmod{30}\\ \frac{25}{16}a_n-\frac{9}{25}&\text{if}　a_n\equiv 11　&\pmod{30}\\ \frac{81}{25}a_n-\frac{143}{25}&\text{if}　a_n\equiv 13　&\pmod{30}\\ a_n-9&\text{if}　a_n\equiv 15　&\pmod{30}\\ \frac{531441}{5}a_n-\frac{1594278}{5}&\text{if}　a_n\equiv 23　&\pmod{30}\\ \frac{1296}{25}a_n-\frac{1246}{25}&\text{if}　a_n\equiv 26　&\pmod{30}\\ 0&\text{otherwise} \end{cases}$

実は、この数列について以下の性質が成り立ちます。

全ての自然数 $m$ に対して、 $a_n=1296^m$ が成り立つような非負整数 $n$ が存在する
$⇔$ コラッツ予想は真

実際に計算してみると、以下のようになります。

1296¹→401→626→32402→1679618→1679616(=1296²)→518401→103683→6403→20740→20736→6401→10001→15626→810002→41990402→2176782338→2176782336(=1296³)→671846401→134369283→8294403→512003→54419558409→614787626176508399625→49797797720297180368896→15369690654412709990401→3073938130882541998083→189749267338428518403→11712917736940032003→723019613391360003→44630840332800003→2754990144000003→170061120000003→10497600000003→648000000003→40000000003→129600000004→419904000004→1360488960004→4407984230404→14281868906500→14281868906496→4407984230401→881596846083→54419558403→3359232003→207360003→12800003→1360488960009→15369690654412709990409→173634184295285569594549998391305→14064368927918131137158549869694976→4340854607382139239863749959782401→868170921476427847972749991956483→53590797622001719010663579750403→3308073927284056729053307392003→204202094276793625250204160003→12605067547950223780876800003→778090589379643443264000003→48030283295039718720000003→2964832302162945600000003→183014339639688000000003→11297181459240000000003→697356880200000000003→43046721000000000003→2657205000000000003→164025000000000003→10125000000000003→625000000000003→2025000000000009→6561000000000004→21257640000000004→68874753600000004→223154201664000004→723019613391360004→2342583547388006404→7589970693537140740→7589970693537140736→2342583547388006401→468516709477601283→28920784535654403→1785233613312003→110199605760003→6802444800003→419904000003→25920000003→1600000003→5184000004→16796160004→54419558404→176319369220→176319369216→54419558401→10883911683→671846403→41472003→2560003→8294404→26873860→26873856→8294401→1658883→102403→331780→331776→102401→160001→250001→390626→20250002→1049760002→54419558402→2821109907458→2821109907456(=1296⁴)→...

膨大な量の計算を経て、m=4まで出現することが確認できました。

実はこのコラッツシステムは、n/2,3n+1数列を初期値を変えながら順番に計算していくプログラムとして機能します。

実際、 $a_n=1296^{13}$ 以降の数列の内、 $16^x81^y$ という形の項を抽出すると、

$16^{13}81^{13}$ → $16^{13}81^{40}$ → $16^{13}81^{20}$ → $16^{13}81^{10}$ → $16^{13}81^{5}$ → $16^{13}81^{16}$ → $16^{13}81^{8}$ → $16^{13}81^{4}$ → $16^{13}81^{2}$ → $16^{13}81^{1}$ →

$16^{14}81^{14}$ → $16^{14}81^{7}$ → $16^{14}81^{22}$ → $16^{14}81^{11}$ → $16^{14}81^{34}$ → $16^{14}81^{17}$ → $16^{14}81^{52}$ → $16^{14}81^{26}$ → $16^{14}81^{13}$ → $16^{14}81^{40}$ → $16^{14}81^{20}$ → $16^{14}81^{10}$ → $16^{14}81^{5}$ → $16^{14}81^{16}$ → $16^{14}81^{8}$ → $16^{14}81^{4}$ → $16^{14}81^{2}$ → $16^{14}81^{1}$ →

$16^{15}81^{15}$ → $16^{15}81^{46}$ → $16^{15}81^{23}$ → $16^{15}81^{70}$ → $16^{15}81^{35}$ → $16^{15}81^{106}$ → $16^{15}81^{53}$ → $16^{15}81^{160}$ → $16^{15}81^{80}$ → $16^{15}81^{40}$ → $16^{15}81^{20}$ → $16^{15}81^{10}$ → $16^{15}81^{5}$ → $16^{15}81^{16}$ → $16^{15}81^{8}$ → $16^{15}81^{4}$ → $16^{15}81^{2}$ → $16^{15}81^{1}$ →

$16^{16}81^{16}$ →...

というようになるのですが、実はこの $y$ の値は $x$ を初期値とするn/2,3n+1数列の計算結果と一致します。

要するに、このコラッツシステムは

(1)　 $16^x81^1$ を $16^x81^x$ にする

(2)　 $16^x81^y$ の $y$ をn/2,3n+1ルールに従って変化させる

(3)　 $y$ が1になったら $x$ に1を足して(1)に戻る

という動作をします。

$1296^m$ というのは(1)を実行した後の値、つまりm-1から始まるn/2,3m+1数列が1に到達した後の値なので、全ての自然数mについて $1296^m$ が現れるということは(1以外の)全ての自然数mについてm-1から始まるn/2,3n+1数列が1に到達することを意味します。

このように、コラッツシステムを使えば意味のある(?)機械的計算を行うことができます。

現実的に実装可能かどうかは別として、例えば3の倍数と3の付く数字を順番に求めるプログラムや素数を順番に求めるプログラムをコラッツシステムで記述することだってできるはずです。

これを数学的に言うとこうなります。

定理4
コラッツシステムはチューリング完全である。

あるシステムがチューリング完全(どんな計算もできること)であることを示すには、チューリング完全な別のシステムを模倣できることを示すという手段があります。

コラッツシステムの場合は、FRACTRANというプログラミング言語の模倣ができます。

en.wikipedia.org

FRACTRANの仕様は以下の通りです。

有理数が入ったリスト $(r_1,r_2,r_3...)$ と1個の自然数 $n$ を使って計算を行う。
(1)　 $r_1$ から順番に、リストの中から $r_mn$ が自然数になるような要素 $r_m$ を探す。
(2)　 $r_m$ が見つかったら、 $n$ を $r_mn$ で置き換えて(1)に戻る。
(3)　 $r_m$ が見つからなくなったら、計算を終了する。

例として、リストを $\left(\frac{5}{7},\frac{14}{15},\frac{1}{5},\frac{3}{2},5\right)$ として、 $n=8$ として計算をしてみます。

まず、8は7、15、5では割り切れないので、最初は $\frac{3}{2}$ を掛けて $n=12$ になります。

この後も2回続けて $\frac{3}{2}$ を掛け、 $n$ の値は12→18→27と変化します。

27はもう2では割り切れないので、リストの右端の $5$ が $n$ に掛けられて135になります。

これで $n$ が15の倍数になったので、次は左から2番目にある $\frac{14}{15}$ を掛けて $n=126$ になります。

次は $\frac{5}{7}$ を掛けて $90$ になって再び15の倍数になり、以降3で割り切れなくなるまで $\frac{14}{15}$ と $\frac{5}{7}$ が交互に掛けられ、 $n$ は90→84→60→56→40と変化します。

最後に40に $\frac{1}{5}$ が掛けられて $n$ は8になり、初期値と同じ値に戻ったのでループすることがわかります。

このサンプルはただループするだけのつまらないプログラムですが、もっと複雑で意味のある(?)計算を実装することができます。

例えば $\left(\frac{5}{7},\frac{12400927}{15},\frac{3}{4},\frac{73205}{2},\frac{11}{3},\frac{1}{5}\right)$ に対して $n=32$ とすると最終的に $n$ の値は45949729863572161になり、 $n=64$ から始めると $n=1331$ で終了します。

値だけ見てもなんのこっちゃ分からないと思いますが、 $n=32$ のときの値は $11^{16}$ と等しく、 $n=64$ のときは $11^3$ になっています。

実はこのプログラムは初期値が $2^n$ なら「 $n$ が偶数なら $11^{\frac{n}{2}}$ 、奇数なら $11^{3n+1}$ 」になる、つまりn/2,3n+1数列を1項だけ計算するプログラムとして機能します。

さて、コラッツシステムの話に戻ります。

FRACTRANを使えばあらゆる機械的計算を実行できますが、以下のような手順によりFRACTRANで書かれたプログラムをコラッツシステムに翻訳することができます。

例として、先程の $\left(\frac{5}{7},\frac{14}{15},\frac{1}{5},\frac{3}{2},5\right)$ をコラッツシステムで再現します。

まず、リストの全ての要素の分母の最小公倍数を求めます。

7、15、5、2、1の最小公倍数は210で、この値がコラッツシステムの分岐数になります。

ちなみに先程の「n/2,3n+1数列を1項だけ計算するプログラム」の分岐数は420、Wikipediaで例として挙げられている「素数を2から順に求めるプログラム」では6469693230になります。

次に、各分岐に対応する210個の一次関数を決定します。

まず、FRACTRANプログラムの先頭の要素は $\frac{5}{7}$ ですが、これは「 $n$ が7の倍数なら $\frac{5}{7}$ を掛ける」ということを意味します。

これをmod 210のコラッツシステムで表すと、以下のような意味になります。

$a_{n+1}=\begin{cases} \frac{5}{7}a_n&\text{if}　a_n\equiv0　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv7　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv14　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv21　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv28　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv35　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv42　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv49　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv56　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv63　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv70　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv77　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv84　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv91　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv98　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv105　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv112　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv119　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv126　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv133　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv140　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv147　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv154　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv161　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv168　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv175　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv182　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv189　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv196　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv203　&\pmod{210} \end{cases}$

210=7×30なので、7の倍数であるという条件をmod 210で表現すると30本の式が必要になります。

さて、FRACTRANプログラムの2個目の要素は $\frac{14}{15}$ です。

これはつまり「 $n$ が7の倍数ではなく、なおかつ15の倍数であれば $\frac{14}{15}$ を掛ける」と言い換えることができ、コラッツシステムに翻訳すると以下のようになります。

$a_{n+1}=\begin{cases} \frac{14}{15}a_n&\text{if}　a_n\equiv15　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv30　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv45　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv60　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv75　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv90　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv120　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv135　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv150　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv165　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv180　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv195　&\pmod{210}\\ \end{cases}$

210未満の非負整数の中で15の倍数は14個ありますが、その内0と105は7の倍数なので除外されます。

以降同様に、

7、15の倍数でないが5の倍数なら $\frac{1}{5}$ を掛ける→
$a_{n+1}=\frac{1}{5}a_n　\text{if}　a_n\equiv5,10,20,25,40,50,55,65,80,85,95,100,110,115,125,130,145,155,160,165,170,185,190,195,205　\pmod{210}$
7、15、5の倍数でないが2の倍数なら $\frac{3}{2}$ を掛ける→
$a_{n+1}=\frac{2}{3}a_n　\text{if}　a_n\equiv2,4,6,8,12,16,18,22,24,26,32,34,36,38,44,46,48,52,54,58,62,64,66,68,72,74,76,78,82,86,88,92,94,96,102,104,106,108,114,116,118,122,124,128,132,134,136,138,132,134,136,138,142,144,146,148,152,156,158,162,166,172,174,176,178,184,186,188,192,194,198,202,204,206,208　\pmod{210}$
7、15、5、2の倍数でないなら5を掛ける→略

となり、全てまとめると以下のようなコラッツシステムができます。

$a_{n+1}=\begin{cases} \frac{5}{7}a_n&\text{if}　a_n\equiv0　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv1　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv2　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv3　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv4　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv5　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv6　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv7　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv8　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv9　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv10　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv11　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv12　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv13　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv14　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv15　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv16　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv17　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv18　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv19　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv20　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv21　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv22　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv23　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv24　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv25　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv26　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv27　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv28　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv29　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv30　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv31　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv32　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv33　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv34　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv35　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv36　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv37　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv38　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv39　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv40　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv41　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv42　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv43　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv44　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv45　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv46　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv47　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv48　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv49　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv50　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv51　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv52　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv53　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv54　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv55　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv56　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv57　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv58　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv59　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv60　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv61　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv62　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv63　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv64　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv65　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv66　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv67　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv68　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv69　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv70　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv71　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv72　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv73　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv74　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv75　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv76　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv77　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv78　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv79　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv80　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv81　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv82　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv83　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv84　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv85　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv86　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv87　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv88　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv89　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv90　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv91　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv92　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv93　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv94　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv95　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv96　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv97　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv98　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv99　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv100　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv101　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv102　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv103　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv104　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv105　&\pmod{210}\\ \end{cases}$
$a_{n+1}=\begin{cases} \frac{3}{2}a_n&\text{if}　a_n\equiv106　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv107　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv108　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv109　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv110　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv111　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv112　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv113　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv114　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv115　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv116　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv117　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv118　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv119　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv120　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv121　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv122　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv123　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv124　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv125　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv126　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv127　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv128　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv129　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv130　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv131　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv132　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv133　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv134　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv135　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv136　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv137　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv138　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv139　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv140　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv141　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv142　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv143　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv144　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv145　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv146　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv147　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv148　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv149　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv150　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv151　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv152　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv153　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv154　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv155　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv156　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv157　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv158　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv159　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv160　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv161　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv162　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv163　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv164　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv165　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv166　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv167　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv168　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv169　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv170　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv171　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv172　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv173　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv174　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv175　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv176　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv177　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv178　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv179　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv180　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv181　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv182　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv183　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv184　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv185　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv186　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv187　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv188　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv189　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv190　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv191　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv192　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv193　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv194　&\pmod{210}\\ \frac{14}{15}a_n&\text{if}　a_n\equiv195　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv196　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv197　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv198　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv199　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv200　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv201　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv202　&\pmod{210}\\ \frac{5}{7}a_n&\text{if}　a_n\equiv203　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv204　&\pmod{210}\\ \frac{1}{5}a_n&\text{if}　a_n\equiv205　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv206　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv207　&\pmod{210}\\ \frac{3}{2}a_n&\text{if}　a_n\equiv208　&\pmod{210}\\ 5a_n&\text{if}　a_n\equiv209　&\pmod{210} \end{cases}$

※210本の式を一纏めにしようとしても何故か正常に表示できなかったので、真ん中で分割してあります。

このように、リストの左側から順に割り当てていくことでFRACTRANプログラムをコラッツシステムに翻訳することができます。

なお、FRACTRANの仕様を考えれば当然なことですが、FRACTRANを翻訳してできたコラッツシステムには定数項が一切使われません。

ということは翻訳で生成されたシステムはコラッツシステムの機能をフルに活用できていないことになり、定数項をうまく使うことで愚直な翻訳よりも(主に簡潔性の面で)優れたコラッツシステムが作れることが予想できます。

実際、「全ての自然数を初期値としたn/2,3n+1数列を計算するコラッツシステム」がmod 30で実装できたのに対し、FRACTRANを経由する場合はそれよりずっと単純なはずの「n/2,3n+1数列を1項だけ計算するコラッツシステム」ですら14倍のmod 420になってしまいます。

さて、ここまでの説明で(厳密な証明ではないものの)「コラッツシステムはチューリング完全である」という事が大体わかってもらえたと思いますが、このことからコラッツ予想派生問題について以下のことが言えます。

一般のコラッツ予想派生問題(=コラッツシステムの挙動の分析)は、決定不可能である。

ある問題群が決定不可能であるというのは、その問題群に属する問題を必ず解けるようなアルゴリズムが存在しないことを意味します。

例えば「整数係数2次方程式 $ax^2+bx+c=0$ が実数解を持つか判定せよ」という問題は、2次方程式の判別式を計算することで解くことができるので決定不可能ではありません。

一方、コラッツシステムの挙動(ある値に辿り着けるか、どんなループが存在するか、発散するか等)を必ず決定できるようなアルゴリズムは存在しません。

そもそもコラッツシステムがチューリング完全であるということはいくらでも複雑な機械的計算ができるということであり、いくらでも複雑な計算の結果を予測するには当然ながらいくらでも複雑な計算が必要になるわけです。

実際、コラッツシステムが1に到達するかという問題が以下のページで「一般化Collatz問題」という名前で載っています。

iso.2022.jp

ちなみに先程までの説明に従うと、コラッツシステムで具体的な何かを計算するには毎回それ専用のルールを設計する必要があるように思えます。

例えばn/2,3n+1数列を計算するコラッツシステムと素数を計算するコラッツシステムは別物でしたが、単一のシステムであらゆる計算を行うことはできないのでしょうか？

1次元セル・オートマトンという計算システムが存在します。

よく知られているものは256種類のルールがあり、それぞれ不規則な模様を生成したり規則的なフラクタル図形を生成したりします。

そして、Rule110というルールはチューリング完全であることが証明されており、その単純さから様々なシステム(例えば「スーパーマリオメーカー」など)のチューリング完全性の証明に使われています。

en.wikipedia.org

もしこのシステムをエミュレートできるコラッツシステムをつくることができれば、「初期値を変えることであらゆる計算を行える単一のコラッツシステム」が実現できるのではないでしょうか？

次回

まだまだ書きたいことは残っているので、次回に続きます。

とりあえず次回で最初の記事で拾えなかったネタの消化は終わって一区切りつくと思います。

それでは、さようなら。

おまけ

n/2,3n+1,(3+2i)n+i,n/(1+i)数列のループがやたら多くて面白かったので載せておきます。

代表値	周期	個数
over		3934324
1	3	31191
1+2i	15	13267
-17	18	10799
-1	2	4556
-5	5	3873
-i	3	2211
38-281i	31	756
173-162i	31	667
1-2i	6	549
239-248i	31	321
112-267i	31	297
257-174i	31	207
248-195i	31	156
312-55i	31	151
247+36i	31	129
167-200i	31	108
205-230i	31	102
172-143i	31	74
208-63i	31	73
200-123i	31	66
167-86i	31	63
172-207i	31	60
0	1	1

1→4→2→1

1+2i→4+6i→2+3i→14i→7i→-14+22i→-7+11i→2+9i→-12+32i→-6+16i→-3+8i→-8+24i→-4+12i→-2+6i→-1+3i→1+2i

-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17

-1→-2→-1

-5→-14→-7→-20→-10→-5

-i→2-2i→1-1i→-i

38-281i→676-766i→338-383i→1780-472i→890-236i→445-118i→1336-354i→668-177i→2358+806i→1179+403i→791-388i→2374-1164i→1187-582i→3562-1746i→1781-873i→454-1327i→4016-3072i→2008-1536i→1004-768i→502-384i→251-192i→754-576i→377-288i→1132-864i→566-432i→283-216i→850-648i→425-324i→1276-972i→638-486i→319-243i→38-281i

173-162i→520-486i→260-243i→1266-208i→633-104i→1900-312i→950-156i→475-78i→1426-234i→713-117i→298-415i→1724-648i→862-324i→431-162i→1294-486i→647-243i→202-445i→1496-930i→748-465i→3174+102i→1587+51i→819-768i→2458-2304i→1229-1152i→3688-3456i→1844-1728i→922-864i→461-432i→1384-1296i→692-648i→346-324i→173-162i

1-2i→4-6i→2-3i→12-4i→6-2i→3-1i→1-2i
239-248i→718-744i→359-372i→1078-1116i→539-558i→1618-1674i→809-837i→-14-823i→1604-2496i→802-1248i→401-624i→1204-1872i→602-936i→301-468i→904-1404i→452-702i→226-351i→1380-600i→690-300i→345-150i→1036-450i→518-225i→2004+362i→1002+181i→2644+2548i→1322+1274i→661+637i→649-12i→1948-36i→974-18i→487-9i→239-248i

112-267i→870-576i→435-288i→1306-864i→653-432i→1960-1296i→980-648i→490-324i→245162i→736-486i→368243i→1590+8i→795+4i→2386+12i→1193+6i→3580+18i→1790+9i→5352+3608i→2676+1804→1338+902i→669+451i→560-109i→1898+794i→949+397i→673-276i→2020-828i→1010414i→505-207i→149-356i→448-1068i→224-534i→112-267i

257-174i→772-522i→386-261i→1680-10i→840-5i→2530+1666i→1265+833i→1049-216i→3148-648i→1574-324i→787-162i→2362-486i→1181-243i→469-712i→1408-2136i→704-1068i→352-534i→176-267i→1062-448i→531-224i→1594-672i→797-336i→2392-1008i→1196-504i→598-252i→299-126i→898-378i→449-189i→130-319i→1028-696i→514-348i→257-174i

248-195i→1134-88i→567-44i→1702-132i→851-66i→2554-198i→1277-99i→589-688i→1768-2064i→884-1032i→442-516i→221-258i→664-774i→332-387i→1770-496i→885-248i→2656-744i→1328-372i→664-186i→332-93i→1182+386i→591+193i→392-199i→1574+188i→787+94i→2362+282i→1181+141i→661-520i→1984-1560i→992-780i→496-390i→248-195i

312-55i→1046+460i→523+230i→1570+690i→785+345i→565-220i→1696-660i→848-330i→424-165i→1602+354i→801+177i→489-312i→1468-936i→734-468i→367-234i→1102-702i→551-351i→100-451i→1202-1152i→601-576i→1804-1728i→902-864i→451-432i→1354-1296i→677-648i→2032-1944i→1016-972i→508-486i→254-243i→1248-220i→624-110i→312-55i

247+36i→742+108i→371+54i→1114+162i→557+81i→319-238i→958-714i→479-357i→61-418i→184-1254i→92-627i→1530-1696i→765-848i→2296-2544i→1148-1272i→574-636i→287-318i→862-954i→431-477i→-23-454i→-68-1362i→-34-681i→1260-2110i→630-1055i→4000-1904i→2000-952i→1000-476i→500-238i→250-119i→988+144i→494+72i→247+36i

167-200i→502-600i→251-300i→754-900i→377-450i→1132-1350i→566-675i→3048-892i→1524-446i→762-223i→2732+856i→1366+428i→683+214i→2050+642i→1025+321i→673-352i→2020-1056i→1010-528i→505-264i→1516-792i→758-396i→379-198i→1138-594i→569-297i→136-433i→1274-1026i→637-513i→62-575i→1336-1600i→668-800i→334-400i→167-200i

205-230i→616-690i→308-345i→1614-418i→807-209i→299-508i→898-1524i→449-762i→1348-2286i→674-1143i→4308-2080i→2154-1040i→1077-520i→3232-1560i→1616-780i→808-390i→404-195i→1602+224i→801+112i→2404+336i→1202+168i→601+84i→1804+252i→902+126i→451+63i→257-194i→772-582i→386-291i→1740-100i→870-50i→435-25i→205-230i

172-143i→802-84i→401-42i→1204-126i→602-63i→1932+1016i→966+508i→483+254i→1450+762i→725+381i→553-172i→1660-516i→830-258i→415-129i→143-272i→430-816i→215-408i→646-1224i→323-612i→970-1836i→485-918i→1456-2754i→728-1377i→4938-2674i→2469-1337i→566-1903i→5504-4576i→2752-2288i→1376-1144i→688-572i→344-286i→172-143i

208-63i→750+228i→375+114i→1126+342i→563+171i→367-196i→1102-588i→551-294i→1654-882i→827-441i→193-634i→580-1902i→290-951i→2772-2272i→1386-1136i→693-568i→2080-1704i→1040-852i→520-426i→260-213i→1206-118i→603-59i→272-331i→1478-448i→739-224i→2218-672i→1109-336i→3328-1008i→1664-504i→832-252i→416-126i→208-63i

200-123i→846+32i→423+16i→1270+48i→635+24i→1906+72i→953+36i→2860+108i→1430+54i→715+27i→371-344i→1114-1032i→557-516i→1672-1548i→836-774i→418-387i→2028-324i→1014-162i→507-81i→213-294i→640-882i→320-441i→1842-682i→921-341i→290-631i→2132-1312i→1066-656i→533-328i→1600-984i→800-492i→400-246i→200-123i

167-86i→502-258i→251-129i→61-190i→184-570i→92-285i→846-670i→423-335i→44-379i→890-1048i→445-524i→1336-1572i→668-786i→334-393i→1788-510i→894-255i→3192+1024i→1596+512i→798+256i→399+128i→1198+384i→599+192i→1798+576i→899+288i→2698+864i→1349+432i→4048+1296i→2024+648i→1012+324i→506+162i→253+81i→167-86i

172-207i→930-276i→465-138i→1396-414i→698-207i→2508+776i→1254+388i→627+194i→1882+582i→941+291i→616-325i→2498+258i→1249+129i→689-560i→2068-1680i→1034-840i→517-420i→1552-1260i→776-630i→388-315i→1794-168i→897-84i→2692-252i→1346-126i→673-63i→305-368i→916-1104i→458-552i→229-276i→688-828i→344-414i→172-207i