mod 上でのコラッツ数列

コラッツ数列

半減：$ a_n/2\quad(a_n\overset2\equiv0)

偶数化：$ a_{n+1}=3a_n+1\quad(a_n\overset2\equiv1)

逆順に辿る

偶数化の逆操作（奇数化）の条件を求める

$ a_n=2k+1とすると

$ 3(2k+1)+1=6k+4

より奇数化は$ a_{n+1}\overset6\equiv4

逆操作は

初期値：$ x_1=1

倍増：$ x_{n+1}=2x_n\quad(\forall x_n)

奇数化：$ (x_n-1)/3\quad(x_n\overset6\equiv4)

この操作を図に描いていくと木のようになる

$ 4\ ({\rm mod}\,6)で枝分かれする

mod 6 上での逆操作を全て見ていこう

$ 6k+0\quad\to\quad6\cdot2k+0

$ 6k+1\quad\to\quad6\cdot2k+2

$ 6k+2\quad\to\quad6\cdot2k+4

$ 6k+3\quad\to\quad6\cdot2(k+1)+6

$ 6k+4\quad\to\quad\begin{cases}6\cdot2(k+1)+2\\2k+1\end{cases}

$ 6k+5\quad\to\quad6\cdot2(k+1)+4

逆操作の性質

3の倍数になると分岐が無くなり倍加のみが行われる

つまり、$ 3(2k+1)\cdot2^nの形の枝がある。

倍加により$ \overset{\rm mod\,6}{2,4}が繰り返される。

木から$ \overset{\rm mod\,6}{2}を除去するとより本質的な情報のみが残るようになる。

逆操作 ver2 を作ろう。

初期値：$ x_1=1

4倍増：$ x_{n+1}=4x_n\quad(x_n\,\overset6{\not\equiv}\,5)

倍増：$ x_{n+1}=2x_n\quad(x_n\overset6\equiv5)

奇数化：$ (x_n-1)/3\quad(x_n\overset6\equiv4)

倍増は奇数化の後にのみ実行される。

→奇数化と合成してみよう

奇数化後の分岐は、$ 3で割った後の$ {\rm mod}\,6の値により生じるので、

奇数化前に判定するには$ {\rm mod}\,18の値を調べれば良い。

$ 18k+4\quad\overset{(x_n-1)/3}→\quad6k+1\quad\overset{4x_n}→\quad24k+4

$ 18k+10\quad\overset{(x_n-1)/3}→\quad6k+3\quad\overset{4x_n}→\quad24k+12

$ 18k+16\quad\overset{(x_n-1)/3}→\quad6k+5\quad\overset{2x_n}→\quad12k+10

逆操作 ver3：

初期値：$ x_1=1

4倍増：$ x_{n+1}=4x_n\quad(\forall x_n)

奇数化&4倍増：$ 4(x_n-1)/3\quad(x_n\overset{18}\equiv4,10)

奇数化&倍増：$ 2(x_n-1)/3\quad(x_n\overset{18}\equiv16)

この後$ {\rm mod}\,36や$ {\rm mod}\,72にすると更に挙動が改善されるのだが、何を改善しようとして法を選んだのかを思い出せない。

https://gyazo.com/2fbe9bd85fd62e52b3af58a1a79603fc

色分けは$ {\rm mod}\,6、数は$ {\rm mod}\,72