prog*sig

コラッツの問題について考える。
問題の概要は、「任意の0でない自然数 n をとり、

• n が偶数の場合、n を 2 で割る
• n が奇数の場合、n に 3 をかけて 1 を足す

という操作を繰り返すと、有限回で 1 に到達する」という主張である（1 に到達すると、1→4→2→1 を繰り返す）。

適当にJavaScriptで書いてみると、以下のような感じ。

function collatz(n) {
    if (n > 1) {
        collatz.count++;
        if (n % 2 === 0) {
            return collatz(n / 2);
        } else {
            return collatz((n * 3) + 1);
        }
    } else if (n === 1) {
        var stepCount = collatz.count;
        collatz.count = 0;// 初期値
        // step数を返す
        return stepCount;
    } else {
        collatz.count = 0;
        return "対象の範囲外の数値";
    }
}
collatz.count = 0;
console.log(collatz(6));    //step : 8
console.log(collatz(1000)); //step : 111
console.log(collatz(31000));//step : 54
var res = [];
for (var i = 0,len = 100; i < len; i++) {
    res[i] = [i,collatz(i)];
}
console.table(res);// ["i" , "step"]

必ずしも与えた値が大きいほどstep数がかかる訳ではないようだ。
ループで回す場合はもっと最適化できて、既に1になる事が分かる数値がnならば、そこで計算をやめられるはず。メモ化みたいなやつ。