(改造版)コラッツの予想

さて、今回もawkでパズルを解いてみます。

コラッツの予想
自然数nについて、
・nが偶数の場合、nを2で割る
・nが奇数の場合、nに3をかけて1を足す
という操作を繰り返すとき、初期値がどんな数であっても必ず1に到達する
(1→4→2→1のように繰り返す)

この予想の内容を少し変えて、初期値が偶数の場合、初回のみnに3をかけて1を
足すことから始めることとし、「最初の数」に戻るものを考えます。

2→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2

4→13→40→20→10→5→16→8→4

10000以下の偶数のうち、「最初の数にもどる数」がいくつあるでしょうか？

awkも他の言語と同様、再帰呼出しが使えます。
今回は再帰で解きました。

#!/usr/bin/awk -f

BEGIN{
    n = 2;
    cnt = 0;
    while(n <= 10000){
        f = 1;
        num = n;
        collatz(n,num,f);

        n += 2;
    }
    print cnt;
}

function collatz(n,num,first){
    if(first != 1 && n == num){
        cnt++;
        return;
    }
    if(n == 1){
        return;
    }
    if(n % 2 == 0){         # 偶数なら
        if(first == 1){     # 初回のみ
            first++;
            return collatz(n * 3 + 1,num,first);
        }else{
            return collatz(n / 2,num,first);
        }
    }else{                  # 奇数なら
        return collatz(n * 3 + 1,num,first);
    }
}

実行してみます。

awk -f q06.awk 
34