Эффективное вычисление наименьшего целого числа с n делителями

9

Чтобы решить эту проблему, я сначала заметил, что

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

Где ϕ(m) - число (не обязательно простых) делителей числа m . Если m наименьшее целое число такое, что ϕ(m)=n , то

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

Теперь мы должны выбрать ei такое , что ipiei минимален. Выбор для p тривиален - это просто простые числа в порядке возрастания.

Тем не менее, моя первая мысль о выборе ei был неправильным. Я думал, что вы могли бы просто множить n , отсортировать факторы в порядке убывания и вычесть 1. В большинстве случаев это работает нормально, например, наименьшее целое число с n=15 делителями:

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

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

Но это неверно для :n=16

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

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

Тогда как правильный ответ:

m = 2 3 3 1 5 1 = 120

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

Поэтому ясно, что иногда нам нужно объединять факторы. В этом случае, потому что . Но я не вижу четкой и прямой стратегии слияния. Например, можно подумать, что мы всегда должны сливаться со степенью 2 , но это не так: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=3072

22315171111131171191231291311

23325171111131171191231291

25335171111131171191231

Однако оптимальным решением является:

27335271111131171191
orlp
источник
n24m2k1log(2)+k2log(3)k1k2=24mm

Ответы:

1

Вот решение, основанное на моих комментариях выше. Я не утверждаю, что это оптимально.

T(n,m)nm

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

И у нас также есть повторение:

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

min1ilog(n)T(n,i)

Для этого вот код Python, который согласуется со всеми числами, которые вы дали выше. Обратите внимание, что он работает с логарифмами, чтобы сохранить числа меньшими: поэтому фактическое целое число вы ищете 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))
Стив Д
источник
nnO(n)O(n2logn)n
j_random_hacker
O(nlogn)powerset
Я полагаю, что это проще реализовать эффективно с помощью динамического программирования: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 Кстати, мне не очень удобен трюк с логарифмом - ограниченная точность с плавающей запятой в какой-то момент будет мешать. При этом я не верю, что это на самом деле быстрее, чем генерация всех мультипликативных разделов. На самом деле, я верю, что это именно то, что он делает скрытно!
orlp
После более внимательного прочтения комментария @ orlp и вашего кода я думаю, что для временной сложности (и практической производительности) важно изменить for factor_list in powerset(factors)то, что генерирует каждый отдельный делитель nровно один раз. Таким образом, например, для , когда вы рассматриваете решения, содержащие ровно первые простых чисел, как их отдельные простые факторы, вы будете выполнять только нерекурсивную работу вместо , который является экспоненциальным по . 2 k O ( k 2 )n=2k3k2kO(k2)O((2kk))k
j_random_hacker
1
@orlp: я неправильно понял термин "мультипликативные разбиения", извините. Спасибо за код Python. Чтобы понять, почему алгоритм Стива D не параллелен этому коду, рассмотрим multiplicative_partitions(24), который производит (среди прочего) разбиения [4, 3, 2]и [6, 2, 2]которые (после изменения порядка, чтобы дать наименьшему простому фактору наибольший показатель степени) соответствуют решениям и соответственно. Алгоритм Стива D никогда не будет рассматривать последнее решение, поскольку он уже определил, что подстановка . 2332512531512332=72<2531=96
j_random_hacker
-1

Возможными кандидатами на «наименьшее целое число с n делителями» являются целые числа вида где a ≥ b ≥ c ... и (a + 1) (b + 1) (c + 1) ... = n.2a·3b·5c...

Таким образом, вам нужно найти все способы выразить n как произведение целых чисел ≥ 2 в не возрастающем порядке, а также рассчитать и проверить соответствующих кандидатов. Например, когда n = 16, 16 = 8 · 2 = 4 · 4 = 4 · 2 · 2 = 2 · 2 · 2 · 2, то есть возможности , , , , а наименьшее - .27·323·3323·3·52·3·5·723·3·5=120

Если n - произведение двух простых чисел p · q, p ≥ q, единственными кандидатами являются и , а последнее всегда меньше ,2pq12p1·3q1

Вы можете выяснить некоторые условия, когда, например, может быть коэффициент , проверив, для некоторых штрих х, это не фактор. В примере n = 16 есть множитель потому что . 2 a b - 1 > 2 a - 1 · x b - 1 2 3 2 3 < 2 · 72ab12ab1>2a1·xb12323<2·7

gnasher729
источник
3
Простите меня, но это не отвечает на мой вопрос вообще, это просто суммирует то, что я нашел в своем вопросе. Название просто так: название, а не сам вопрос. Я чувствую, что вы только прочитали заголовок, прежде чем ответить. Настоящий вопрос в нижней части моего текста вопроса.
orlp
Это ответ в последнем абзаце.
gnasher729
@ gnasher729 это далеко от того , ответ на вопрос «эффективно вычислить», или даже для «оптимальной стратегии слияния»
йо»