ハッピーナンバーの判定

C/C++の宿題を片付けます@wiki - C++の宿題/HappyNumberHappyNumberの判定 - みずぴー日記 にインスパイヤされて、awk でも行ってみました。

なお、ハッピーナンバーとは以下のようなものだそうで、1 か 4 に収束し、4 の場合には無限ループになるというもののようです。 この性質を使うことにします。

HappyNumberとは、正整数nの各桁の数を2乗し、その合計を求め、その合計の
各桁の数を2乗し、またその合計を求める計算を繰り返したとき、最終的に1と
なる正整数nのことをいう。

上記の URL に掲載されているものは真偽を返すようになっていますが、ここでは真の場合にはその数値を返し、偽の場合には 0 を返すようなものを作ってみました。

#! /usr/local/bin/nawk -f
# happy_number.awk
# ハッピーナンバーを判定する
# usage: nawk -f happy_number.awk num

BEGIN {

    # See http://en.wikipedia.org/wiki/Happy_number
    if (__test__) {
        for (i = 1; i <= 500; i++) {
            if (is_happy_number(i)) {
                print i " is a happy number.";
            }
        }
        exit;
    }

    num = ARGV[1] ? ARGV[1] : 100;

    print is_happy_number(num);
}

# is_happy_number():    ハッピーナンバーかどうかを判定する
#   in:     数値 (num)
#   out:    ハッピーナンバーでなければ数値 0 を返す
#           ハッピーナンバーであれば数値 (num) をそのまま返す
function is_happy_number(num,
            init_num, num_num, arr_num, i, sum_num) {
    init_num = num;
    for (;;) {
        sum_num = 0;
        num_num = split(num, arr_num, "");
        for (i = 1; i <= num_num; i++) {
            sum_num += arr_num[i] ^ 2;
        }

        if (sum_num == 4) {
            return 0;
        } else if (sum_num == 1) {
            return init_num;
        }
        num = sum_num;
    }
}

さて、思いつくハッピーナンバーは 1 とか 100 とかです。

$ nawk -f happy_number.awk 1
1

$ nawk -f happy_number.awk 100
100

ちょうど Happy number - Wikipedia, the free encyclopedia に 500 までのハッピーナンバーが掲載されていますので、答え合わせをしてみましょう。

$ nawk -v __test__=1 -f happy_number.awk
1 is a happy number.
7 is a happy number.
10 is a happy number.
13 is a happy number.
19 is a happy number.
23 is a happy number.
28 is a happy number.
31 is a happy number.
32 is a happy number.
44 is a happy number.
49 is a happy number.
68 is a happy number.
70 is a happy number.
79 is a happy number.
82 is a happy number.
86 is a happy number.
91 is a happy number.
94 is a happy number.
97 is a happy number.
100 is a happy number.
103 is a happy number.
109 is a happy number.
129 is a happy number.
130 is a happy number.
133 is a happy number.
139 is a happy number.
167 is a happy number.
176 is a happy number.
188 is a happy number.
190 is a happy number.
192 is a happy number.
193 is a happy number.
203 is a happy number.
208 is a happy number.
219 is a happy number.
226 is a happy number.
230 is a happy number.
236 is a happy number.
239 is a happy number.
262 is a happy number.
263 is a happy number.
280 is a happy number.
291 is a happy number.
293 is a happy number.
301 is a happy number.
302 is a happy number.
310 is a happy number.
313 is a happy number.
319 is a happy number.
320 is a happy number.
326 is a happy number.
329 is a happy number.
331 is a happy number.
338 is a happy number.
356 is a happy number.
362 is a happy number.
365 is a happy number.
367 is a happy number.
368 is a happy number.
376 is a happy number.
379 is a happy number.
383 is a happy number.
386 is a happy number.
391 is a happy number.
392 is a happy number.
397 is a happy number.
404 is a happy number.
409 is a happy number.
440 is a happy number.
446 is a happy number.
464 is a happy number.
469 is a happy number.
478 is a happy number.
487 is a happy number.
490 is a happy number.
496 is a happy number.

問題なさそうです。

ところで、4 に収束した場合はどのような無限ループになるのでしょうか。 各位の 2 乗の和だけを表示すると以下のようになります。

sum = 4
sum = 16
sum = 37
sum = 58
sum = 89
sum = 145
sum = 42
sum = 20
sum = 4

このようにして無限ループになります。

追記 (2009-07-14)

Happy Number - Rosetta Code に無限ループを判定するように組まれたハッピーナンバーのコードがありますので、参考にしてみてください。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png