Calcular eficientemente el entero más pequeño con n divisores

9

Para abordar este problema, primero observé que

ϕ(p1e1 p2e2 pkek)=(e1+1)(e2+1)(ek+1)

Donde es el número de divisores (no necesariamente primos) de m . Si m es el entero más pequeño tal que ϕ ( m ) = n , entoncesϕ(m)mmϕ(m)=n

( e 1 + 1 ) ( e 2 + 1 ) ( e k + 1 ) = n

ϕ(m)=n
(e1+1)(e2+1)(ek+1)=n

Ahora debemos elegir tal que i p e i i sea ​​mínimo. Las opciones para p son triviales: son solo los números primos en orden ascendente.eiipieip

Sin embargo, mi primer pensamiento para elegir fue incorrecto. Pensé que podría simplemente factorizar n , ordenar los factores en orden descendente y restar 1. La mayoría de las veces esto funciona bien, por ejemplo, el entero más pequeño con n = 15 divisores es:einn=15

15 = ( 4 + 1 ) ( 2 + 1 ) m = 2 4 3 2 = 144

15=53
15=(4+1)(2+1)
m=2432=144

Pero esto es incorrecto para :n=16

16 = ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) m = 2 1 3 1 5 1 7 1 = 210

16=2222
16=(1+1)(1+1)(1+1)(1+1)
m=21315171=210

Mientras que la respuesta correcta es:

m = 2 3 3 1 5 1 = 120

16=(3+1)(1+1)(1+1)
m=233151=120

Entonces está claro que a veces necesitamos fusionar factores. En este caso porque . Pero no veo exactamente una estrategia de fusión limpia y directa. Por ejemplo, uno podría pensar que siempre debemos fusionarnos en el poder 2 , pero esto no es cierto:71>222

1552=(96+1)(1+1)(1+1)(1+1)(1+1)
m=296315171111>296335171

No puedo pensar de inmediato en un ejemplo, pero mi instinto dice que algunos enfoques ambiciosos pueden fallar si fusionan primero los poderes equivocados.

¿Existe una estrategia óptima simple para fusionar estos poderes para obtener la respuesta correcta?


n=3072

22315171111131171191231291311

23325171111131171191231291

25335171111131171191231

Sin embargo, la solución óptima es:

27335271111131171191
orlp
fuente
n24m2k1log(2)+k2log(3)k1k2=24mm

Respuestas:

1

Aquí hay una solución, basada en mis comentarios anteriores. No hago afirmaciones, esto es óptimo.

T(n,m)nm

T(n,1)=2n1T(2m,m)=p1p2pm

Y también tenemos la recurrencia:

T(n,m)=mind|n[T(nd,m1)pmd1]

min1ilog(n)T(n,i)

Para ese fin, aquí hay un código de Python, que está de acuerdo con todos los números que proporcionó anteriormente. Tenga en cuenta que funciona con los logaritmos para mantener los números más pequeños: por lo tanto, el entero real que busca es round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')  
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r) 
                                       for r in range(1, len(lst)+1))
Steve D
fuente
nnO(n)O(n2logn)n
j_random_hacker
O(nlogn)powerset
Creo que esto es más fácil de implementar de manera eficiente usando la programación dinámica: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 Por cierto, no estoy muy cómodo con el truco del logaritmo: la precisión limitada de coma flotante en algún momento atornillará las cosas. Dicho esto, no creo que esto sea realmente más rápido que generar todas las particiones multiplicativas. De hecho, ¡creo que eso es exactamente lo que está haciendo disfrazado!
orlp
for factor_list in powerset(factors)nn=2k3k2kO(k2)O((2kk))k
1
multiplicative_partitions(24)[4, 3, 2][6, 2, 2]2332512531512332=72<2531=96
-1

2a·3b·5c...

27·323·3323·3·52·3·5·723·3·5=120

2pq12p1·3q1

2ab12ab1>2a1·xb12323<2·7

gnasher729
fuente
3
Perdóname, pero esto no responde a mi pregunta, solo resume lo que he encontrado en mi pregunta. El título es solo eso: un título, no la pregunta en sí. Siento que solo has leído el título antes de responder. La verdadera pregunta está al final del texto de mi pregunta.
orlp
Eso se responde en el último párrafo.
gnasher729
@ gnasher729 Eso está lejos de ser una respuesta a una pregunta "calcular eficientemente", o incluso "una estrategia óptima para la fusión"
yo