如何根据质因数生成数字，但是指数未知？

Question

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

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

我们定义“丑数”为任何可以写成形式：2^x * 3^y * 5^z 的数字 n，其中 x、y 和 z 均为自然数。请找出第 1500 个丑数。

例如，前几个“丑数”为：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

我尝试使用暴力破解来解决这个问题，方法如下：

import itertools as it

def is_ugly(n):
    '''Return `True` if *n* is an ugly number.'''

    if n == 1:
        return True
    while not n % 2:
        n //= 2
    while not n % 3:
        n //= 3
    while not n % 5:
        n //= 5
    return n == 1

def nth_ugly(n):
    '''Return the nth ugly number.'''

    num = 0
    for i in it.count(1):
        if is_ugly(i):
            num += 1
            if num == n:
                return i

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

我知道丑数的质因子，但我想不出一种按正确顺序生成这些数字的方法。

我认为必须有一种方法来生成这些数字，而不必检查所有数字。问题在于，质因子的指数似乎分布得相当随机。

看看这个表格：

n   |number| x | y | z |
------------------------
1   |  1   | 0 | 0 | 0 |
------------------------
2   |  2   | 1 | 0 | 0 |
------------------------
3   |  3   | 0 | 1 | 0 |
------------------------
4   |  4   | 2 | 0 | 0 |
------------------------
5   |  5   | 0 | 0 | 1 |
------------------------
6   |  6   | 1 | 1 | 0 |
------------------------
7   |  8   | 3 | 0 | 0 |
------------------------
8   |  9   | 0 | 2 | 0 |
------------------------
9   |  10  | 1 | 0 | 1 |
------------------------
10  |  12  | 2 | 1 | 0 |
------------------------
11  |  15  | 0 | 1 | 1 |
------------------------
12  |  16  | 4 | 0 | 0 |
------------------------
13  |  18  | 1 | 2 | 0 |
------------------------
14  |  20  | 2 | 0 | 1 |
------------------------
15  |  24  | 3 | 1 | 0 |
------------------------

如您所见，x、y 和 z 值似乎没有遵循任何规律。

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

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

- Bakuriu

---

作业？面试？我曾经把这个当作一道作业，下面会发布解决方案。 - Mihai Maruseac

根据https://dev59.com/pWw05IYBdhLWcg3wfhyg的说法，“使用“循环迭代器”的替代版本”是一个非常漂亮的Python解决方案，适用于任何决定阅读哪个Python解决方案的人，在[此页面](http://rosettacode.org/wiki/Hamming_numbers#Alternate_version_using_.22Cyclic_Iterators.22)中找到。 - Xavier Combelle

这是几年前在参加乌迪内卓越学校入学考试时出现的一个问题。我正在准备进入那里，所以我正在尝试解决以前的测试。很抱歉有重复，即使编程语言不同...我只是没有尝试“丑陋的数字”，因为我认为这只是测试作者发明的一个随机名称。 - Bakuriu

虽然使用 O(n) 代码找到整个序列的答案是一个好方法，但是也有可能直接在 O(n^(2/3)) 的时间内计算出 Hamming 序列的第 n 个数，且系数非常小。这段 Haskell 代码 可以在 Ideone.com 上（案例＃8，“d”）在几百分之一秒内计算出第 1,000,000 个值。 - Will Ness

Answer 1

下面是一个完整的解决方案。它具有O(n)的时间复杂度，它会按顺序生成每个数字一次。

# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF

n = 15
bases = [2, 3, 5]

nums = [1] * n
candidates_indexes = [0 for _ in bases]
candidates = [base for base in bases]

for i in range(1, n):
    nextn = min(candidates)
    nums[i] = nextn

    for index, val in enumerate(candidates):
        if val == nextn:
            candidates_indexes[index] += 1
            candidates[index] = bases[index] * nums[candidates_indexes[index]]

print(nums)

- orlp

---

@Bakuriu: 而且它也可以适应不同的数字。 - orlp

Answer 2

这里是一种使用堆的解决方案。我们的思路是将指数与丑陋数乘积一起跟踪。在每次迭代中，算法执行多达三个find_min操作和三个insert操作，find_min可能是冗余的，因为您可以通过将任何指数加1来到达每个指数，并且有三个指数。我们进行了三次插入，因为我们将每个指数加1并将其插入堆中。因此，要找到第n个丑数，我们必须执行N个操作，这些操作是6*O(log n)，因此该算法具有O(n log n)的时间复杂度。堆本身由于每次迭代仅能增加常量数量，因此空间复杂度为O(n)。

>>> import heapq, itertools
>>> class UglyGen(object):
...     def __init__(self, x, y, z):
...         self.x, self.y, self.z = x, y, z
...         self.value = 2**self.x * 3**self.y * 5**self.z
...     def incr(self):
...         x, y, z = self.x, self.y, self.z
...         return (UglyGen(x+1, y, z),
...                 UglyGen(x, y+1, z),
...                 UglyGen(x, y, z+1))
...     def __lt__(self, other):
...         if not isinstance(other, UglyGen):
...             return NotImplemented
...         return self.value < other.value
... 
>>> def gen_ugly():
...     gens = [UglyGen(0, 0, 0)]
...     last = 0
...     while gens:
...         while gens[0].value == last:
...             heapq.heappop(gens)
...         top = heapq.heappop(gens)
...         succ_items = top.incr()
...         for succ in succ_items:
...             heapq.heappush(gens, succ)
...         last = top.value
...         yield last
... 
>>> def find_nth_ugly(n):
...     for n0, u in itertools.izip(xrange(n), gen_ugly()):
...         pass
...     return u
... 
>>> find_nth_ugly(15)
24

- SingleNegationElimination

---

实际上，堆的空间复杂度为O(n^(2/3))。这种解决方案的复杂度不仅次优，而且还会在请求的元素之后过度生成堆。 - Will Ness

Answer 3

使用列表（在以下代码中表示为n）来存储所有之前的丑数，下一个丑数是大于n[-1]的(n * 2、n * 3、n * 5)中的最小数：

n = [1]
while len(n) < 1500:
    n.append(min([next(x*s for x in n if x*s>n[-1]) for s in (2,3,5)]))    
print n[-1]

这是一个O(n^2)的解决方案，所以不要尝试大量数据。

- HYRY

Answer 4

我建议您逐步解决问题，并将所有找到的丑陋数字存储在列表中。

因此，在检查数字是否丑陋时，您只需要检查它是否是您的数字之一乘以2、3或5。

编辑：我刚试图这样实现。

ugly = [1]
candidate = 2
while len(ugly) < 1500:
    for u in ugly:
        if any([(u * x == candidate) for x in (2, 3 ,5)]):
            ugly.append(candidate)
            break
    candidate += 1

print ugly[-1]

但这种方法太幼稚了，会陷入无望的停滞。 :) 最好使用一些埃拉托斯特尼筛法之类的方法。

- Johannes Charra