如何根據主要因素生成數字，但指數未知？

Question

可能重複：
nth ugly number
Find the Kth least number for expression (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) 

Answer 2

我建議你逐步解決這個問題，並將你在列表中找到的所有難看的數字都存儲起來。

當檢查醜陋一個號碼，然後，你只需要檢查它是否是你的次數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] 

但這種方法停滯不前。太天真了。 :)使用某種Eratosthenes篩。

Answer 3

使用列表（以下代碼中的n）來存儲所有以前的醜陋數字，下一個醜陋數字是大於（n * 2，n * 3，n * 5） -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

這是一個使用堆的解決方案。我們的想法是，我們跟蹤丑角產品的指數。對於每次迭代，該算法最多執行3次find_min操作和3次插入操作。find_mins可能是多餘的，因爲您可以通過將任意指數加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