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

お久しぶりです、チオールです。

某ラジオ番組で話題になったコラッツ予想の派生問題を紹介する記事、第3弾です。

www.tbsradio.jp

☟第0弾
hassium277.hatenablog.com

☟第1弾
hassium277.hatenablog.com

☟第2弾
hassium277.hatenablog.com

続・ガウス整数
異世界転生
3項漸間化式
連立と統一
最後に
おまけ

続・ガウス整数

前回と前々回の両方でガウス整数版のコラッツシステムの話をしましたが、扱った数列は1種類のみでした。

というわけで、別のガウス整数版コラッツシステムの挙動を調べてみました。

n/2,3n+1,(2+i)n+1,(2+i)n+1+i

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

±1000±1000iの範囲の4004001個の初期値を総当たりで調べ、発散する初期値の個数とループの個数を調べました。

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{5}}{2}×\frac{\sqrt{5}}{2}\right)^{\frac{1}{4}}≒0.984$
over	201378(5.03%)
ループ個数	7個

1→4→2→1
0→0
-1→-2→-1
-5→-14→-7→-20→-10→-5
-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17
i→2i→i
-1+i→-2+2i→-1+i

収束先に応じて初期値を色分けすると以下のようになります。

前々回載せた図と同様に、放射状の線が見えますがそれ以外に目立った特徴は見当たりません。

ちなみに、前々回の記事を書いたときはほぼすべての計算をExcelに任せており、上の図もVBAを使って半日近く(必要な事前計算も含めると丸1日以上)掛けて描画させていました。

ところが、2月ごろに行われた(らしい)ExcelのアップデートのせいでVBAによる図の描画がやり辛くなってしまったため、Processingというものに乗り換えることにしました。

processing.org

そして環境の変化とアルゴリズムの改良により、図1枚の作成にかかる時間は長くても10分程度にまで短縮されました。(ループ個数が極端に多いものを除く)

ちなみに、先程の図を最初に作成しようとしたとき、以下のようになりました。

図の作成に使ったプログラムでは、 $a_n$ の計算のほかに既知のループの代表値を配列に保存して、

$a_n$ を1回計算するごとに配列の中に同じ値があるか探して、同じ値があったら収束したと見做して計算を止める
$a_{4999}$ まで計算して同じ値が出なかったら、 $a_{4999}$ の値を配列に追加する

という計算をしています。

この手法は「±1000±1000iの範囲の初期値なら、4999回以内の計算で何らかのループに必ず到達できるだろう」という仮定に依存しているのですが、どうやらこのn/2,3n+1,(2+i)n+1,(2+i)n+1+iルールではこの仮定は成り立たないようです。

配列の中身を見てみると、ループの代表値7個の他に関係ない値が23個も入っており、図の右側が変色していたのも誤った値でループ判定が起きていたせいだと考えられます。(なぜあの領域だけ変色するのかは謎です)

これ以降の図では計算回数を49999回まで増やしているので、誤判定は減っていると思います。

n/2,3n+1,5n+i,(n+1+i)/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\\ 5a_n+i&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{5}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.984$
over	1007538(25.2%)
ループ個数	410個

ループ個数が超多い。

ループごとの初期値の分布図は以下のようになりました。

放射状の模様がよりはっきり見えます。

このことと関係あるのかはわかりませんが、このルールのループを複素平面にプロットするとほぼ直線状に点が並びます。

直線状になるのは、 $a_n$ の係数が4つとも実数であるためだと思われます。

定数項 $c$ に対して $x$ が十分大きい場合、 $rx+c$ ( $r$ は実数)は原点から直線的に離れたり近づいたりする動きをするので、ループも直線的になるというわけです。

ちなみに、ループの個数が異様に多いのも、「直線的な動きしかできないから遠くにあるループサイクルに近づきにくいから」と考えることができます。

n/2,3n+1,5in+1,(n+1+i)/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\\ 5ia_n+1&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{5}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.984$
over	992528(24.8%)
ループ個数	558個

さらにループが増えました。

分布図はこんな感じです。

4回回転対称っぽい模様になりました。

ループの形は手裏剣みたいな4つのカドがある形になります。

これは $a_n$ の係数の内の3つが実数で、あと一つが純虚数であるためだと思われます。

実数係数の式を計算すると直線状の動きをし、純虚数の場合は90度回転した位置にある直線の辺りへ移動します。

なのでループの要素は原点で直交する2本の直線の近くに集中し、4つのカドができるというわけです。

以下、整数乗すると実数になるような係数しか持たないルールを有理角ルールと呼ぶことにします。

n/2,3n+1,3n+i,(n+1+i)/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\\ 3a_n+i&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	882194(22.0%)
ループ個数	62個

このルールの平均増加率は実はn/2,3n+1ルールと同じ値ですが、over率もループ個数もずっと多いです。

また、これよりも平均増加率が大きいn/2,3n+1,(2+i)n+1,(2+i)n+1+iルールと比べても、やはりover率もループ個数も(5.03%、7個)多いです。

ループ個数が多いのはn/2,3n+1,5n+i,(n+1+i)/2ルールの項目で説明した通りですが、同様に「離れた位置にあるループに近づきにくいから」という理屈で「有理角ルールはover率が高くなりがち」ということが説明できます。(ちゃんとした証明ではありませんが)

このルールの分布図はこうなります。

有理角ルールの例にもれず放射状の模様がはっきり見えますが、前の2つとは違いノイズ状の模様すらないまっさらな領域があります。

これに関しては理由が全く分からなかったので、似たルールをいくつか試してみました。

n/2,3n+1,(2+i)n+1,(n+1+i)/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\\ (2+i)a_n+1&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{5}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.805$
over	0(0%)
ループ個数	11個

平均増加率が小さければああなるというわけではなさそうです。

n/2,3n+1,3in+1,(n+1+i)/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\\ 3ia_n+i&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	2974(0.0743%)
ループ個数	23個

平均増加率が小さくて有理角ルールならいいというわけでもないようです。

n/2,3n+5,3n+i,(n+1+i)/2

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	179034(4.47%)
ループ個数	80個

定数項を一つだけ変えてみましたが、同じような感じにはなりませんでした。

n/2,3n+3,3n+i,(n+1+i)/2

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	208824(5.22%)
ループ個数	76個

ようやく非ノイズ状領域が現れました。

実整数版コラッツ数列では「3n+3k,n/2ルールの挙動は3n+k,n/2ルールとほぼ同じ」という性質がありましたが、関係あるのでしょうか？

-n/2,3n+1,3n+i,(n+1+i)/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\\ 3a_n+i&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	223810(5.59%)
ループ個数	30個

前々回「-n/2,3n+1ルールはn/2,3n+1ルールよりある意味単純」みたいなことを言いましたが、このルールにはその性質は反映されないようです。

どうやら実整数での性質は、必ずしもガウス整数全体へ反映されるわけではないようです。

n/2,3n+3,3n+3i,(n+1+i)/2

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	403354(10.1%)
ループ個数	60個

非ノイズ状領域がありますが、それよりも所々に見える模様が特徴的です。

n/2,3n+1,3n+1,(n+1+i)/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\\ 3a_n+1&\text{if}　a_n\equiv i&\pmod2\\ \frac{a_n+1+i}{2}&\text{if}　a_n\equiv1+i&\pmod2 \end{cases}$

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{3}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.866$
over	1667000(41.6%)
ループ個数	32個

もう意味が分かりません。

結局、非ノイズ状領域の出現条件はよくわかりませんでした。

平均増加率の小ささと有理角ルールであることが必要条件になりそうな気がするのですが、それ以上の絞り込みは現時点では無理そうです。

n/2,15n+1,(n+i)/2,(n+1+i)/2

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{15}{2}×\frac{1}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.984$
over	1526070(38.1%)
ループ個数	62個

よく見ると、三角形の鱗状の模様が見えます。

この図形は「シェルピンスキーのギャスケット」というフラクタル図形で、非常に単純な規則で生成できるのでいろいろなところで見かけます。(前回紹介した「1次元セル・オートマトン」でもこれを生成するルールがたくさんあります)

どうやら、4つの1次関数の内3つの係数の絶対値を $\frac{1}{2}$ に統一すると、シェルピンスキーのギャスケットみたいな模様が現れるようです。

異世界転生

前々回の記事では、コラッツシステムを自然数だけでなく整数全体、そしてガウス整数の世界へと拡張することについて考えました。

自然数→整数→ガウス整数と来てさらにこの先に進んでもいいのですが、あえて別の方向に進んでみます。

整数を拡張した概念は、実はガウス整数だけではありません。

というわけで、ガウス整数以外の数の世界でコラッツシステムを考える　ー　いわばコラッツシステムの異世界転生について考えてみましょう。

アイゼンシュタイン整数

アイゼンシュタイン整数は、整数 $a$ 、 $b$ と $\omega=\frac{-1+\sqrt{3}i}{2}$ を用いて $a+b\omega$ と表せる数のことです。

これを使ってこんな数列を作ってみました。

$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+\omega)a_n+1&\text{if}　a_n\equiv\omega&\pmod2\\ (2+\omega)a_n+1&\text{if}　a_n\equiv1+\omega&\pmod2 \end{cases}$

考え方はガウス整数の時と同じで、平均増加率がギリギリ1を超えないように適当に数値を決めています。

この数列のループは以下のようなものが見つかりました。

0→0
1→4→2→1
-1→-2→-1
-5→-14→-7→-20→-10→-5
-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17
ω→2ω→ω
1+ω→2+2ω→1+ω
1+2ω→4+6ω→2+3ω→4+8ω→2+4ω→1+2ω

黒で書かれているのは普通の整数版コラッツ数列でも存在するループで、赤がアイゼンシュタイン整数への拡張で新たに出現したループです。

各ループに収束する初期値の統計データは以下の通りです。

なお、ガウス整数 $a+bi$ の絶対値(の2乗)は $a^2+b^2$ でしたが、アイゼンシュタイン整数 $a+b\omega$ の絶対値は $a^2-ab+b^2$ です。( $a+b\omega=a-\frac{b}{2}+b\frac{\sqrt{3}i}{2}$ と変形して複素数の絶対値の式を使うとこの式になります)

これにより、ガウス整数上では不可能だった3分岐のコラッツシステムをつくることができます。

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

このルールでは7個のループが見つかっており、分布図は以下の通りです。

※a+bωを点(a,b)としてプロットしているので、実際の複素平面上での正確な位置関係とは異なります。

実はこれを最初に描いたときは、以下のような画像が出力されました。

見事なフラクタル図形ですが、これはプログラムのバグによるものです。

負の数に対する剰余はプログラミング言語によって挙動がバラバラらしいのですが、今回使用したProcessingという言語では「負の数を割った余りは負の数になる」という仕様になっているようです。

ja.wikipedia.org
※上記のページにはProcessingの仕様については載っていませんが、Processingの元になったJavaという言語が載っています。

説明は省きますが、「 $x+y\omega$ を $2+\omega$ で割った余り」は「 $x-2y$ を3で割った余り」として計算できます。

ところが、 $x-2y$ が負になった場合は3で割った余りも負になってしまい、例えばProcessingに「 $1+3\omega$ を $2+\omega$ で割った余りは１ですか？」と聞いた場合、Processingは「1-2*3=-5を3で割った余りは-2なので、違う」と判断してしまいます。

こういうミスにより数列が正しく計算できなくなり、結果として間違った分布図が出力されたようです。(フラクタル図形になる理由は不明ですが)

ℤ[√-2]

有理数に対して代数的数(代数方程式の解になる数)を追加して拡張した数の世界を代数体と呼び、その中での整数の集まりのことをその代数体の整数環と呼ぶそうです。

特に2次無理数で拡張した代数体を2次体と呼び、今まで紹介してきたガウス整数とアイゼンシュタイン整数はそれぞれℤ[√-1]、ℤ[(-1+√-3)/2]と表記される2次体の一種です。

・・・という話は別にどうでもよくて、ここの項目名であるℤ[√-2]が「 $\sqrt{2}i$ を追加して拡張された整数」を表しているということがわかっていたただければ十分です。(そもそもこの辺の話は私もよく知らないです)

とりあえず、こんな数列を作ってみました。

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

統計データは以下の通りです。

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{2}}{2}×\frac{\sqrt{11}}{2}\right)^{\frac{1}{4}}≒0.968$
over	0(0%)
ループ個数	6個

このルール固有(実数では無かった)のループは以下の1個のみです。

※以下、 $\alpha=\sqrt{2}i$ と略記します。

-1-6α→-2-18α→-1-9α→16-28α→8-14α→4-7α→-6-2α→-3-α→-6-6α→-3-3α→-2-12α→-1-6α

分布図は以下の通りです。

特に目立った特徴は無いようです。

ところで、このルールでは前回紹介したとある現象とよく似た現象が確認されました。

以下の数列は、先程の数列の余りが $\sqrt{2}i$ の時のルールの定数項を1にしただけのものです。

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

この数列のmod 2での平均増加率は $a_n$ と同じ値になるのですが、発散率は大きく異なります。

	$a_n$	$b_n$
平均増加率(mod 2)	0.968	0.968
over	0(0%)	3796683(95.0%)
ループ個数	6個	5個

ちなみに、分布図もこんなに違います。

この現象は、前回説明したとおり平均増加率をmod 4に細分化することで解消されます。

$a_n$ のmod 4での平均増加率は0.778、一方 $b_n$ は1.06になり、 $b_n$ が発散性が強いことが数値的に示されたことになります。

ガウス整数でこの現象が起きたのは2が1+iで割り切れるという性質のせいでしたが、今回は $\sqrt{2}i$ が2を割り切ってしまいます。

アイゼンシュタイン整数では2は素数のままだったので、こういった現象には遭遇しなかったというわけです。

話は変わりますが、 $\sqrt{2}i$ は2乗すると-2になります。

-2で割った余りというのは2で割った余りと同一視できると考えると、 $\text{mod}　\sqrt{2}i$ のコラッツシステムを細分化するとmod 2のコラッツシステムになるという事が言えます。

つまり、こういうことができます。

$a_{n+1}=\begin{cases} \frac{a_n}{\sqrt{2}i}&a_n\equiv0&\pmod{\sqrt{2}i}\\ -3a_n+1&a_n\equiv1&\pmod{\sqrt{2}i} \end{cases}$

これをmod 2に細分化すると、こうなります。

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

上二つの式を見ると、-n/2,3n+1ルールと実質的に同じ数列であることがわかります。

つまりこの数列は-n/2,3n+1数列をℤ[√-2]に拡張したものであり、しかも今までの適当に式を追加しただけの拡張よりも自然な拡張であると考えることができます。

・・・と思ったのですが、

めちゃくちゃ発散性が強くて全然面白く無いです。

ℤ[√-5]

ℤ[√-5]は、整数 $a$ 、 $b$ を使って $a+b\sqrt{5}i$ と表せる複素数全体の集合です。

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{21}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.963$
over	306502(7.65%)
ループ個数	9個

1+α→1+α
3+2α→10+6α→5+3α→3+2α
-9-4α→-26-12α→-13-6α→-38-18α→-19-9α→-9-4α
-33-16α→-98-48α→-49-24α→-146-72α→-73-36α→-218-108α→-109-54α→-326-162α→-163-81α→-81-40α→-242-120α→-121-60α→-362-180α→-181-90α→-542-270α→-271-135α→-135-67α→-67-33α→-33-16α

※ $\alpha=\sqrt{5}i$

ところで、今まで何の説明もなく「 $a+b\sqrt{5}i$ を2で割った余り」みたいな概念を扱ってきましたが、どうやら拡張された整数の世界における割り算の余りというのは必ずしも定義できるものではないようです。

wikipediaの2次体に関する記事を眺めてみると、以下のようなことが書かれていました。

余りのある割り算が定義できる整数の世界のことを「ユークリッド整域」という
ℤ[√-5]は、ユークリッド整域ではない

ただし、ユークリッド整域における「余りのある割り算ができる」という性質は正確には「余りが十分小さいと言えるような、大きさの尺度が定義できる」というもので、コラッツシステムを定義するために必要な余りの性質とは異なります。

具体的には、以下の性質が成り立てばコラッツシステムが定義できるはずです。

整数環 $O$ とその要素 $\alpha$ に対して、以下の性質を満たすような $O$ の部分集合 $m_{\alpha}$ が存在すれば $O$ 上での $\mod{\alpha}$ のコラッツシステムが定義できるだろう。

$O$ のいかなる要素 $\beta$ に対しても、 $\beta-\mu$ が $\alpha$ で割り切れるような $m_{\alpha}$ の要素 $\mu$ がただ一つ存在する。

$m_{\alpha}$ は有限集合である。

例えば $O=\mathbb{Z}[\sqrt{-5}]$ 、 $\alpha=2$ とすると、 $O$ の要素が2で割り切れるには実部と虚部が両方偶数であればいいので $m_2=\{0,1,\sqrt{5}i,1+\sqrt{5}i\}$ とすることで $\mod2$ のコラッツシステムが定義できる・・・と思います。

正直に言うとこの辺の話は私はまだよくわかってないので、どこまであってるかはわからないです。

ℤ[√2]

ここまでで扱った数の世界は、2次体の中の虚2次体と呼ばれるものです。

2次方程式の虚数解で拡張した整数の世界を虚2次体と言い、実数解で拡張したものは実2次体と呼ばれます。

というわけで、実2次体の一種であるℤ[√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+\sqrt{2})a_n+\sqrt{2}&\text{if}　a_n\equiv\sqrt{2}&\pmod2\\ \frac{a_n+1+\sqrt{2}}{2}&\text{if}　a_n\equiv1+\sqrt{2}&\pmod2\\ \end{cases}$

ところで、虚2次体では絶対値(の2乗)によって平均増加率を計算できたり分岐数がわかったりしましたが、一般の代数体には絶対値に対応する概念として「ノルム」というものがあるそうです。

ノルムの詳しい説明は省きますが(なぜなら説明できるほど詳しくないので)、ℤ[√2]のノルムは $a^2-2b^2$ になります。

そして、先程の数列のノルムによる平均増加率を含む統計データは以下のようになりました。

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{7}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.839$
over	39501(0.987%)
ループ個数	16個

分布図はこんな感じです。

何の変哲もない収束性の強いルールに見えます。

ところが、以下のルールは全く同じ平均増加率を持つにもかかわらず異なった性質を持ちます。

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{7}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.839$
over	2968415(74.1%)
ループ個数	21個

平均増加率が同じなのに、明らかに発散性が強くなっています。

さらに、以下のルールはもっと発散しやすくなります。

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

平均増加率(mod 2)	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{7}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.839$
over	3828077(95.6%)
ループ個数	10個

もうお気づきかと思いますが、実は実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\\ (5-3\sqrt{2})a_n+\sqrt{2}&\text{if}　a_n\equiv\sqrt{2}&\pmod2\\ \frac{a_n+1+\sqrt{2}}{2}&\text{if}　a_n\equiv1+\sqrt{2}&\pmod2\\ \end{cases}$

この数列の平均増加率はノルムで計算すれば先程のものと同じ約0.839になりますが、実数としての絶対値を使えば $\left(\frac{1}{2}×\frac{3}{2}×\frac{5-3\sqrt{2}}{2}×\frac{1}{2}\right)^{\frac{1}{4}}≒0.614$ となります。

一方で $5-3\sqrt{2}$ の部分を $5+3\sqrt{2}$ に変えると平均増加率は約1.15になるので、先程紹介したものと比べると確かに発散性が抑えられていると言え・・・

ません。

残念ながら、実数としての絶対値も発散性の指標にはならないようです。

そもそも「 $a+b\sqrt{2}$ が発散する」とはどういうことかというと、私が計算に使っているコードでは「 $|a|$ か $|b|$ が発散する」という解釈をもとにしてコードが書かれています。

例えば複素数の絶対値においては $a^2+b^2$ が発散するときは $|a|$ か $|b|$ も発散すると言えますが、ℤ[√2]の場合は $|a|$ と $|b|$ が両方発散しても $|a+b\sqrt{2}|$ が有限の値になることがあります。

例として $|(1-\sqrt{2})^n|$ という値を考えると、以下のように $|a|$ と $|b|$ が発散するのに $|a+b\sqrt{2}|$ が発散しない例になっていることがわかります。

$(1-\sqrt{2})^1=1-1\sqrt{2}≒-0.414$
$(1-\sqrt{2})^2=3-2\sqrt{2}≒0.172$
$(1-\sqrt{2})^3=7-5\sqrt{2}≒-0.0711$
$(1-\sqrt{2})^4=17-12\sqrt{2}≒0.0294$
$(1-\sqrt{2})^5=41-29\sqrt{2}≒0.0122$

どうやらコラッツシステムの話に限らず、2次体の整数環の一般論として、虚2次体より実2次体の方がややこしい性質があって扱いにくいことが少なからずあるらしいです。

さて話は変わりますが、 $\sqrt{2}^2=2$ であることを利用すると以下のようなことができます。

$a_{n+1}=\begin{cases} \frac{a_n}{\sqrt{2}}&\text{if}　a_n\equiv0&\pmod{\sqrt{2}}\\ 3a_n+1&\text{if}　a_n\equiv1&\pmod{\sqrt{2}}\\ \end{cases}$

この数列を $\mod2$ に細分化すると以下のようになります。

$a_{n+1}=\begin{cases} \frac{a_n}{2}&\text{if}　a_n\equiv0&\pmod2\\ \frac{3a_n+1}{2}&\text{if}　a_n\equiv1&\pmod2\\ \frac{3a_n+\sqrt{2}}{2}&\text{if}　a_n\equiv\sqrt{2}&\pmod2\\ \frac{9a_n+3-9\sqrt{2}}{2}&\text{if}　a_n\equiv1+\sqrt{2}&\pmod2\\ \end{cases}$

上2つの式を見ると、n/2,3n+1数列の自然な拡張になっていることがわかります。

まぁ、発散性が強すぎて全然面白くないんですけどね。

分解型複素数

分解型複素とは、実数に対して $j^2=1$ を満たす新たな数 $j$ を追加した数の体系です。

「 $j=±1$ では？」と思うかもしれませんが、「±1と同じ性質を持つけど±1じゃない数」を追加したのが分解型複素数というものです。

「そんなことしていいのか？」と思うかもしれませんが、実際あまりよくないらしく色々と変な性質があります。

例えば分解型複素数 $a+bj$ のノルムは $a^2-b^2$ になるようですが、今まで扱ってきた体系と異なりこの値は負になったり0になったりします。

さらに $(1+j)(1-j)=1-j+j-1=0$ というように0を掛けたわけでもないのに掛け算の結果が0になったり、0以外にも割り算ができない数があったりと厄介な挙動をします。

さて、そんな変な世界でコラッツシステムはどのように振舞うのでしょうか？

まずは以下のような数列を考えました。

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

平均増加率	$\left(\frac{1}{2}×\frac{3}{2}×\frac{\sqrt{-1}}{2}×0\right)^{\frac{1}{4}}=0$
over	0(0%)
ループ個数	1642個

ノルムが負になったり0になったりするので平均増加率もメチャクチャなことになっており、もはや発散性の指標として全く機能していないことが伺えます。(以降、こんな感じで平均増加率が意味を成さないときは記載しないことにします)

また、ループ個数が異様に多いのも気になります。

どうやら任意の奇数aに対してa-aj→2a-2aj→a-ajというループが存在する、つまりこのルールには無限個のループが存在するようです。

分布図はこんな感じです。

※プログラムのバグにより、発散しない点でも極稀に黒く描画されてしまうようです。今までの図でも同じ現象が発生しているのですが、面倒なので修正は諦めました。

今までのものと同じような原点中心の放射状の模様は見られず、平行な斜めの線が目立ちます。

他のルールもいくつか試してみます。

n/2,3n+1,(1+2j)n+j,(1-j)n+1

over	0(0%)
ループ個数	6個

定数項を一つ追加するだけで無限無限ループが消滅したようです。

n/2,3n+1,(1+4j)n+j,(1-j)n

over	45(0.00112%)
ループ個数	8763個

ループが大幅に増えました。

n/2,3n+1,(1+6j)n+j,(1-j)n

over	879(0.0220%)
ループ個数	26267個

ループがさらに増えました。

描画に使用しているプログラムはループ個数が増えれば増えるほど動作が遅くなるので、この画像1枚を描画するのに半日近く掛かりました。

n/2,3n+1,(1+4j)n+j,(1-j)n+1

over	3992699(99.7%)
ループ個数	6個

定数項を一つ追加するだけで、無限無限ループが消滅しただけでなく発散性が急上昇しました。

???

次は、 $a+b\sqrt[3]{2}+c\sqrt[3]{4}$ (a,b,cは整数)という形の数に対するコラッツシステムを考えます。

$\sqrt[3]{2}$ は3次の代数的数なので、 $a+b\sqrt[3]{2}+c\sqrt[3]{4}$ の世界は多分3次体の整数環というものになると思います。

ちなみにこの体のノルムは多分 $a^3+2b^3+4c^3-6abc$ です。(wikipediaのノルムの記事を読んでも何もわからなかったので、自己流解釈＆勘を駆使して求めました)

まず、以下のような数列を考えます。

$a_{n+1}=\begin{cases} \frac{a_n}{\sqrt[3]{2}}&\text{if}　a_n\equiv0\pmod{\sqrt[3]{2}}\\ 3a_n+1&\text{if}　a_n\equiv1\pmod{\sqrt[3]{2}} \end{cases}$

$b\sqrt[3]{2}$ と $c\sqrt[3]{4}$ は $\sqrt[3]{2}$ で割り切れるので、「 $a+b\sqrt[3]{2}+c\sqrt[3]{4}$ を $\sqrt[3]{2}$ で割った余り」はaを2で割った余りとして計算できます。

$(\sqrt[3]{2})^3=2$ なのでmod 2に細分化すると以下のようになります。

$a_{n+1}=\begin{cases} \frac{a_n}{2}&\text{if}　a_n\equiv0&\pmod2\\ \frac{3a_n+1}{2}&\text{if}　a_n\equiv1&\pmod2\\ \frac{3a_n+\sqrt[3]{2}}{2}&\text{if}　a_n\equiv\sqrt[3]{2}&\pmod2\\ \frac{9a_n+3+\sqrt[3]{2}}{2}&\text{if}　a_n\equiv1+\sqrt[3]{2}&\pmod2\\ \frac{3a_n+\sqrt[3]{4}}{2}&\text{if}　a_n\equiv\sqrt[3]{4}&\pmod2\\ \frac{9a_n+3+\sqrt[3]{4}}{2}&\text{if}　a_n\equiv1+\sqrt[3]{4}&\pmod2\\ \frac{9a_n+3\sqrt[3]{2}+\sqrt[3]{4}}{2}&\text{if}　a_n\equiv\sqrt[3]{2}+\sqrt[3]{4}&\pmod2\\ \frac{27a_n+9+3\sqrt[3]{2}+\sqrt[3]{4}}{2}&\text{if}　a_n\equiv1+\sqrt[3]{2}+\sqrt[3]{4}&\pmod2 \end{cases}$

上2つの式を見ると、n/2,3n+1数列の自然な拡張になっていることがわかります。

※ $a+b\sqrt[3]{2}+c\sqrt[3]{4}$ に対応する点を描画するには3次元空間が必要ですが、上手く描画する技術力が無いのでcの値を固定して平面上にプロットしています。

まぁ、発散性が強すぎて全然面白くないんですけどね。

もう流石にこの展開は見飽きたと思います。

何故毎回こうなるのかというと、おそらく2の冪乗根に対して「3」という値が大きすぎるせいだと思います。

これまで見てきた「細分化するとn/2,3n+1数列になる数列」では、2で割るという操作を $\sqrt{2}$ や $\sqrt[3]{2}$ で割るという操作の繰り返しへと分解していました。

同様に3を掛けるという動作を分割しようとすると「 $\sqrt{3}$ を2回掛ける」というような動作になるわけですが、 $\sqrt{3}$ は $\mathbb{Z}[\sqrt{2}]$ や $\mathbb{Z}[\sqrt[3]{2}]$ では整数として存在できなかったので仕方なく分割せずに一括で掛けていたのでした。

????

次は、 $a+b\sqrt{2}+c\sqrt{3}+d\sqrt{6}$ (a,b,c,dは整数)という形の数に対するコラッツシステムを考えます。

これなら $\sqrt{2}$ と $\sqrt{3}$ が両方とも整数になるので、「細分化するとn/2,3n+1数列になり、なおかつ発散性の低い数列」が存在することが期待できます。

というわけで、完成したものがこちらです。

$a_{n+1}=\begin{cases} \frac{a_n}{\sqrt{2}}&\text{if}　a_n\equiv0&\pmod{\sqrt{2}}\\ \sqrt{3}a_n+\sqrt{2}+\sqrt{3}+\sqrt{6}&\text{if}　a_n\equiv1&\pmod{\sqrt{2}}\\ \frac{a_n+\sqrt{3}}{\sqrt{2}}&\text{if}　a_n\equiv \sqrt{3}&\pmod{\sqrt{2}}\\ \sqrt{3}a_n-3-\sqrt{2}-2\sqrt{3}&\text{if}　a_n\equiv1+\sqrt{3}&\pmod{\sqrt{2}}\\ \end{cases}$

$b\sqrt{2}$ と $d\sqrt{6}$ は $\sqrt{2}$ で割り切れるので、 $a+b\sqrt{2}+c\sqrt{3}+d\sqrt{6}$ を $\sqrt{2}$ で割った余りはaとcを2で割った余りの組み合わせとして計算できます。(ちなみにこの代数体のノルムは多分 $a^4+4b^4+9c^4+36c^4-4a^2b^2-6a^2c^2-12a^2d^2-12b^2c^2-24b^2d^2-36c^2d^2+48abcd$ です)

これをmod 2に細分化すると以下のようになります。

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

上2つの式を見ると、n/2,3n+1数列の自然な拡張になっているように見えます。

分布図と統計データは以下の通りです。

※ $a+b\sqrt{2}+c\sqrt{3}+d\sqrt{6}$ に対応する点を描画するには4次元空間が必要ですが、上手く描画する技術力が無いのでcとdの値を固定して平面上にプロットしています。

over	96317(2.41%)
ループ個数	26個

ようやく発散性が低いルールが見つかりましたね。

ちなみに、先程の分布図ではcとdを0に固定していましたが、別の変数を固定すると見た目が変わります。

over	0(0%)
ループ個数	16個

over	384361(9.60%)
ループ個数	67個

over	0(0%)
ループ個数	3個

ところで、今までの代数体の整数環では「細分化するとn/2,3n+1数列になる数列」は有限個(多分1個)しか存在しなかったようなのですが、今回は事情が違うようです。

例えば以下の数列ではe,f,g,hの値が何であっても細分化すれば $\frac{a_n}{2}$ と $\frac{3a_n+1}{2}$ になるので、 $a+b\sqrt{2}+c\sqrt{3}+d\sqrt{6}$ の世界では「細分化するとn/2,3n+1数列になる数列」は無限に存在することがわかります。

$a_{n+1}=\begin{cases} \frac{a_n}{\sqrt{2}}&\text{if}　a_n\equiv0&\pmod{\sqrt{2}}\\ \sqrt{3}a_n-\sqrt{2}+\sqrt{3}&\text{if}　a_n\equiv1&\pmod{\sqrt{2}}\\ ea_n+f&\text{if}　a_n\equiv \sqrt{3}&\pmod{\sqrt{2}}\\ ga_n+h&\text{if}　a_n\equiv1+\sqrt{3}&\pmod{\sqrt{2}}\\ \end{cases}$

余談ですが、代数体の整数環の歴史にはかの有名なフェルマーの最終定理が深く関わっているそうです。

フェルマーの最終定理：3以上の自然数 $n$ について、 $X^n+Y^n=Z^n$ を満たす自然数 $X,Y,Z$ は存在しない。

$x^n=1$ の解を追加して拡張した整数の世界(「円分体の整数環」というそうです)では $X^n+Y^n$ を因数分解することができ、かつてそのことを利用してフェルマーの最終定理を証明しようとした数学者がいました。

最終的に完全な証明には至らなかったものの最終定理の研究は大きく前進し、同時に代数体の整数環の理論にも大きく影響を与えたそうです。

実は私が代数体の整数環上でのn/2,3n+1数列の一般化について考えたのには上記のような背景があり、「フェルマーの最終定理と同じように、コラッツ予想も『分解』したら何かが見えてくるのでは？」と思ったのがきっかけです。

まぁ結局のところ、代数体についてまともに勉強したことのないド素人にはほぼ何も見えてこなかったわけですが。

3項漸間化式

数列の話をしていると、フィボナッチ数列を思い浮かべるという人も多いかもしれません。

フィボナッチ数列

$F_0=0$

$F_1=1$

$F_{n+2}=F_{n+1}+F_n$

$F_n=0,1,1,2,3,5,8,13,21...$

フィボナッチ数列はコラッツシステムと違い、ある項を計算するために前の項とさらに前の項を使います。

計算したい項、前の項、さらに前の項の3つの項が式に含まれるので、フィボナッチ数列の定義のような漸化式は3項間漸化式と呼ばれているようです。

というわけで、コラッツシステムに3項間漸化式を組み込んだらどうなるか見てみましょう。

※同じような発想で4項間漸化式や5個間漸化式を組み込んだコラッツシステムを考えることもできますが、キリがないので紹介しません。

m/2,(m+1)/2+n

※ルール名のmは $a_{n+1}$ 、nは $a_n$ に対応しています。

まず、こんな数列を作ってみました。

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

下の方の式が3項間漸化式になっています。

このコラッツシステムには以下のようなループがあります。

0→0
-1→-1
-1→-2→-1
-3→-7→-6→-3
1→3→3→5→6→3→8→4→2→1
-31→-77→-69→-111→-124→-62→-31
-35→-87→-78→-39→-97→-87→-140→-70→-35
77→193→174→87→218→109→273→246→123→308→154→77
157→393→354→177→443→399→643→721→1004→502→251→628→314→157
-783→-1957→-1761→-2837→-3179→-4426→-2213→-5532→-2766→-1383→-3457→-3111→-5012→-2506→-1253→-3132→-1566→-783
11037→27593→24834→12417→31043→27939→45013→50446→25223→63058→31529→78823→70941→114294→57147→142868→71434→35717→89293→80364→40182→20091→50228→25114→12557→31393→28254→14127→35318→17659→44148→22074→11037
11687→29218→14609→36523→32871→52959→59351→82635→100669→132970→66485→166213→149592→74796→37398→18699→46748→23374→11687

$a_0$ を縦軸、 $a_1$ を横軸とすると分布図はこうなりました。

縞模様が見えますが、分解型複素数のやつと違って色々な角度の線が混じっています。

統計データは以下の通りです。

平均増加率	0.898
over	0(0%)
ループ個数	12個

この数列の平均増加率は以下のような考え方で算出しました。

まず、平均増加率を $r$ と置きます。

平均増加率は「 $a_{n+1}$ が $a_n$ に対して(確率的に)どのくらい大きくなるか」を表す値として導入したものですが、逆に「 $a_n$ が $a_{n+1}$ に対して(確率的に)どのくらい小さかったか」を表していると考えることもできます。

$a_{n+1}$ が奇数のときは $a_{n+2}=\frac{a_{n+1}+1}{2}+a_n$ になりますが、 $a_n$ が $a_{n+1}$ の約 $\frac{1}{r}$ 倍であると考えるとこのときの $a_{n+2}$ は $a_{n+1}$ の約 $\frac{1}{2}+\frac{1}{r}$ 倍であると考えることができます。

$a_{n+1}$ が偶数のときは $a_{n+2}=\frac{a_{n+1}}{2}$ なので、平均増加率の計算式に当てはめると以下のようになります。

$r=\sqrt{\frac{1}{2}×\left(\frac{1}{2}+\frac{1}{r}\right)}$

これを $r$ について解くことで、 $r≒0.898$ という値が出てきます。

ちなみに $r$ についての方程式は3次になりますが、ちゃんと解くのは面倒なのでグラフ描画ツールDesmosに計算させました。

他の数列も試してみましょう。

m/2,m-2n+1

$a_{n+2}=\begin{cases} \frac{a_{n+1}}{2}&\text{if}　a_{n+1}\equiv0\pmod2\\ a_{n+1}-2a_n+1&\text{if}　a_{n+1}\equiv1\pmod2\\ \end{cases}$

平均増加率	0.689
over	0(0%)
ループ個数	3個

先程のものと同じく、向きの違う縞模様が重なった図になりました。

理由はわかりませんが、3項間漸化式を使ったコラッツシステムは同様の性質を持つことが多いっぽいです。

m/2,(m+1)/2+2n

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

平均増加率	1.083
over	3235817(80.3%)
ループ個数	5個

「平均増加率が1を超えると発散しやすくなる」という平均増加率の基本的性質がちゃんと発現しているように見えます。

m/2,(m+1)/2-2n

$a_{n+2}=\begin{cases} \frac{a_{n+1}}{2}&\text{if}　a_{n+1}\equiv0\pmod2\\ \frac{a_{n+1}+1}{2}-2a_n&\text{if}　a_{n+1}\equiv1\pmod2\\ \end{cases}$

平均増加率	0.917
over	1780464(44.5%)
ループ個数	3個

このルールの平均増加率は以下の方程式の解として計算しました。

$r=\sqrt{\frac{1}{2}×\left|\frac{1}{2}-\frac{2}{r}\right|}$

絶対値が付いているのは、 $\frac{1}{2}-\frac{2}{r}$ が負になる可能性がある(実際に計算結果を代入すると負になる)からです。

平均増加率について初めて述べた「コラッツ予想派生問題集(2)」では、係数が負になる場合について以下のように書いています。

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

要するに、「今まで無視してたけど、平均増加率は本来絶対値をつけて計算するものである」ということです。

ちなみに、絶対値をつけずに立てた方程式は正の実数解を持たないようです。

※平方根を外して分母を払って3次方程式にした場合、r=-1.083という実数解があります。

m/2,m+n

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

平均増加率	0.818
over	0(0%)
ループ個数	1501個

このルールの平均増加率は、今までのものと少し違う方法で計算しています。

前回の記事での記法に合わせると、以下のようになります。

(2m,2n)→(m,2m): $\frac{1}{2}$
(2m+1,2n)→(2m+2n+1,2m+1)→(4m+2n+2,2m+2n+1)→(2m+n+1,4m+2n+2): $1+\frac{1}{2r}$ 　※ $m\approx rn$
(2m,2n+1)→(m,2m): $\frac{1}{2}$
(2m+1,2n+1)→(2m+2n+2,2m+1)→(m+n+1,2m+2n+2): $\frac{1}{2}+\frac{1}{2r}$

$r=\left(\frac{1}{2}×\left(1+\frac{1}{2r}\right)×\frac{1}{2}×\left(\frac{1}{2}+\frac{1}{2r}\right)\right)^{\frac{1}{4}}$

最初に紹介したm/2,(m+1)/2+nルール等ではnを2で割った余りが平均増加率に影響しなかったので無視していましたが、このルールでは影響するのでmとnの両方の余りを加味しています。

m/2,m+n+1

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

平均増加率	∞
over	999999(25.0%)
ループ個数	6個

平均増加率が∞なのに分布図が黒くないように見えますが、拡大してみると以下のようになっています。

どうやら $a_{n+1}$ と $a_n$ が両方奇数の時((-1,-1)を除く)に発散し、それ以外の場合は発散しないようです。

実際、奇数が2つ並んだ場合は以下のようになります。

(2m+1,2n+1)→(2m+2n+3,2m+1)

2m+2n+3と2m+1は両方奇数なので、この後も永久に奇数が出続けることがわかります。

m/2,m+n+2

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

平均増加率	0.818
over	0(0%)
ループ個数	2個

m/2,m+n+1ルールのような細かい格子模様が見えます。

m/2,m+n+kという形の数列は、kの値によって以下のように特徴がわかれるようです。

kが奇数→(2m+1,2n+1)の組み合わせの時だけ発散
kを4で割った余りが2→発散しない
kが4の倍数(0を除く)→ほぼすべての初期値で発散

k	平均増加率(mod 2)	over	ループ個数	k	平均増加率(mod 2)	over	ループ個数
0	0.818	0(0%)	1501	1	∞	999999(25.0%)	6
2	0.818	0(0%)	2	3	∞	999999(25.0%)	6
4	0.818	4000502(99.9%)	1	5	∞	999999(25.0%)	11
6	0.818	0(0%)	3	7	∞	999999(25.0%)	7
8	0.818	4000504(99.9%)	1	9	∞	999999(25.0%)	6
10	0.818	0(0%)	3	11	∞	999999(25.0%)	9
12	0.818	4000506(99.9%)	1	13	∞	999999(25.0%)	15
14	0.818	0(0%)	4	15	∞	999999(25.0%)	11

kが4の倍数の時の平均増加率は0.818ですが、mod 4に細分化すると以下のような発散パターンが発生します。

(4m+2,n)→(2m+1,4m+2)→(6m+4j+3,2m+1)→(8m+8j+4,6m+4j+3)→(4m+4j+2,8m+8j+4)

※k=4j

$a_{n+1}$ を4で割った余りが2になると、 $a_n$ の値に関係なく発散するようです。

ちなみに、この場合の発散スピードは1次関数オーダー(従来のものは指数関数オーダー)なので、今まで使っていたプログラムでは正常に発散判定ができず、手直しが必要になりました。

m/2,m-n+k

$a_{n+2}=\begin{cases} \frac{a_{n+1}}{2}&\text{if}　a_{n+1}\equiv0\pmod2\\ a_{n+1}-a_n+k&\text{if}　a_{n+1}\equiv1\pmod2\\ \end{cases}$

k	平均増加率(mod 2)	over	ループ個数
0	0.551	0(0%)	501
1	0.560	0(0%)	250501
2	0.551	0(0%)	501
3	0.560	0(0%)	251496

kが奇数の時のループ個数がとんでもないことになっていますが、これは以下のようなループが存在するためです。

(2m+1,2n+1)→(2m-2n+2j+1,2m+1)→(-2n+4j+1,2m-2n+2j+1)→(-2m+4j+1,-2n+4j+1)→(-2m+2n+2j+1,-2m+4j+1)→(2n+1,-2m+2n+2j+1)→(2m+1,2n+1)

※k=2j+1

なお平均増加率の計算でもこのループが出てくるのですが、その場合の因子(平均増加率の計算で相乗平均をとる値のこと)の値は1としました。

m/2,m-3n+k

$a_{n+2}=\begin{cases} \frac{a_{n+1}}{2}&\text{if}　a_{n+1}\equiv0\pmod2\\ a_{n+1}-3a_n+k&\text{if}　a_{n+1}\equiv1\pmod2\\ \end{cases}$

k	平均増加率(mod 2)	over	ループ個数	k	平均増加率(mod 2)	over	ループ個数
0	0.926	0(0%)	1251	1	∞	3319215(82.9%)	2
2	0.926	4001334(99.9%)	1	3	∞	2992498(74.7%)	5
4	0.926	0(0%)	1	5	∞	2861380(71.5%)	2
6	0.926	3976015(99.3%)	2	7	∞	3248076(81.1%)	5
8	0.926	0(0%)	1255	9	∞	3249304(81.2%)	6
10	0.926	4001334(99.9%)	1	11	∞	2886670(72.1%)	8
12	0.926	0(0%)	2	13	∞	2765302(69.1%)	5
14	0.926	4001334(99.9%)	1	15	∞	2438735(60.9%)	5
16	0.926	0(0%)	1258	17	∞	3174041(79.3%)	3
18	0.926	3979032(99.4%)	2	19	∞	3524526(88.0%)	4

kを8で割った余りによって挙動がわかれるようです。なんで？

m/2-n,m-n

$a_{n+2}=\begin{cases} \frac{a_{n+1}}{2}-a_n&\text{if}　a_{n+1}\equiv0\pmod2\\ a_{n+1}-a_n&\text{if}　a_{n+1}\equiv1\pmod2\\ \end{cases}$

今までは $a_n$ の値を使うのは $a_{n+1}$ が奇数の時だけでしたが、偶数の時も3項間漸化式になるようにしてみました。

平均増加率	0.768
over	?(?%)
ループ個数	?個

このルールは以下のような周期の長いループがたくさん(おそらく無限個)存在するのが特徴です。

(1,3)→(-2,1)→(-2,-2)→(1,-2)→(3,1)→(2,3)→(-2,2)→(-3,-2)→(-1,-3)→(2,-1)→(2,2)→(-1,2)→(-3,-1)→(-2,-3)→(2,-2)→(3,2)→(1,3)
(1,10)→(-9,1)→(-10,-9)→(4,-10)→(12,4)→(2,12)→(-11,2)→(-13,-11)→(-2,-13)→(12,-2)→(8,12)→(-8,8)→(-12,-8)→(2,-12)→(13,2)→(11,13)→(-2,11)→(-12,-2)→(-4,-12)→(10,-4)→(9,10)→(-1,9)→(-10,-1)→(-4,-10)→(8,-4)→(8,8)→(-4,8)→(-10,-4)→(-1,-10)→(9,-1)→(10,9)→(-4,10)→(-12,-4)→(-2,-12)→(11,-2)→(13,11)→(2,13)→(-12,2)→(-8,-12)→(8,-8)→(12,8)→(-2,12)→(-13,-2)→(-11,-13)→(2,-11)→(12,2)→(4,12)→(-10,4)→(-9,-10)→(1,-9)→(10,1)→(4,10)→(-8,4)→(-8,-8)→(4,-8)→(10,4)→(1,10)

しかし、以下の理由により統計データの取得は断念せざるを得ませんでした。

発散速度が1次関数オーダーで、さらに「 $a_{n+1}$ を4で割った余りが2」みたいな簡単な判別方法が見つからなかった
周期が長すぎて本当にループに入ってるのか判別できてないっぽいケースがあった

連立と統一

数列の定義の形式として、以下のようなものもあります。

$(a_{n+1},b_{n+1})=(a_n+b_n,a_nb_n)$

こういう形の漸化式を、「連立漸化式」というそうです。

※一般的な連立漸化式の書き方とは違うようですが、この記事では描きやすさを重視してこの書式を使用します。

それでは連立漸化式を使ったコラッツシステムを・・・と行きたいところですが、実はこの記事では既に連立漸化式を使ったコラッツシステム(と同等なもの)を紹介しています。

以下の数列は、この記事で最初に紹介したガウス整数上でのコラッツシステムです。

この数列は、複素数としての実部と虚部を別の数列と見做すことにより、以下のような連立コラッツシステムと同等のものであると考えることができます。

$(a_{n+1},b_{n+1})=\begin{cases} (\frac{a_n}{2},\frac{b_n}{2})&\text{if}　(a_n,b_n)\equiv(0,0)\pmod2\\ (3a_n+1,3b_n)&\text{if}　(a_n,b_n)\equiv(1,0)\pmod2\\ (2a_n-b_n+1,a_n+2b_n)&\text{if}　(a_n,b_n)\equiv(0,1)\pmod2\\ (2a_n-b_n+1,a_n+2b_n+1)&\text{if}　(a_n,b_n)\equiv(1,1)\pmod2\\ \end{cases}$

同様に考えると、これまでこの記事で紹介した「ガウス整数上のコラッツシステム」「代数体の整数環上のコラッツシステム」「3項間漸化式によるコラッツシステム」は全て、連立コラッツシステムとして表せるように思えます。

アイゼンシュタイン整数上での3分岐の数列は以下のように表せます。

　　　　　↓↓↓

$(a_{n+1},b_{n+1})=\begin{cases} (\frac{a_n+b_n}{3},\frac{-a_n+2b_n}{3})&\text{if}　a_n-2b_n\equiv0&\pmod3\\ (5a_n+1,5b_n)&\text{if}　a_n-2b_n\equiv1&\pmod3\\ (\frac{a_n+b_n+1}{3},\frac{-a_n+2b_n+1}{3})&\text{if}　a_n-2b_n\equiv2&\pmod3\\ \end{cases}$

分岐条件に $a_n-2b_n$ とかいう謎の式が出てきてますが、これを使わずに表すこともできます。

$(a_{n+1},b_{n+1})=\begin{cases} (\frac{a_n+b_n}{3},\frac{-a_n+2b_n}{3})&\text{if}　(a_n,b_n)\equiv(0,0)&\pmod3\\ (5a_n+1,5b_n)&\text{if}　(a_n,b_n)\equiv(1,0)&\pmod3\\ (\frac{a_n+b_n+1}{3},\frac{-a_n+2b_n+1}{3})&\text{if}　(a_n,b_n)\equiv(2,0)&\pmod3\\ (5a_n+1,5b_n)&\text{if}　(a_n,b_n)\equiv(0,1)&\pmod3\\ (\frac{a_n+b_n+1}{3},\frac{-a_n+2b_n+1}{3})&\text{if}　(a_n,b_n)\equiv(1,1)&\pmod3\\ (\frac{a_n+b_n}{3},\frac{-a_n+2b_n}{3})&\text{if}　(a_n,b_n)\equiv(2,1)&\pmod3\\ (\frac{a_n+b_n+1}{3},\frac{-a_n+2b_n+1}{3})&\text{if}　(a_n,b_n)\equiv(0,2)&\pmod3\\ (\frac{a_n+b_n}{3},\frac{-a_n+2b_n}{3})&\text{if}　(a_n,b_n)\equiv(1,2)&\pmod3\\ (5a_n+1,5b_n)&\text{if}　(a_n,b_n)\equiv(2,2)&\pmod3\\ \end{cases}$

3項間漸化式の場合は、以下のようになります

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

　　　　↓↓↓

$(a_{n+1},b_{n+1})\begin{cases} (\frac{a_n}{2},a_n)&\text{if}　a_n\equiv0\pmod2\\ (\frac{a_n+1}{2}-b_n,a_n)&\text{if}　a_n\equiv1\pmod2 \end{cases}$

3項漸化式の方での $a_n$ の値を $b_n$ に保存するようにしただけです。

なお、この記事で紹介してきた3項漸化コラッツシステムを連立コラッツシステムに変換した場合、当然ですが分岐条件には $a_n$ しかでてきません。

実は「 $a_{n+1}$ と $a_n$ を両方分岐条件に使う3項漸化コラッツシステム」というのを考えることもできて、そういうものであれば連立コラッツシステムに変換した場合の分岐条件に $b_n$ が出てきます。(触れていくときりがないので今回はスルーします)

さて、このように既存のコラッツシステムは連立コラッツシステムを使って表すことができそうです。

ということは、連立コラッツシステムを研究することによって、異なる方向へ進化していったコラッツシステムたちを統一的に扱える理論を構築できることが期待できるのではないでしょうか。

というわけでその第一歩として、連立コラッツシステムにおける平均増加率の計算法を考えてみました。

例として、ついさっき紹介した「ガウス整数上のコラッツシステムを連立コラッツシステムに翻訳したもの」を使います。

まず、3項間漸化式の時と同様に $a_n$ と $b_n$ を2で割った余りの組み合わせの全4パターンに対して数列を計算します。

(2m,2n)→(m,n)
(2m+1,2n)→(6m+4,6n)→(3m+2,3n)
(2m,2n+1)→(4m-2n,2m+4n+2)→(2m-n,m+2n+1)
(2m+1,2n+1)→(4m-2n+2,2m+4n+4)→(2m-n+1,m+2n+2)

3項間漸化式のときは各因子に対してnが与える影響の強さをmの1/r倍としていましたが、今回は平均増加率rとは異なる正の定数"s"を用いて1/s倍として計算できると考えます。

これにより、それぞれの組み合わせにおける因子は以下のようになります。

(2m,2n)→(m,n)： $(\frac{1}{2},\frac{1}{2})$
(2m+1,2n)→(6m+4,6n)→(3m+2,3n)： $(\frac{3}{2},\frac{3}{2})$
(2m,2n+1)→(4m-2n,2m+4n+2)→(2m-n,m+2n+1)： $(|1-\frac{1}{2s}|,\frac{s}{2}+1)$
(2m+1,2n+1)→(4m-2n+2,2m+4n+4)→(2m-n+1,m+2n+2)： $(|1-\frac{1}{2s}|,\frac{s}{2}+1)$

そして、 $a_n$ と $b_n$ がどちらも同じ平均増加率rを持つとすると、rとsに関する以下のような連立方程式を立てることができます。

$\begin{cases}r=\left(\frac{1}{2}×\frac{3}{2}×\left|1-\frac{1}{2s}\right|×\left|1-\frac{1}{2s}\right|\right)^{\frac{1}{4}}\\ r=\left(\frac{1}{2}×\frac{3}{2}×\left(\frac{s}{2}+1\right)×\left(\frac{s}{2}+1\right)\right)^{\frac{1}{4}}\end{cases}$

これを解くと、 $(r,s)≒(0.984,0.236)$ という値が出てきます。

※sが負の解もあるのですが、「sは正」と決めたので無視することにします。

この数列の元になったガウス整数上のコラッツシステムの平均増加率は1未満だったので、それと矛盾しない結果が得られました。

次は、元の数列で平均増加率が正しく計算できなかったものを調べてみましょう。

これらはℤ[√2]上のコラッツシステムとして紹介した数列で、以下のような性質がわかっていました。

ノルムを用いて計算した平均増加率は、➀➁➂の全てで同じ値(約0.839)になった
実数としての絶対値を用いて計算した平均増加率は、➁が0.614で➂が1.15になった
収束性の強い数列は➀だけだった

以上のことから、「ℤ[√2]上ではノルムも絶対値も平均増加率の計算には使えない」と判断したのでした。

もし連立コラッツシステムとしての平均増加率が「➀は1未満、➁と➂は1以上」になれば数列の性質と合致し、連立コラッツシステムにおける平均増加率の有用性を裏付ける証拠となりそうです。

そして、実際の結果がこちらです。

	方程式	解
➀	$\begin{cases}r=\left(\frac{1}{2}×\frac{3}{2}×\left(\frac{3}{2}+\frac{1}{s}\right)×\frac{1}{2}\right)^{\frac{1}{4}}\\r=\left(\frac{1}{2}×\frac{3}{2}×\left(\frac{1}{2}s+\frac{3}{2}\right)×\frac{1}{2}\right)^{\frac{1}{4}}\end{cases}$	$(r,s)≒(0.954,1.41)$
➁	$\begin{cases}r=\left(\frac{1}{2}×\frac{3}{2}×\left(\frac{5}{2}+\frac{3}{s}\right)×\frac{1}{2}\right)^{\frac{1}{4}}\\r=\left(\frac{1}{2}×\frac{3}{2}×\left(\frac{3}{2}s+\frac{5}{2}\right)×\frac{1}{2}\right)^{\frac{1}{4}}\end{cases}$	$(r,s)≒(1.15,1.41)$
➂	$\begin{cases}r=\left(\frac{1}{2}×\frac{3}{2}×\begin{vmatrix}\frac{5}{2}-\frac{3}{s}\end{vmatrix}×\frac{1}{2}\right)^{\frac{1}{4}}\\r=\left(\frac{1}{2}×\frac{3}{2}×\begin{vmatrix}-\frac{3}{2}s+\frac{5}{2}\end{vmatrix}×\frac{1}{2}\right)^{\frac{1}{4}}\end{cases}$	$(r,s)≒(0.839,0.785),(0.614,1.41),(0.839,2.55)$

➂では3つの解が見つかりましたが、残念ながらどの解でもrは1を超えませんでした。

しかし、グラフをよく見てみるとsが負になる範囲にも1つ解があり、こちらはr>1になっています。

元々、「sは正である」という制約は特に根拠もなく決めたものでした。

なので、解を1つに絞り込むためのより合理的な基準を定めることができればこの問題を解決できる可能性があります。

まぁ何にせよ、解が複数ある場合の解釈の仕方について改善が必要なのは確かです。(ガウス整数上では数列の性質と平均増加率の大きさが合わないケースもありましたし、そもそも「発散性」というもの自体有限の観測結果に頼った不確かなものです)

最後に

一番最初の記事で拾いきれなかった話題は、これでほぼすべて回収できました。

というわけで、このシリーズは一旦ここで完結という事にしたいと思います。

ここまで読んでくださりありがとうございました。

おまけ

今まで紹介してきた問題とは違う形式だけど、コラッツ予想派生問題と若干雰囲気が近いものを紹介します。

ジャグラー数列

ジャグラー数列は、以下の通り定義される数列です。

$a_{n+1}=\begin{cases}\floor{a_n^{\frac{1}{2}}}&\text{if}　　a_n\equiv0&\pmod2\\\floor{a_n^{\frac{3}{2}}}&\text{if}　　a_n\equiv1&\pmod2\end{cases}$

en.wikipedia.org

コラッツ予想と同じく、どんな初期値に対してもジャグラー数列は1に到達すると予想されているそうです。

$a_n$ の代わりに $\text{log}(a_n)$ (底は何でもいい)を考えると、 $\text{log}(a_n)$ は $a_n$ が偶数のとき約 $\frac{1}{2}$ 倍、奇数のとき $\frac{3}{2}$ 倍になるのでコラッツ数列と同様に $\left(\frac{1}{2}×\frac{3}{2}\right)^{\frac{1}{2}}≒0.866$ の平均増加率を持つと考えることができます。

アリコット数列

アリコット数列は、以下の通り定義される数列です。

$a_{n+1}=\sigma(a_n)-a_n$

ただし、 $\sigma(k)$ は $k$ の約数和です。

ja.wikipedia.org

アリコット数列は最終的に以下のどれかのパターンになります。

(1)　素数→1→0(σ(0)は未定義)

(2)　ループに入る

(3)　発散する

(2)におけるループの要素となる数は、1周期の時は完全数、2周期の時は友愛数、3周期以上は社交数と呼ばれ、例えば以下のような例が存在します。

6→6(6は完全数)
220→284→220((220,284)は友愛数)
12496→14288→15472→14536→14264→12496((12496,14288,15472,14536,14264)は5個組の社交数)

これらの数に対して、以下のような未解決問題があります。

完全数は無限に存在するか
奇数の完全数は存在するか
友愛数は無限に存在するか
偶数と奇数の友愛数のペアは存在するか
社交数は無限に存在するか
3個、7個、10個組の社交数は存在するか

また、(3)については276から始まるアリコット数列が発散すると考えられているものの、実際に発散することは証明されておらず(3)のケースが実在するかどうかは未解決だそうです。

リクレル数

「ある自然数と、その自然数を左右反転させた自然数を足す」という操作をリクレルプロセスといいます。

そして、リクレルプロセスを何回適用しても回文数にならない自然数をリクレル数といいます。

ja.wikipedia.org

例えば、89に対してリクレルプロセスを繰り返すと以下のような数列が生成されます。

89→187→968→1837→9218→17347→91718→173437→907808→1716517→8872688→17735476→85189247→159487405→664272356→1317544822→3602001953→7193004016→13297007933→47267087164→93445163438→176881317877→955594506548→1801200002107→8813200023188

8813200023188は回文数なので、89はリクレル数ではないことがわかります。

一方、196はリクレルプロセスを10億回適用しても回文数にならず、リクレル数であると予想されているそうです。