0653: ハミング数のマージ¶
問題¶
素因数が 2, 3, 5 のみである正の整数をハミング数（正則数）と呼びます。
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 と続き、7 や 14 のように他の素因数を含む数は現れません。
ハミング数を昇順に、重複なく、無限に生成するジェネレータ関数 hamming() を実装してください。
ハミング数は \(2^a 3^b 5^c\) の形の数ですが、指数の組 \((a, b, c)\) を単純な多重ループで列挙しても値の昇順にはならない点が本問の中心です。 この列を昇順に生成する課題は、Dijkstra が『A Discipline of Programming』で扱った古典問題として知られます。
制約¶
- 最初の値は 1 で、以後、昇順かつ重複なしで生成します。
- 上限を仮定してはいけません。値は多倍長整数のまま扱い、浮動小数点数（対数による大小比較など）を使ってはいけません（丸め誤差のため大きな値で順序を誤ります）。
- 自然数を 1 から順に調べてハミング数かどうか判定する方式は禁止します。\(N\) 以下のハミング数は \(O(\log^3 N)\) 個しかないため、この方式では \(n\) 番目を得るのに \(n\) に対して指数的な時間がかかります。
例¶
>>> from itertools import islice
>>> list(islice(hamming(), 15))
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
>>> next(islice(hamming(), 999, None)) # 1000番目のハミング数
51200000
発展¶
- 任意の有限素数集合に一般化した
smooth(primes)（いわゆる \(k\)-smooth 数の列挙）を実装してください。 hamming()の出力自身を 2 倍、3 倍、5 倍した3本のストリームとみなし、それらを重複を除きながらマージする自己参照的な実装に書き直してください（itertools.teeが使えます）。\(n\) 番目までの生成で内部に保持される要素数を、元の実装と比較してください。
参考¶
- 『Python Distilled』第6章「ジェネレータとyield文」
- 『Python Distilled』第6章「ジェネレータの実例」
- Regular number - Wikipedia