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

Question

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

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

我们将每个数字n定义为“丑陋”，这些数字可以写成以下形式：2^x * 3^y * 5^z;，其中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 值似乎不遵循任何规则。

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

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

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)

Answer 2

这是使用堆的解决方案。我们的想法是，我们跟踪指数以及丑陋的产品。对于每次迭代，算法最多执行 3 个 find_min 操作和 3 个插入操作。 find_min 可能是多余的，因为您可以通过对任何指数加 1 来获得每个操作，并且有 3 个指数。我们执行三次插入，因为我们为每个指数加一并将其插入到堆中。为了找到第 n 个丑数，我们必须执行 N 个操作，即 6 * O(log n)，因此该算法的时间复杂度为 O(n log n)。堆本身因为每次迭代只能增长恒定量，所以是 SPACE(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

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

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 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]

但这种方法毫无希望地停滞不前。太天真了。 :) 而是使用某种埃拉托斯特尼筛法。