come generare numeri dati i loro fattori primi, ma con esponenti sconosciuti?

Question

Possibili duplicati:
nth ugly number
Find the Kth least number for expression (2^x)*(3^y)*(5^z)

Mi chiedo come risolvere questo problema in modo veloce ed elegante:

Definiamo "brutto" ogni numero n che può essere scritto nel formato: 2^x * 3^y * 5^z ;, dove x, y e z sono numeri naturali. Trova il 1500esimo numero brutto.

E.g. i primi numeri "brutto" sono:

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

ho cercato di risolvere questo problema usando la forza bruta, in questo modo:

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 

ma ci vuole un bel po 'di tempo, e io "Mi piacerebbe trovare una soluzione più veloce e migliore.

Conosco i fattori primi di numeri brutti, ma non riesco a pensare a un modo per generare questi numeri seguendo l'ordine corretto.

Penso che ci sia un modo per generare questi numeri senza dover controllare tutti i numeri. Il problema è che sembra che gli esponenti dei fattori primi siano distribuiti in modo piuttosto casuale.

Guardate questa tabella:

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

Come potete vedere i valori x, yez non sembrano seguire alcuna regola.

Qualcuno di voi può trovare una soluzione a questo problema?

Sto pensando di provare a dividere il problema in diverse parti. Poiché il problema è determinato dalla casualità degli esponenti, potrei provare a generare autonomamente le potenze di 2s, 3s, 5s e quindi i numeri della forma 2^x * 3^y, 2^x * 5^z ecc. E finalmente li metto insieme, ma non so se questo risolverà il mio problema.

Answer 1

Ecco una soluzione completa. O (n) complessità, genera ogni numero una volta e nell'ordine.

# 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

Ti suggerisco di risolverlo in modo incrementale e di memorizzare tutti i brutti numeri che trovi in ​​una lista.

Quando si controlla un numero per la bruttezza, allora, è sufficiente verificare se si tratta di uno dei tuoi momenti numero 2, 3 o 5.

EDIT: Ho appena cercato di attuare tale come questo

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] 

ma questo approccio ristagna irrimediabilmente. Troppo ingenuo. :) Utilizzare piuttosto una specie di setaccio di Eratostene.

Answer 3

utilizzare una lista (n nel seguente codice) per memorizzare tutti i numeri prev brutti, il prossimo numero brutto è il numero minimo di (n * 2, n * 3, n * 5) che è più grande di 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] 

È una soluzione O (n^2), quindi non provare un numero elevato.

Answer 4

Ecco una soluzione che utilizza un heap. L'idea è di tenere traccia degli esponenti insieme al brutto prodotto. Per ogni iterazione, l'algoritmo esegue fino a 3 operazioni find_min e 3 operazioni di inserimento, i find_mins possono essere ridondanti perché è possibile arrivare a ciascuno aggiungendo uno a qualsiasi esponente e ci sono tre esponenti. Facciamo un inserimento tre volte perché ne aggiungiamo uno a ciascun esponente e lo inseriamo nell'heap. Per trovare l'ennesimo numero brutto, dobbiamo quindi eseguire N operazioni che sono 6 * O (log n), quindi l'algoritmo ha una complessità temporale di O (n log n). Lo stesso heap, dal momento che può crescere solo di una quantità costante per ogni iterazione, è 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