这里有很多好的答案，但我无法理解这些答案，特别是这些答案中的任何一个，包括已接受的答案，如何维护Dijkstra 原始论文中的公理 2 ：
公理 2。如果 x 在序列中，则 2 * x、3 * x 和 5 * x 也是。
在一些白板之后，很明显公理 2在算法的每次迭代中都不是不变量，而是算法本身的目标。在每次迭代中，我们尝试恢复公理 2 中的条件。如果last是结果序列中的最后一个值，则S公理 2 可以简单地改写为：
对于某些xin S， in 的下一个值是、 和S的最小值2x，
即大于。我们称此公理 2'。3x5xlast
因此，如果我们能找到，我们可以在恒定时间内计算、 和x的最小值2x，并将其添加到。3x5xS
但是我们怎么找到x呢？一种方法是，我们不这样做；相反，每当我们向 中添加新元素e时S，我们都会计算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} |
+---------+---+---+---+----+----+----+-------------------+
请注意，S在第 6 次迭代中它没有增长，因为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)))
}