Collatz問題 #25

#7で作成した65536までの初期値と操作回数の散布図のためのデータを出力するプログラムcollatzから、
1に至るまでの操作回数が最大となる初期値を求める。

$ ./collatz | sort -n -k2 | tail
47329 313
60169 316
61999 316
63105 316
53483 321
56095 321
35655 323
63387 329
60975 334
52527 339

第2フィールド（操作回数）を数値キーとして昇順ソートし、その末尾を表示する。
初期値52527で339回の操作が必要になるのが最大であることが分かる。
この52527から1への経路をプロットする。

$ ./collatz13 52527 > p52527.dat

で得られる経路データから、

gnuplot> m = 339
gnuplot> plot 'p52527.dat' using 1:(up($2, $3, m)) w l, '' using 1:(down($2, $3, m)) w l lt 3

初期値97の場合と異なり、急速に最大値まで上昇した後、
下降の連続で値を下げる時と上昇と下降が拮抗もしくは少しずつ上昇する時とがあり、
最後に下降する操作が優勢になって1へ下降していく。

と、このプロットの操作回数100回以下の辺りを見ていると、
初期値97のプロットにそっくりな気がする。
少なくとも80回より小さい領域はそっくりである。
ただ、90回あたりにある4回連続の下降操作が初期値97の場合には存在しないので、
ここかこれより下のどこかで二つの経路は合流しているのだろうと見当がつく。
この近辺の6で割って4余る値がその候補であるので探索すると、
94回の操作で1に達する値364が二経路の合流点であった。

52527 -> ... -> 728 -> 364
   97 -> ... -> 121 -> 364

ちなみに364は上で述べた90回辺りにある4連続下降操作の中間点になっている。
初期値52527からの経路上でとる最大値は、

$ sort -n p52527.dat | tail
56023972 83 1
56023972 84 0
59826388 101 1
59826388 102 0
70905346 93 1
70905346 94 0
79768516 98 1
79768516 99 0
106358020 95 1
106358020 96 0

から、106358020であり、1億を超える値となるがまだ余裕で32ビット整数の範囲内である。
52527から95回目の操作で最大値に達し、その後、339-96+1=244回の操作で1に至る。