问题标签 [hamming-numbers]

这是一种基于从序列中的一个数字到下一个数字的间隔来生成汉明数序列（又名常规数字，5-平滑数字）的稍微不同的方法。这是所述间隔的示例图：

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

基本上，随着 H 的上升，2^i*3^j*5^k 的机会更大，其中 i,j,k 是正整数或负整数，导致小数接近 1.0。

事实证明，只有 119 个区间（i、j、k 三元组）的表涵盖了高达约 10^10000 的汉明数。这大约是前 1.59 万亿个海明数。这样一个表（C头文件），按区间大小从小到大排序，就在这里。给定一个汉明数，要找到下一个，只需要找到表中的第一个条目，其中乘法（各个指数相加）将产生对 i、j 和 k 具有正幂的结果。

例如，第 100 万个海明数是 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 < 1.59 e12)。这些列表在 succtab[] 结构的上述头文件中给出，例如：

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

因此，凭经验发现该特定索引后仅跟随列出的 11 个不同索引，因此仅搜索这些索引。

这样做可以将算法速度提高 4 倍左右，在此处实现（C 代码）以及上面的头文件。这是 i7-2600 3.4GHz 机器上的执行时间图：

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

汉明问题有时会简化为仅找到第 n 个汉明数而不生成所有中间值。将上述技术应用于一个众所周知的方案，即仅在所需范围附近的一个频带中枚举汉明数，就可以得到这个执行时间图：

因此，找到第 1.59 万亿个海明数只需要不到 2 秒的时间。C 代码在这里。至少在给定的范围内，这是否也与最先进的技术相媲美？

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

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

{-7470,2791,1312}

它有 23 个可能的不同继任者。也许某种基于其他参数（例如，以前遍历的条目的历史）缩小范围的方法会有所帮助，尽管对于昂贵的操作来说空间不大。

编辑＃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

计算这类分数的区间的 AC 程序在这里。对于高达约 10^10000 的汉明数，它会在几秒钟内运行。它可能会变得更有效率。

对其他 5 类分数重复类似的过程会产生六个列表。按间隔大小将它们全部排序并删除重复项会产生完整的表格。

维瓦尔第数是只能被 2、3 和 5 分解的数（V = 2^a * 3^b * 5^c, a, b, c = 0,1,...也称为汉明数）。任务是找到第 N 个维瓦尔第数。

该算法对于小输入来说还不错，但 N 的范围从 0 到 9999。在 2000 年花了 2 分钟。我用一个非常简单的算法编写了代码，但我很好奇（希望）找到另一种方法。我试图用对数在数学上解决这个问题，但最终无处可去。当涉及到大量输入时，甚至可能有一种有效的方法吗？

我想在 Haskell 中编写一个汉明函数，将列表作为输入。我已经有了这个：

那很简单。但现在我想要像“hamming [4,6,7,9]”这样的输入。实际输入是 1，但现在输入应该是一个列表，并且列表中的每个数字都在汉明列表中。当然 2x 3x 和 5x 在列表中。

我写了类似的东西

"hamming (x:xs) = x : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))"只是为了测试一个列表，但它不起作用。

我正在尝试生成可以用表格表示的所有倍数的列表，其中 a、b 和 c 是整数。我尝试了以下，

但它只列出了 5 的幂，从不继续 2 或 3。

编辑：抱歉，我似乎没有充分澄清这个问题。我想要的是一个有序的无限列表，虽然我可以对一个有限列表进行排序，但我觉得好像有一个更有效的解决方案。

我正在尝试学习 Haskell 和理解列表，但找不到解决方案：

经过我的试验，结果是这样的

因为在列表推导中，x取值1，然后y反复更改值。

但我的目标是完成不同的任务，以便获得以下结果：

我的意思是我想要混合组合而不是分开，因为我有一个严重的问题来获得合适的结果。

我将举一个更具体的例子。

我想要一个包含这种形式的所有数字的列表：

x并且y必须取所有值>= 0。

我的方法如下：

但这样我只取 3 的幂，因为x一直是 0。

我试过这个

以便合并不同的值，但再次合并值 6,12 等。丢失 - 结果是这样的：

我基本上被困在 SICP 的练习 3.56 上。问题是这样的：

练习 3.56。一个著名的问题，首先由 R. Hamming 提出，以不重复的升序枚举所有除 2、3 或 5 之外没有素因数的正整数。一个明显的方法是简单地测试每个整数反过来看它是否具有除 2、3 和 5 之外的任何因子。但这非常低效，因为随着整数变大，符合要求的整数越来越少。作为替代方案，让我们调用所需的数字流 S 并注意以下有关它的事实。

• S 以 1 开头。
  • (scale-stream S 2) 的元素也是 S 的元素。
  • (scale-stream S 3) 和 (scale-stream 5 S) 也是如此。
  • 这些都是S的元素。

现在我们要做的就是结合这些来源的元素。为此，我们定义了一个过程合并，将两个有序流合并为一个有序结果流，消除重复：

然后可以用merge构造所需的流，如下：

(define S (cons-stream 1 (merge <??> <??>)))

在上面标记的地方填写缺少的表达式。

在这个特定问题之前，我已经能够使用信号处理框图来可视化和理解这些隐式流定义，并将原始流反馈给过程。

但是我基本上已经遇到了这个特殊问题，我已经查找了解决方案，但我发现无法想象解决方案在我的头脑/论文中是如何工作的。

有没有什么技巧可以帮助我们理解这些问题并提出解决方案？

这是有效的解决方案：

提前致谢。

显示前N个自然数，除数只有 2、3 和 7。我写了类似的东西。我是 Lisp 的初学者。谢谢！

嗨，我需要打印汉明数，但我只能使用 if 循环来完成。如何使用 for 或 while 循环来做到这一点？

目标是确定一个数字是否是汉明数？！众所周知，汉明数是一个仅包含 2、3 和 5 作为因数的数。这意味着一个数字不能包含任何大于 5 的素数！所以我创建了一个函数 isPrimeNumber 来确定一个数字是否是素数，然后我创建了一个函数来确定一个数字是否包含因子 2、3 和 5？！

想结合这两个函数来确定输入的数字是否是汉明数？！