免責事項：それについて多くの質問がありますが、一定のメモリを必要とするものは見つかりませんでした。
ハミング数とは、2^i*3^j*5^ki、j、k を自然数とする数です。
O(N)時間とO(1)(定数)メモリでN番目のハミング数を生成する可能性はありますか? 生成とは、正確には生成器を意味します。つまり、結果を出力することしかできず、以前に生成された数値を読み取ることはできません (その場合、メモリは一定ではありません)。ただし、一定数のそれらを保存できます。
たとえば、優先キューに基づいて、定数メモリを使用した最適なアルゴリズムのみが O(N log N) よりも優れていないことがわかります。しかし、O(N) 時間でアルゴリズムを構築することは不可能であるという数学的な証明はありますか?