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

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])

然后我想知道：

这个构造算法是否适用于生成数字的问题，给定像 "If x is in the result, then all f(x), g(x), p(x), q(x)... are also in the result" 这样的规则，前提是这些函数将给出结果 >= x?

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) 的重要性。

那么为什么这样做有效？

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

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

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

Hamming number using custom functions instead of prime

algorithm

math

hamming-numbers