按间隔排列的汉明数

这是生成汉明数序列（又名常规数字 https://en.wikipedia.org/wiki/Regular_number, 5-平滑数 https://en.wikipedia.org/wiki/Smooth_number）基于序列中一个数字到下一个数字的间隔。以下是所述间隔的示例图：

因此，将一个数字与下一个数字分开的离散间隔数量相对有限，并且随着 H 的增加，间隔会变小。人们经常注意到，汉明数随着大小的增加而变得越来越稀疏，这在绝对意义上是如此，但在另一种意义上（按比例）它们变得更接近。

基本上，随着 H 的增加，2^i*3^j*5^k（其中 i、j、k 是正整数或负整数）有更大的机会产生接近 1.0 的分数。

事实证明，只有 119 个间隔（i,j,k 三元组）的表涵盖了最多大约 10^10000 的汉明数。这大约是前 1.59 万亿个汉明数。这样一个表（C头文件），按照区间大小从小到大排序，就是here https://github.com/jmknapp/hammingnumbers/blob/master/hamseq.h。给定一个汉明数，要找到下一个，所需要做的就是找到表中的第一个条目，其中乘法（相应指数的加法）将产生 i、j 和 k 的正幂结果。

例如，第一百万个汉明数是 2^55*3^47*5^64，大约是 5.1931278e83。之后的下一个汉明数是 2^38*3^109*5^29 或大约 5.1938179e83。第一个合适的表条目是：

{-17,62,-35}, // 1.000132901540844

因此，虽然这些数字之间的间隔约为 7e79，但它们的比率为 1.000132901540844。要找到下一个数字，在最坏的情况下只需尝试最多 119 个条目，仅涉及加法和比较（无乘法）。此外，每个条目只有 3 个短整数的表需要不到 1kb 的内存。该算法基本上在内存上是 O(1)，在时间上是 O(n)，其中 n 是序列的长度。

加快速度的一种方法是，不要每次都从第 0 个索引开始搜索表，而是将表条目列表限制为仅搜索那些根据经验已知在给定范围内接替给定条目的条目（n

{11,{47,55,58,65,66,68,70,72,73,75,76}},

因此，根据经验发现，该特定索引后面仅跟随列出的 11 个不同索引，因此这些是唯一搜索的索引。

这样做可以将算法速度提高 4 倍左右，已实现here https://github.com/jmknapp/hammingnumbers/blob/master/hamseq.c（C 代码）以及头文件 https://github.com/jmknapp/hammingnumbers/blob/master/hamseq.h多于。下面是 i7-2600 3.4GHz 机器上的执行时间图：

我相信这与最先进的技术相比是有利的——是这样吗？

The Hamming problem is sometimes reduced to just finding the nth Hamming number without generating all the intermediate values. Adapting the above technique to a well-known scheme of just enumerating the Hamming numbers in a band around the desired range gives this plot of execution time:

因此，只需不到 2 秒即可找到第 1.59 万亿个汉明数。其 C 代码是here https://github.com/jmknapp/hammingnumbers/blob/master/hamnum.c。至少在给定的范围内，这是否也能与现有技术相媲美？

编辑：n 的边界（1.59e12，汉明数高达约 10^10000）是根据特定机器选择的，其中希望 i、j、k 是短整数，并且对执行速度也有合理的期望。可以生成更大的表，例如一个包含 200 个条目的表将允许 n 高达约 1e18（汉明数高达约 10^85000）。

另一个问题是如何进一步加快速度。一个潜在的领域：事实证明，某些表条目比其他表条目更频繁地被命中，并且它们有相应更大的后继者列表需要检查。例如，当生成前 1.59e12 个数字时，该条目被 46% 的迭代命中：

{-7470,2791,1312}

它有 23 种可能的不同后继者。也许基于其他参数（例如，先前遍历的条目的历史记录）缩小范围的某种方法会有所帮助，尽管没有太多空间用于昂贵的操作。

EDIT #2:

有关生成表格的一些信息，基本上有六类分数 2^i*3^j*5^k，其中 i,j,k 是正整数或负整数：分子中只有 2,3 或 5 的分数，以及分母只有 2、3 或 5 的分数。例如，对于分子中只有 2 的类：

f = 2^i/(3^j*5^k)，i > 0 且 j,k >= 0

计算此类分数的间隔的 C 程序是here https://github.com/jmknapp/hammingnumbers/blob/master/n2.c。对于大约 10^10000 的汉明数，它会在几秒钟内运行。它可能会变得更有效率。

对其他 5 类分数重复类似的过程会产生 6 个列表。按间隔大小对它们进行排序并删除重复项即可生成完整的表格。

The triples enumeration is ~ n^2/3 but the sorting of the band is ~ n^2/3 log (n^2/3) i.e. ~ n^2/3 log n. This obviously doesn't change even with ~ n^1/3 band space scheme.

Indeed the empirical complexities are seen in practice as ~ n^0.7.

I am yet to understand your algorithm fully, but the evidence you presented https://chat.stackoverflow.com/transcript/message/39753573#39753573 strongly suggests the pure ~ n^2/3 operation, which would constitute a clear and significant improvement over the previous state of the art, absolutely.

在我看来，如果需要生成整个序列才能找到算法所基于的“间隔”（比率），情况就不是这样了。但由于您是独立生成它们的，正如您后来的编辑似乎所暗示的那样，这根本不是障碍。

更正：如果我们只对n序列中的第一个成员，则不需要对带进行完整排序；O(n) 选择第 k 个最大的算法确实存在。