问题标签 [smooth-numbers]

我的一个朋友正在面试一份工作。其中一个面试问题让我思考，只是想要一些反馈。

有 2 个非负整数：i 和 j。给定以下等式，找到一个（最佳）解决方案来迭代 i 和 j，从而对输出进行排序。

所以前几轮看起来像这样：

尽我所能，我看不到模式。你的意见？

如何2^i * 5^j按递增顺序打印表格编号。

正则数是 60 次幂的整数。例如，60 ² = 3600 = 48 × 75，因此 48 和 75 都是 60 次幂的除数。因此，它们也是正则数。

这是向上取整到 2 的下一个幂的扩展。

我有一个整数值N，它可能包含大的素因数，我想将它四舍五入为仅由小素因数（2、3 和 5）组成的数字

例子：

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

找到满足此要求的最小数字的有效方法是什么？

涉及的值可能很大，所以我想避免从 1 开始枚举所有常规数字或维护所有可能值的数组。

我有一组素数，我必须只使用这些素数以递增的顺序生成整数。

例如，如果集合是p = {2, 5}，那么我的整数应该是 1, 2, 4, 5, 8, 10, 16, 20, 25, ...</p>

有没有有效的算法来解决这个问题？

我试图在haskell中生成汉明数，问题是我的输出列表中有重复的#，我无法弄清楚究竟是为什么。我应该只创建一个删除重复项功能还是我只是缺少一些简单的东西？

同样在汉明函数中，我想确保输入列表的大小正好是 3，如何找到列表的大小以便进行比较？

我一直在尝试在python中实现Dixon的分解方法，我有点困惑。我知道你需要给出一些界限B和一些数字N，并搜索它们之间的数字sqrtN，N其平方是B-smooth，这意味着它们的所有因子都在小于或等于 的素数集中B。我的问题是，给定N一定的大小，是什么决定B了算法会产生 的重要因素N？这是有关该算法的维基百科文章，如果有帮助，这是我的实现代码：

也许有人也可以帮我清理一下我的代码？这似乎非常低效。

所以问题是：

编写一个程序来查找第 n 个超级丑数。

超级丑数是正数，其所有素因数都在给定大小为 k 的素数列表中。例如，[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是给定素数 = [2, 7, 13, 19] 的前 12 个超丑数的序列大小为 4。

所以我的算法基本上使用它们遵循的模式找到所有可能的因素，将它们推送到一个数组，对该数组进行排序，然后返回数组中的第 n 个值。它可以准确地计算所有这些，但是对于高 nth 值来说太慢了。

我的问题是这样做的正确方法是什么，因为我确信必须有一个更直接的解决方案。我主要对找到它背后的理论以及是否有某种封闭的公式感到好奇。

考虑有限集 {2,3,5,...,n}。我对素数感兴趣，但这个问题可能适用于任何一组数字。我想按升序找到这些数字的所有可能乘积，特别是大于或等于某个数字 x。有谁知道一个很好的算法吗？

编辑澄清：

输入集中的每个因子都可以使用任意次数。如果输入为 {2,3,5,7}，则输出为 {2,3,4,5,6,7,8,9,10,12,14,15,16,18,...} . 一旦产生大于或等于某个数字 x 的结果，该算法就可以停止。

这是一种基于从序列中的一个数字到下一个数字的间隔来生成汉明数序列（又名常规数字，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 分钟。我用一个非常简单的算法编写了代码，但我很好奇（希望）找到另一种方法。我试图用对数在数学上解决这个问题，但最终无处可去。当涉及到大量输入时，甚至可能有一种有效的方法吗？