1．定義、プログラム

定義

自然数 n に対して次のような操作を行う。

n が偶数 ⇒ n=n/2 とする
n が奇数 ⇒ n=3*n+1 とする

この操作を次々と適用し、n の挙動を観察してみる。

例 n=3 のとき

3 ⇒ 10 ⇒ 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 ⇒ 4 ⇒ 2 ⇒ 1 ⇒ ......

例 n=7 のとき

7 ⇒ 22 ⇒ 11 ⇒ 34 ⇒ 17 ⇒ 52 ⇒ 26 ⇒ 13 ⇒ 40 ⇒ 20 ⇒ 10 ⇒ 5 ⇒
以下 n=5 のときと同じ

例 n=9 のとき

9 ⇒ 28 ⇒ 14 ⇒ 7 ⇒
以下 n=7 のときと同じ

このように、どのような n についても、最終的には 4 ⇒ 2 ⇒ 1 というループに行き着くように見える。
これを発見者の名前にちなんで Collatz 予想 と呼ぶ。有名な未解決問題である。

プログラム

上の例を見る限り、1 に収束するのがあたりまえのように思えるが、
次の例の場合、本当に 1 に収束するのかどうかすぐにはわからない。

例 n=27 のとき

27 ⇒ 82 ⇒ 41 ⇒ 124 ⇒ 62 ⇒ 31 ⇒ 94 ⇒ 47 ⇒ 142 ⇒ 71 ⇒ 214 ⇒ 107 ⇒ ......

手計算ではらちがあかないので、プログラムを組んでみることにする。
定義をそのままプログラム化すればよい。

10   ' collatz
20   input N:print N;
30   if odd(N) then N=N*3+1 else N=N\2
40   print " ⇒ ";N;
50   if N=1 then print:goto 20 else goto 30

実行して n に 27 を代入してみる。

27 ⇒ 82 ⇒ 41 ⇒ 124 ⇒ 62 ⇒ 31 ⇒ 94 ⇒ 47 ⇒ 142 ⇒ 71 ⇒ 214 ⇒ 107 ⇒ 322 ⇒ 161 ⇒ 484 ⇒ 242 ⇒ 121 ⇒ 364 ⇒ 182 ⇒ 91 ⇒ 274 ⇒ 137 ⇒ 412 ⇒ 206 ⇒ 103 ⇒ 310 ⇒ 155 ⇒ 466 ⇒ 233 ⇒ 700 ⇒ 350 ⇒ 175 ⇒ 526 ⇒ 263 ⇒ 790 ⇒ 395 ⇒ 1186 ⇒ 593 ⇒ 1780 ⇒ 890 ⇒ 445 ⇒ 1336 ⇒ 668 ⇒ 334 ⇒ 167 ⇒ 502 ⇒ 251 ⇒ 754 ⇒ 377 ⇒ 1132 ⇒ 566 ⇒ 283 ⇒ 850 ⇒ 425 ⇒ 1276 ⇒ 638 ⇒ 319 ⇒ 958 ⇒ 479 ⇒ 1438 ⇒ 719 ⇒ 2158 ⇒ 1079 ⇒ 3238 ⇒ 1619 ⇒ 4858 ⇒ 2429 ⇒ 7288 ⇒ 3644 ⇒ 1822 ⇒ 911 ⇒ 2734 ⇒ 1367 ⇒ 4102 ⇒ 2051 ⇒ 6154 ⇒ 3077 ⇒ 9232 ⇒ 4616 ⇒ 2308 ⇒ 1154 ⇒ 577 ⇒ 1732 ⇒ 866 ⇒ 433 ⇒ 1300 ⇒ 650 ⇒ 325 ⇒ 976 ⇒ 488 ⇒ 244 ⇒ 122 ⇒ 61 ⇒ 184 ⇒ 92 ⇒ 46 ⇒ 23 ⇒ 70 ⇒ 35 ⇒ 106 ⇒ 53 ⇒ 160 ⇒ 80 ⇒ 40 ⇒ 20 ⇒ 10 ⇒ 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1

途中で 9232 になったのが最大であり、112 世代目にして 1 に収束した。