Collatz問題 #21

ある値から操作前の値へと遡ることを考える。
その値の6を法とする剰余が4になるとき、
その値を2倍した値と1を引いて3で割った値の二つは共に操作前の値である。
つまり6を法とする剰余が4になる値のノードは二つの値のノードからの合流ノードとなる。
また、逆に剰余が4でない値のノードは合流ノードとならない。

全てのノードはその値を2倍した値のノードからの入力を受ける。
さらに6を法とする剰余が4の場合はであるから、
操作前の値が奇数の場合は3倍して1を加えるという操作によってもその値を生成することができる。
逆に操作前の値が奇数の場合全てについて操作後の値の剰余が4になることを網羅しているので、
剰余が4でない値のノードは合流ノードにはならない。

6を法とする剰余が4以外の場合の挙動はどうなるのだろうか？
剰余が0の場合、半分にする操作を何回遡ろうとも剰余は0であるので合流ノードが現れることはない。
剰余が1の場合、半分にする操作を2回遡ると剰余が4になり、これが合流ノードとなる。
剰余が2の場合、半分にする操作を1回遡ると合流ノードとなる。
剰余が3の場合、半分にする操作を1回遡ると剰余が0となり、剰余が0の場合と同様いくら遡っても合流ノードは現れない。
剰余が5の場合、半分にする操作を1回遡ると剰余が4になり、これが合流ノードとなる。

剰余が0と3のとき、つまり3の倍数の場合は操作をどれだけ遡っても合流ノードは現れないことになる。

合流ノードからさらに半分にする操作の方を1回遡ると剰余は2となり、
さらに1回遡ると剰余は4となるので再び合流ノードとなる。

1を除く2のべき乗の場合、その6を法とする剰余は4のべき乗で4、4のべき乗の2倍のとき2となる。
これは、2と4では自明であり、


半分にする操作を1回遡るごとに2と4とが交互に剰余となる。
すなわち、合流ノードと非合流ノードが交互に繰り返される。

合流ノードから3倍して1を加える操作の方を1回遡った値は6を法とする剰余が4になることはない。
なぜならその値は奇数でなければならないからである。つまり合流ノードにはならない。

これらから、1から操作を遡っていく場合、
2のべき乗の経路を遡ると合流ノードと非合流ノードが交互に現れ、
合流ノードから3倍して1を加える操作の方を遡ると、
その値が3の倍数ならばそれ以降は合流ノードが現れず、
それ以外の場合は操作を1回か2回遡れば再び合流ノードが現れ、
それ以降非合流ノードと合流ノードが交互に現れる。