偽計数学妨害罪

うるせぇ、こっちは遊びで数学やってんだよ

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


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


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



www.tbsradio.jp


☟第0弾
hassium277.hatenablog.com


☟第1弾
hassium277.hatenablog.com


☟第2弾
hassium277.hatenablog.com

続・ガウス整数

前回と前々回の両方でガウス整数版のコラッツシステムの話をしましたが、扱った数列は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.866
over 1526070(38.1%)
ループ個数 62個



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

☝よく似た模様


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


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

☝n/2,15in+i,(n+i)/2,(n+1+i)/2
☝n/2,(n+1)/2,(n+i)/2,(15+5i)n

異世界転生

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


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


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


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

アイゼンシュタイン整数

アイゼンシュタイン整数は、整数ab\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\omega2+\omegaで割った余り」は「x-2yを3で割った余り」として計算できます。


ところが、x-2yが負になった場合は3で割った余りも負になってしまい、例えばProcessingに「1+3\omega2+\omegaで割った余りは1ですか?」と聞いた場合、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]は、整数abを使って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次体に関する記事を眺めてみると、以下のようなことが書かれていました。

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


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

整数環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数列の自然な拡張になっていることがわかります。

☝c=0

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

☝c=1
☝c=-1


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


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


何故毎回こうなるのかというと、おそらく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数列の自然な拡張になっているように見えます。


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

☝c=d=0

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

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


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


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

☝b=c=0
over 0(0%)
ループ個数 16個
☝a=c=0
over 384361(9.60%)
ループ個数 67個
☝a=b=0
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_na_{n+1}に対して(確率的に)どのくらい小さかったか」を表していると考えることもできます。


a_{n+1}が奇数のときはa_{n+2}=\frac{a_{n+1}+1}{2}+a_nになりますが、a_na_{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に計算させました。

☝r≒0.898


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

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の係数ではなくその絶対値を計算に使えばいいだけです。


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


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

☝青の曲線はx軸と交わらない

平方根を外して分母を払って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=1の中心部の拡大図


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,10)を含む56周期のループ


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

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

連立と統一

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


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


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

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


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


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


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}


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


(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}=\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}

     ↓↓↓

(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が出てきます。(触れていくときりがないので今回はスルーします)


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


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


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


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


(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項間漸化式の時と同様にa_nb_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_nb_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未満だったので、それと矛盾しない結果が得られました。


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


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}  ・・・➀


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}  ・・・➁


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}  ・・・➂


これらはℤ[√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)については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億回適用しても回文数にならず、リクレル数であると予想されているそうです。