汉明数使用自定义函数而不是素数。

Question

汉明问题是一个著名的问题，基本上生成所有只有{2、3、5}作为质因子的整数。（我认为它可以扩展到任何一组质因子）

要找到第n个汉明数，Dijkstra提出了一个巧妙的O(N)构建算法，其伪代码如下：

List<int> H
int i=0,j=0,k=0, n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
   int next = min(2*H[i], 3*H[j], 5*H[k])
   H.add(next)
   if(next == 2*H[i]) ++i
   if(next == 3*H[j]) ++j
   if(next == 5*H[k]) ++k

output(H[10])

这个解决方案的关键在于，如果H是汉明数，那么2H、3H、5H也是汉明数。

---

我遇到了一个问题，我感觉它有点像汉明问题，但不是用一组质因数构建数字，而是像下面这样重新表述问题陈述：

1在结果集中。 如果H在结果集中，则2H+1和3H+1也在结果集中。 找到结果集中的第n个数字

然后我想知道同样的构造算法是否适用于此问题，结果它确实有效！（我甚至不知道为什么它有效）

Def f(x) 2x+1
Def g(x) 3x+1

List<int> H
int i=0,j=0,n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
   int next = min(f(H[i]), g(H[j]))
   H.add(next)
   if(next == f(H[i])) ++i
   if(next == g(H[j])) ++j

output(H[10])

---

那么我想知道：

这个构造算法是否适用于生成数字问题，给定一个规则，如“如果x在结果中，则所有f(x), g(x), p(x), q(x)...也在结果中”，前提是这些函数将给出一个>=x的结果？

- shole

---

函数需要单调递增或单调递减：如果f(2) > f(3)，那么生成的数字就不会按照递增顺序排序。如果函数是单调的，我认为可以通过归纳证明所有数字都按正确的顺序生成。在生成到N的所有数字后，其中一个指针必须准备好生成序列中的下一个数字。 - mcdowella

@mcdowella 谢谢，我认为你关于单调部分的观点是正确的。至于证明，我正在尝试做这件事，但对我来说并不太容易... - shole

单调性（或其他强假设）是必不可少的。如果 f，g 等可计算且具有可证明无界范围但没有其他假设，则通过应用这些函数从 {1} 生成的集合是递归可枚举的，但通常不是递归的。在非递归情况下，由于停机问题是不可判定的，因此没有算法可能起作用。实际上，没有通用算法可以确定 2 是否在该集合中。 - John Coleman

Answer 1

一个充分的条件是所有从整数到整数的函数f_i必须是单调递增的，并且对于所有的i和n都有n < f_i(n)。例如，展示整数规则类似所需的一对函数是(n+0.5，(n + floor(n+1))/2)。这将导致序列1、3/2、7/4、15/8，你永远不会得到2。函数(2^n，20 - 5n + n^2)以1、2、4、16、14的顺序出现，显然不是有序的。因此需要非递减。函数(n-3)给出了序列(1,-2,-5，...)，显示了n < f_i(n)的重要性。那么为什么这个算法有效呢？首先，很明显，该算法输出的任何内容都在集合中。

假设满足所有三个条件，现在我们需要通过归纳证明，如果你属于这个序列，我们会在到达你之前开始寻找你，并且必须在经过你时找到你。（由于该序列是递增的整数集合，我们保证会经过你。）证明有些复杂，但很直接。

- btilly