如何在未知指数的情况下生成给定素因数的数字？

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 等形式的数字。最后把它们组合在一起，但我不知道这样是否能解决我的问题。

Answer 1

用一个列表（下面代码中的n）来存储所有之前的丑数，接下来的丑数是比列表中最后一个数大且最小的（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)，所以不要尝试处理很大的数字。

Answer 2

这里有一个使用堆的解决方案。这个方法的核心思想是我们同时记录指数和丑数的乘积。在每次循环中，算法最多会进行3次查找最小值的操作和3次插入的操作。查找最小值的操作可能会有点多余，因为你可以通过给任何一个指数加一来找到每个值，而我们有三个指数。我们进行三次插入是因为我们给每个指数加一，然后把这些值插入到堆里。为了找到第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

Answer 3

这里有一个完整的解决方案。它的复杂度是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)