ハッピーナンバーの判定
C/C++の宿題を片付けます@wiki - C++の宿題/HappyNumber と HappyNumberの判定 - みずぴー日記 にインスパイヤされて、awk でも行ってみました。
なお、ハッピーナンバーとは以下のようなものだそうで、1 か 4 に収束し、4 の場合には無限ループになるというもののようです。 この性質を使うことにします。
HappyNumberとは、正整数ｎの各桁の数を２乗し、その合計を求め、その合計の 各桁の数を2乗し、またその合計を求める計算を繰り返したとき、最終的に１と なる正整数ｎのことをいう。
上記の 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 に無限ループを判定するように組まれたハッピーナンバーのコードがありますので、参考にしてみてください。
