Чтобы решить эту проблему, я сначала заметил, что
Где - число (не обязательно простых) делителей числа . Если наименьшее целое число такое, что , то
Теперь мы должны выбрать такое , что минимален. Выбор для тривиален - это просто простые числа в порядке возрастания.
Тем не менее, моя первая мысль о выборе был неправильным. Я думал, что вы могли бы просто множить , отсортировать факторы в порядке убывания и вычесть 1. В большинстве случаев это работает нормально, например, наименьшее целое число с делителями:
15 = ( 4 + 1 ) ( 2 + 1 ) т = 2 4 3 2 = 144
Но это неверно для :
16 = ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) т = 2 1 3 1 5 1 7 1 = 210
Тогда как правильный ответ:
m = 2 3 3 1 5 1 = 120
Поэтому ясно, что иногда нам нужно объединять факторы. В этом случае, потому что . Но я не вижу четкой и прямой стратегии слияния. Например, можно подумать, что мы всегда должны сливаться со степенью 2 , но это не так:
m = 2 96 3 1 5 1 7 1 11 1 > 2 96 3 3 5 1 7 1
Я не могу сразу придумать пример, но мой инстинкт говорит, что некоторые жадные подходы могут потерпеть неудачу, если они сначала объединят неправильные силы.
Существует ли простая оптимальная стратегия объединения этих полномочий, чтобы получить правильный ответ?
Однако оптимальным решением является:
источник
Ответы:
Вот решение, основанное на моих комментариях выше. Я не утверждаю, что это оптимально.
И у нас также есть повторение:
Для этого вот код Python, который согласуется со всеми числами, которые вы дали выше. Обратите внимание, что он работает с логарифмами, чтобы сохранить числа меньшими: поэтому фактическое целое число вы ищете
round(2**smallest(n))
.источник
powerset
for factor_list in powerset(factors)
то, что генерирует каждый отдельный делительn
ровно один раз. Таким образом, например, для , когда вы рассматриваете решения, содержащие ровно первые простых чисел, как их отдельные простые факторы, вы будете выполнять только нерекурсивную работу вместо , который является экспоненциальным по . 2 k O ( k 2 )multiplicative_partitions(24)
, который производит (среди прочего) разбиения[4, 3, 2]
и[6, 2, 2]
которые (после изменения порядка, чтобы дать наименьшему простому фактору наибольший показатель степени) соответствуют решениям и соответственно. Алгоритм Стива D никогда не будет рассматривать последнее решение, поскольку он уже определил, что подстановка .Возможными кандидатами на «наименьшее целое число с 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⋅3 23⋅33 23⋅3⋅5 2⋅3⋅5⋅7 23⋅3⋅5=120
Если n - произведение двух простых чисел p · q, p ≥ q, единственными кандидатами являются и , а последнее всегда меньше ,2pq−1 2p−1⋅3q−1
Вы можете выяснить некоторые условия, когда, например, может быть коэффициент , проверив, для некоторых штрих х, это не фактор. В примере n = 16 есть множитель потому что . 2 a b - 1 > 2 a - 1 · x b - 1 2 3 2 3 < 2 · 72ab−1 2ab−1>2a−1⋅xb−1 23 23<2⋅7
источник