如何根据其主要因素生成数字,但未知指数？

Question

可能的重复:
第n个丑陋的数字
找到表达式的第K个最小数(2 ^ x)*(3 ^ 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)