algorithm - 使用自定义函数代替素数的汉明数

Question

Hamming Problem是一个著名的问题，它基本上生成所有质因数仅为 {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也是一个海明数

---

我遇到了一个 problem ，我觉得它有点像汉明问题，但它不是使用一组质因数构造数字，相反，如果我重新定相问题陈述，它就像下面这样:

1 is in the result set. If H is in result set, then 2H+1 and 3H+1 is also in the result set. Find the n-th number in the result set

然后我想知道相同的构造算法是否适用于这个问题，事实证明确实如此! (我什至不知道它为什么有效)

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?

Answer 1

充分条件是所有函数f_i从整数到整数必须是单调递增的并且有n < f_i(n)对于所有 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) 的重要性.

那么为什么这样做有效呢？

首先很明显，这个算法输出的任何东西都在集合中。

反过来，假设满足所有三个条件。然后我们必须通过归纳法证明，如果你属于这个序列，我们会在到达那里之前开始寻找你，然后当我们经过你时必须产生它。 (序列是一组递增的整数这一事实保证我们通过了你。)证明有点困惑，但很简单。