shuraba.com - コラッツ問題

コラッツ問題

一九三七年にローター・コラッツ Lothar Collatz が提起した。「コラッツ予想」「角谷問題（予想）」「Syracuse 予想」「3n + 1 問題」とも呼ばれる。

任意の自然数 n をとり、

• n が偶数なら 2 で割る
• n が奇数なら 3 を掛けて 1 を足す

という操作を繰り返すと、有限回で 1 に到達する。

この命題の真偽はまだ証明されていない。コンピュータによって 3 × 2⁵³ = 27,021,597,764,222,976 までの n が調べられているが、反例は存在していない。

コラッツ数列

n から始まり、1 に到達するまでに出現する数からなる数列をコラッツ数列という。例えば n = 5 のときのコラッツ数列は「5, 16, 8, 4, 2, 1」である。

コラッツ数列 collatzArray を得るプログラムを考えよう。n = 1 のとき、数列は「1, 4, 2, 1」を繰り返すので、n = 1、あるいは数列が 1 に到達したときに処理は終了する。Javascript では以下のようになる。

function collatz (n) {
　var collatzArray = new Array (n);
　while (n != 1) {
　　if (n%2 == 0) {
　　　n = n/2;
　　} else {
　　　n = n*3+1;
　　}
　　collatzArray.push(n);
　}
　return collatzArray;
}

では、コラッツ数列を求めてみよう。

の コラッツ数列