ハミングの問題

ハンミング数に挑戦して失敗した - みずぴー日記からですが、元は2^i * 3^j * 5^k なる整数 DouKaku? です。 これはハミングの問題として知られているようで、C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー) (単行本) に Hamming の問題として出ています。 ここでは、このアルゴリズムを用います。

#! /usr/bin/gawk -f
# hamming.awk
# Ref: 「C言語による最新アルゴリズム事典」(ISBN-10: 4874084141) P.361

BEGIN {
    j2 = j3 = j5 = 0;
    x2 = x3 = x5 = 1;

    for (i = 0; i < 100; i++) {
        min = x2;
        if (x3 < min) {
            min = x3;
        }
        if (x5 < min) {
            min = x5;
        }

        hamming[i] = min;

        while (x2 <= min) {
            x2 = 2 * hamming[j2++];
        }
        while (x3 <= min) {
            x3 = 3 * hamming[j3++];
        }
        while (x5 <= min) {
            x5 = 5 * hamming[j5++];
        }
    }

    for (i = 0; i < 100; i++) {
        print hamming[i];
    }
}

実行してみましょう。

$ gawk -f hamming.awk
1
2
3
4
5
6
8
9
10
12
<snip>

2^i * 3^j * 5^k なる整数 DouKaku? でも同様のアルゴリズムで解いている解答が多いようです。

最初、素因数分解を用いて解けると思ったのですが、専用のアルゴリズムの方がはるかに高速です。(そもそも 0, 1 は素数でないので素因数分解では解けません)