问题标签 [hamming-numbers]

只有质因数为 2、3 或 5 的数称为丑数。

例子：

1 可以认为是 2^0。

我正在努力寻找第 n^个丑数。n请注意，随着变大，这些数字的分布非常稀疏。

我写了一个简单的程序来计算给定的数字是否丑陋。因为n > 500- 它变得超级慢。我尝试使用记忆 - 观察：ugly_number * 2，，都是丑陋的ugly_number * 3。ugly_number * 5即使这样它也很慢。我尝试使用 log 的一些属性——因为这将把这个问题从乘法减少到加法——但是，还没有多少运气。想把这个分享给大家。有什么有趣的想法吗？

使用类似于埃拉托色尼筛法的概念（感谢 Anon）

i是第 n^个丑数。

即使这样也很慢。我试图找到第 1500^个丑陋的数字。

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

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

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

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

在表达式中

2 ^x * 3 ^y * 5 ^z

,x和可以取非y负z整数值 (>=0)。

所以该函数会生成一系列数字1,2,3,4,5,6,8,9,10,12,15,16....

• 我有一个蛮力解决方案。
• 我基本上会在从 1​​ 开始的循环中进行迭代，并且在每次迭代中，我会发现当前的数字因子是否仅来自 2,3 或 5 的集合。

我想要的是一个优雅的算法。

这是一道面试题。

可能的重复：
第 n 个丑数
找到表达式 (2^x)*(3^y)*(5^z) 的第 K 个最小数

我想知道如何以快速而优雅的方式解决这个问题：

我们定义每个可以写成以下形式的数字n的“丑陋” ：2^x * 3^y * 5^z;，其中 x,y 和 z 是自然数。找到第 1500 个丑数。

例如，第一个“丑陋”的数字是：

我试图通过这种方式使用蛮力解决这个问题：

但这需要相当多的时间，我想找到一个更快更好的解决方案。

我知道丑数的主要因素，但我想不出按照正确顺序生成这些数字的方法。

我认为必须有一种方法可以生成这些数字，而无需检查所有数字。问题是，主要因子的指数似乎是随机分布的。

看这张表：

如您所见，x、y 和 z 值似乎不遵循任何规则。

你们中有人能找到解决这个问题的方法吗？

我正在考虑尝试将问题划分为不同的部分。由于问题是由指数的随机性决定的，我可以尝试独立生成 2s、3s、5s 的幂，然后生成 2^x*3^y、2^x*5^z 等形式的数字。最后把它们放在一起，但我不知道这是否能解决我的问题。

正则数是 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，如何找到列表的大小以便进行比较？

这是我的一门课程作业中的编程问题。我已经有几年没有编程了，而且我一开始也不是很好。我目前正在阅读教程以恢复速度，但这需要一些时间。如果你们能帮我解决这个问题，我将不胜感激。

约束：

这个序列的每一项都是一个形式为 的正整数，对于所有具有 2^i*3^j*5^k的非负整数i, j, and ki + j + k >= 1.

不能使用数组。解决这个问题的算法必须涉及列表的重复创建和合并。具体来说5 lists; a final list, temp list, and three term lists。

“最终列表通过与当前临时列表合并而增长。临时列表又被三个术语列表的合并所取代。新术语列表是通过将新临时列表乘以2, 3, and 5 respectively“

所需的顺序如下：2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, . . .

(this is exciting!) I know, the subject matter is well known. The state of the art (in Haskell as well as other languages) for efficient generation of unbounded increasing sequence of Hamming numbers, without duplicates and without omissions, has long been the following (AFAIK - and btw it is equivalent to the original Edsger Dijkstra's code too):

The question I'm asking is, can you find the way to make it more efficient in any significant measure? Is it still the state of the art or is it in fact possible to improve this to run twice faster and with better empirical orders of growth to boot?

If your answer is yes, please show the code and discuss its speed and empirical orders of growth in comparison to the above (it runs at about ~ n^1.05 .. n^1.10 for first few hundreds of thousands of numbers produced). Also, if it exists, can this efficient algorithm be extended to producing a sequence of smooth numbers with any given set of primes?

我正在解决一个问题，该问题要求使用素数 2、3 和 5 生成一个序列，然后在序列中显示第 n 个数字。所以，如果我让程序显示第 1000 个数字，它应该显示它。

我不能使用数组或类似的东西，只能使用基本的决策和循环。

我开始研究它并碰壁......这就是我得到的：

不幸的是，该代码没有执行所需的操作。它显示诸如 14 之类的数字，其中包括一个素数 7.... 这些数字只能除以 3 个指定的素数 (2,3,5)。

我发现了一些我试图理解的信息，到目前为止还不确定如何实现它......也许使用了很多 for() 循环？所以，看来我必须使用 2^n * 3^m * 5^k 的概念，其中 n+m+k>0。

我想我必须通过一个测试来运行一个数字，它首先检查它是否可以被 2^1 * 3^0 * 5^0 完全整除，然后是 2^0 * 3^1 * 5^0，然后是 2^ 0 * 3^0 * 5^1，等等......只是不知道从哪里开始。