这里有很多好的答案，但我有些难以理解，特别是包括被接受的答案在内的所有答案如何保持
Dijkstra原始论文中的公理2：
公理2. 如果x在序列中，则2 * x，3 * x和5 * x也在序列中。
经过一些白板演示，变得清晰的是，公理2在算法的每次迭代中都不是一个不变量，而实际上是算法本身的目标。在每次迭代中，我们尝试恢复公理2中的条件。如果last是结果序列S中的最后一个值，则公理2可以简单地重新表述为：
对于S中的某个x，S中的下一个值是2x、3x和5x的最小值，大于last。让我们称之为公理2'。
因此，如果我们可以找到x，我们可以在常数时间内计算出2x、3x和5x的最小值，并将其添加到S中。
但是，我们如何找到x呢？一种方法是我们不寻找；相反，每当我们向S中添加一个新元素e时，我们计算2e、3e和5e，并将它们添加到最小优先级队列中。由于此操作保证e在S中，因此仅提取PQ的顶部元素就满足公理2'。
这种方法有效，但问题是我们生成了一堆可能不会使用的数字。请参见
此答案以获取示例；如果用户想要S中的第5个元素（5），那么此时的PQ保存着6 6 8 9 10 10 12 15 15 20 25。我们能不能不浪费这个空间呢？
原来我们可以做得更好。我们不必存储所有这些数字，而只需为每个倍数维护三个计数器，即
2i、
3j和
5k。这些是下一个在
S中的数字的候选项。当我们选择其中一个时，我们只增加相应的计数器，而不增加其他两个计数器。通过这样做，我们不会急于生成所有的倍数，从而解决了第一种方法中的空间问题。
让我们看一个
n = 8的演示，即数字
9。我们从
1开始，正如Dijkstra论文中的公理1所述。
+---------+---+---+---+----+----+----+-------------------+
| # | i | j | k | 2i | 3j | 5k | S |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2 | 3 | 5 | {1} |
+---------+---+---+---+----+----+----+-------------------+
| 1 | 1 | 1 | 1 | 2 | 3 | 5 | {1,2} |
+---------+---+---+---+----+----+----+-------------------+
| 2 | 2 | 1 | 1 | 4 | 3 | 5 | {1,2,3} |
+---------+---+---+---+----+----+----+-------------------+
| 3 | 2 | 2 | 1 | 4 | 6 | 5 | {1,2,3,4} |
+---------+---+---+---+----+----+----+-------------------+
| 4 | 3 | 2 | 1 | 6 | 6 | 5 | {1,2,3,4,5} |
+---------+---+---+---+----+----+----+-------------------+
| 5 | 3 | 2 | 2 | 6 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 6 | 4 | 2 | 2 | 8 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 7 | 4 | 3 | 2 | 8 | 9 | 10 | {1,2,3,4,5,6,8} |
+---------+---+---+---+----+----+----+-------------------+
| 8 | 5 | 3 | 2 | 10 | 9 | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+
请注意，第6次迭代时
S没有增长，因为最小的候选项
6已经在之前添加过了。为了避免记住所有先前元素的问题，我们修改算法，在相应倍数等于最小候选项时递增所有计数器。这使我们得到以下Scala实现。
def hamming(n: Int): Seq[BigInt] = {
@tailrec
def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
val leq = factor * xs(x) <= xs.last
if (leq) next(x + 1, factor, xs)
else x
}
@tailrec
def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
if (xs.size < n) {
val a = next(i, 2, xs)
val b = next(j, 3, xs)
val c = next(k, 5, xs)
val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min
val x = a + (if (2 * xs(a) == m) 1 else 0)
val y = b + (if (3 * xs(b) == m) 1 else 0)
val z = c + (if (5 * xs(c) == m) 1 else 0)
loop(x, y, z, xs :+ m)
} else xs
}
loop(0, 0, 0, IndexedSeq(BigInt(1)))
}
