cómo generar números dados sus factores primos, pero con exponentes desconocidos?

Question

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

Me pregunto cómo resolver este problema de una manera rápida y elegante:

Definimos "feo" cada número n que se puede escribir en la forma: 2^x * 3^y * 5^z ;, donde x, y y z son números naturales. Encuentra el número feo número 1500.

E.g. los primeros números "feos" son:

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

He tratado de resolver este problema usando la fuerza bruta, de esta manera:

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 

pero se necesita mucho tiempo, y yo Me gustaría encontrar una solución más rápida y mejor.

Conozco los factores primos de los números feos, pero no se me ocurre una manera de generar estos números siguiendo el orden correcto.

Creo que debe haber una manera de generar estos números sin tener que verificar todos los números. El problema es que parece que los exponentes de los factores primos se distribuyen de forma bastante aleatoria.

mirada a esta tabla:

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

Como se puede ver no parecen x, y, z los valores que seguir ninguna regla.

¿Alguien puede encontrar alguna solución a este problema?

Estoy pensando en tratar de dividir el problema en diferentes partes. Dado que el problema está determinado por la aleatoriedad de los exponentes, podría intentar generar independientemente los poderes de 2s, 3s, 5s y luego los números de la forma 2^x * 3^y, 2^x * 5^z, etc. Y finalmente ponerlos juntos, pero no sé si esto resolverá mi problema.

Answer 1

Aquí hay una solución completa. O (n) complejidad, genera cada número una vez y en orden.

# 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

Sugiero que resuelva esto incrementalmente y almacene todos los números feos que encuentre en una lista.

Al comprobar un número de fealdad a continuación, sólo tiene que comprobar si se trata de uno de sus momentos de números 2, 3 o 5.

EDIT: Acabo de intentar poner en práctica que como esto

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] 

pero este enfoque se estanca irremediablemente. Demasiado inocente. :) Usa algo así como Tamiz de Eratóstenes.

Answer 3

utilizar una lista (n en el siguiente código) para almacenar todos los números feos prev, el siguiente número feo es el número min de (n * 2, n * 3, n * 5) que es más grande que 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] 

Es una solución O (n^2), por lo que no intente con números grandes.

Answer 4

Aquí hay una solución usando un montón. La idea es que hagamos un seguimiento de los exponentes junto con el producto feo. Para cada iteración, el algoritmo realiza hasta 3 operaciones de find_min y 3 operaciones de inserción. Find_mins puede ser redundante porque puede obtener cada una agregando una a cualquier exponente, y hay tres exponentes. Hacemos una inserción tres veces porque agregamos una a cada exponente e insertamos eso en el montón. Para encontrar el enésimo número feo, tenemos que realizar N operaciones que son 6 * O (log n), por lo que el algoritmo tiene una complejidad temporal de O (n log n). El montón en sí mismo, dado que solo puede crecer en una cantidad constante para cada iteración, es 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