Computando com eficiência o menor número inteiro com n divisores

9

Para resolver esse problema, observei primeiro que

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

Onde ϕ(m) é o número de divisores (não necessariamente primos) de m . Se m é o menor número inteiro tal que ϕ(m)=n , então

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

Agora devemos escolher ei tal que ipiei é mínima. As opções para p são triviais - elas são apenas os primos em ordem crescente.

No entanto, meu primeiro pensamento para escolher ei estava incorreto. Eu pensei que você poderia simplesmente fatorar n , classificar os fatores em ordem decrescente e subtrair 1. Na maioria das vezes isso funciona bem, por exemplo, o menor número inteiro com n=15 divisores é:

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

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

Mas isso está incorreto 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

Considerando que a resposta correta é:

m = 2 3 3 1 5 1 = 120

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

Portanto, é claro que às vezes precisamos mesclar fatores. Nesse caso, porque . Mas não vejo exatamente uma estratégia de fusão limpa e direta. Por exemplo, pode-se pensar que devemos sempre nos unir à potência 2 , mas isso não é verdade:71>222

m = 2 96 3 1 5 1 7 1 11 1 > 2 96 3 3 5 1 7 1

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

Não consigo pensar imediatamente em um exemplo, mas meu instinto diz que algumas abordagens gananciosas podem falhar se fundirem os poderes errados primeiro.

Existe uma estratégia ótima e simples para mesclar esses poderes para obter a resposta correta?


n=3072

22315171111131171191231291311

23325171111131171191231291

25335171111131171191231

No entanto, a solução ideal é:

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

Respostas:

1

Aqui está uma solução, com base nos meus comentários acima. Não afirmo que isso seja ideal.

T(n,m)nm

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

E também temos a recorrência:

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

min1ilog(n)T(n,i)

Para esse fim, aqui está um código Python, que concorda com todos os números que você forneceu acima. Observe que ele trabalha com os logaritmos para manter os números menores: portanto, o número inteiro real que você procura é 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
fonte
nnO(n)O(n2logn)n
j_random_hacker 01/01
O(nlogn)powerset
Acredito que seja mais fácil implementá-lo com eficiência usando programação dinâmica: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 me sinto confortável com o truque do logaritmo - a precisão limitada do ponto flutuante estragará as coisas. Dito isto, não acredito que isso seja realmente mais rápido do que gerar todas as partições multiplicativas. Na verdade, acredito que é exatamente isso que está fazendo disfarçado!
orlp
for factor_list in powerset(factors)nn=2k3k2kO(k2)O((2kk))k
11
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
fonte
3
Perdoe-me, mas isso não responde à minha pergunta, apenas resume o que encontrei na minha pergunta. O título é apenas isso: um título, não a pergunta em si. Sinto que você só leu o título antes de responder. A verdadeira questão está na parte inferior do texto da minha pergunta.
Orlp
Isso é respondido no último parágrafo.
gnasher729
@ gnasher729 Isso está longe de ser uma resposta para uma pergunta "computação eficiente", ou mesmo para "estratégia ideal para mesclar"
yo '