Из заданного числа определите три близких числа, произведение которых является исходным числом

У меня есть номер n, и я хочу найти три числа, продукт которых n, но как можно ближе друг к другу. То есть, если n = 12, то я хотел бы получить 3, 2, 2 в результате, в отличие от 6, 1, 2.

Еще один способ подумать о том, что если n - это объем кубоида, то я хочу найти длины сторон, чтобы сделать кубоид максимально похожим на куб (т.е. длины насколько это возможно). Эти числа должны быть целыми числами.

Я знаю, что вряд ли это будет идеальным решением, и я рад использовать что-то, что дает хороший ответ большую часть времени, но я просто не могу думать, куда идти с этим алгоритмом, Любые идеи?

Ответ 1

Здесь мой первый алгоритм эскиза, при условии, что n относительно невелик:

Вычислить основные факторы n.
Выберите три самых больших и назначьте их f1, f2, f3. Если существует менее трех факторов, назначьте 1.
Перебирайте оставшиеся коэффициенты в порядке убывания, умножьте их на самый маленький в настоящий момент раздел.

Изменить

Возьмем n=60.

Его простые множители 5 3 2 2.

Установите f1=5, f2=3 и f3=2.

Оставшийся 2 умножается на f3, поскольку он является наименьшим.

В итоге получим 5 * 4 * 3 = 60.

Изменить

Этот алгоритм не найдет оптимального, обратите внимание на btillys комментарий:

Рассмотрим 17550 = 2 * 3 * 3 * 3 * 5 * 5 * 13. Ваш алгоритм даст 15, 30, 39, когда лучшие будут 25, 26, 27.

Изменить

Хорошо, вот мой второй алгоритм эскиза с немного лучшей эвристикой:

Задайте список L основные факторы n.
Установите r в кубический корень n.
Создайте набор из трех факторов F, изначально настроенных на 1.
Итерации по простым факторам в порядке убывания:
- Попробуйте умножить коэффициент тока L[i] на каждый из факторов в порядке убывания.
  - Если результат меньше r, выполните умножение и перейдите к следующему простой коэффициент.
  - Если нет, попробуйте следующий F. Если из F s, умножьте его на наименьший.

Это будет работать для случая 17550:

n=17550
L=13,5,5,3,3,3,2
r=25.98

F = { 1, 1, 1 }

Итерация 1:

F[0] * 13 меньше r, установите F в {13,1,1}.

Итерация 2:

F[0] * 5 = 65 отображается ниже r.
F[1] * 5 = 5 меньше r, установите F в {13,5,1}.

Итерация 3:

F[0] * 5 = 65 отображается ниже r.
F[1] * 5 = 25 меньше r, установите F в {13,25,1}.

Итерация 4:

F[0] * 3 = 39 отображается ниже r.
F[1] * 3 = 75 greated, чем r.
F[2] * 3 = 3 меньше r, установите F в {13,25,3}.

Итерация 5:

F[0] * 3 = 39 отображается ниже r.
F[1] * 3 = 75 greated, чем r.
F[2] * 3 = 9 меньше r, установите F в {13,25,9}.

Итерация 6:

F[0] * 3 = 39 отображается ниже r.
F[1] * 3 = 75 greated, чем r.
F[2] * 3 = 27 больше, чем r, но это наименьшее значение F, которое мы можем получить. Установите F в {13,25,27}.

Итерация 7:

F[0] * 2 = 26 greated, чем r, но это наименьший F, который мы можем получить. Установите F в {26,25,27}.

Ответ 2

Здесь используется чисто математический подход, который возвращает оптимальное решение и не требует какой-либо сортировки. Черт, ему даже не нужны простые факторы.

История:

1) Напомним, что для многочлена

сумма и произведение корней даются выражением

где x_i - корни.

2) Вспомните еще один элементарный результат теории оптимизации:

i.e., учитывая две переменные такие, что их произведение является константой, сумма минимальна, когда две переменные равны друг другу. Значения тильды обозначают оптимальные значения.

Следствием этого было бы то, что если сумма двух переменных, произведение которых постоянна, является минимумом, то две переменные равны между собой.

Реформируйте исходную проблему:

Теперь вы можете переформулировать свой вышеперечисленный вопрос как упражнение по набору полиномиальных корней. Мы построим многочлен, удовлетворяющий вашим условиям, и вашими корнями этого полинома будет ваш ответ. Если вам нужны k числа, оптимальные, у вас будет многочлен степени k. В этом случае мы можем говорить в терминах кубического уравнения

Мы знаем, что:

c - отрицательный номер входа (предположим положительный)
a является целым и отрицательным (поскольку все факторы положительны)
b - целое число (которое является суммой корней, взятых по два за раз) и положительно.
Корни p должны быть реальными (и положительными, но уже рассмотренными).

Чтобы решить проблему, нам просто нужно максимизировать a в соответствии с указанным выше набором условий. Единственная часть, которая явно не известна прямо сейчас, является условием 4, которое мы можем легко обеспечить с помощью дискриминанта многочлена.

Для кубического многочлена p дискриминант

и p имеют вещественные и различные корни, если ∆>0 и действительные и совпадающие (либо два, либо все три), если ∆=0. Итак, ограничение 4 теперь читает ∆>=0. Теперь это просто и легко программировать.

Решение в Mathematica

Вот решение в Mathematica, которое реализует это.

И вот тест на некоторые цифры, используемые в других ответах/комментариях.

Столбец слева представляет собой список, а соответствующая строка в столбце справа дает оптимальное решение.

Примечание:

Я только заметил, что OP никогда не упоминал, что 3 числа должны быть целыми, хотя все (включая меня до сих пор) предполагали, что они (вероятно, из-за его первого примера). Перечитав вопрос и перейдя по примеру куба, не похоже, что OP был зафиксирован на целых числах.

Это важный момент, который позволит решить, какой класс алгоритмов следует выполнять и который необходимо определить. Если им не обязательно быть целые числа, существует несколько решений на основе полиномов, которые могут быть предоставлены, один из которых является моим (после ослабления целочисленного ограничения). Если они должны быть целыми числами, возможно, более подходящим может быть подход с использованием области ветвления-n-bound/branch-n-cut/cutting.

Было записано следующее, предполагая, что OP означает, что три числа являются целыми числами.

То, как я реализовал его прямо сейчас, в некоторых случаях может дать нецелое решение.

Причина, по которой это дает нецелое решение для x, заключается в том, что я только максимизировал a, когда на самом деле b также должен быть минимальным (не только это, но также и потому, что я не поставил ограничение на x_i, являющееся целыми числами. Можно использовать теорему целочисленного корня, которая включала бы поиск простых факторов, но усложняла вещи.)

Математический код в тексте

Clear[poly, disc, f]
poly = x^3 + a x^2 + b x + c;
disc = Discriminant[poly, x];
f[n_Integer] := 
 Module[{p, \[CapitalDelta] = disc /. c -> -n}, 
  p = poly /. 
     Maximize[{a, \[CapitalDelta] >= 0, 
        b > 0 && a < 0 && {a, b} \[Element] Integers}, {a, b}][[
      2]] /. c -> -n;
  Solve[p == 0]
  ]

Ответ 3

Может быть умный способ найти самый тёплый триплет, как преследует Андерс Линдаль, но я сосредоточусь на более базовом подходе.

Если я сгенерирую все триплеты, я могу их потом фильтровать, но я хочу, поэтому я начну. Лучший способ, который я знаю для генерации, использует рекурсию:

f[n_, 1] := {{n}}

f[n_, k_] := Join @@
    Table[
      {q, ##} & @@@ Select[f[n/q, k - 1], #[[1]] >= q &],
      {q, #[[2 ;; ⌈ [email protected]#/k ⌉ ]] & @ Divisors @ n}
    ]

Эта функция f принимает два целочисленных аргумента, число в фактор n и количество факторов для создания k.

В разделе #[[2 ;; ⌈ [email protected]#/k ⌉ ]] & @ Divisors @ n используется Divisors для создания списка всех делителей n (включая 1), а затем берется из них из второго (чтобы отбросить 1) до потолка число делителей, деленное на k.

Например, для {n = 240, k = 3} вывод {2, 3, 4, 5, 6, 8}

Команда Table выполняет итерацию по этому списку при накоплении результатов, присваивая каждому элементу q.

Тело Table равно Select[f[n/q, k - 1], #[[1]] >= q &]. Это вызывает f рекурсивно, а затем выбирает из результата все списки, начинающиеся с числа >= q.

{q, ##} & @@@ (также в теле), затем "добавляет" q к каждому из этих выбранных списков.

Наконец, Join @@ объединяет списки этих выбранных списков, которые создаются каждым циклом Table.

В результате все целые множители n в k части, в лексикографическом порядке. Пример:

In[]:= f[240, 3]

Out[]= {{2, 2, 60}, {2, 3, 40}, {2, 4, 30}, {2, 5, 24}, {2, 6, 20},
        {2, 8, 15}, {2, 10, 12}, {3, 4, 20}, {3, 5, 16}, {3, 8, 10},
        {4, 4, 15}, {4, 5, 12}, {4, 6, 10}, {5, 6, 8}}

С выходом приведенной выше функции/алгоритма можно затем проверить триплеты на качество, однако желаемое.

Обратите внимание, что из-за упорядочения последней тройкой на выходе является единица с наибольшим минимальным коэффициентом. Обычно это будет "кубический" результат, но иногда это не так.

Если истинный оптимум должен быть найден, имеет смысл протестировать, начиная с правой стороны списка, отказаться от поиска, если лучший результат не будет найден быстро, так как качество результатов будет уменьшаться при перемещении влево.

Очевидно, что этот метод основан на быстрой функции Divisors, но я полагаю, что это либо стандартная библиотечная функция, либо вы можете найти хорошую реализацию здесь в StackOverflow. При этом это должно быть довольно быстро. В приведенном выше коде найдены все триплеты для n от 1 до 10000 в 1,26 секунды на моей машине.

Ответ 4

ИЗМЕНИТЬ Здесь более короткое объяснение с использованием более эффективного кода KSetPartitions значительно упрощает. Так и некоторые предложения от Mr.W. Общая логика остается неизменной.

Предполагая там не менее 3 простых множителей n,

Найдите список триплетов KSetPartitions для простых множителей n.
Умножьте каждый из элементов (простых множителей) внутри каждого подмножества, чтобы получить все возможные комбинации для трех делителей n (при умножении они дают n). Вы можете думать о делителях как о длине, ширине и высоте ортогонального параллелепипеда.
Параллелепипед, ближайший к кубу, будет иметь кратчайшую диагональ пространства. Суммируйте квадраты трех делителей для каждого случая и выберите наименьший.

Здесь код в Mathematica:

Needs["Combinatorica`"]
g[n_] := Module[{factors = Join @@ ConstantArray @@@ FactorInteger[n]},
  Sort[Union[Sort /@ Apply[Times, Union[Sort /@ 
      KSetPartitions[factors, 3]], {2}]] 
      /. {a_Integer, b_Integer, c_Integer} :>  
           {Total[Power[{a, b, c}, 2]], {a, b, c}}][[1, 2]]]

Он может обрабатывать довольно большие числа, но значительно замедляется по мере роста числа факторов n. Ниже приведены примеры для 240, 2400,... 24000000. Это можно было бы ускорить в принципе, если учесть случаи, когда простой делитель появляется в делителе более одного раза. Я еще не знаю, как это сделать.

In[28]:= g[240]

Out[28]= {5, 6, 8}

In[27]:= t = Table[Timing[g[24*10^n]][[1]], {n, 6}]

Out[27]= {0.001868, 0.012734, 0.102968, 1.02469, 10.4816, 105.444}

Ответ 5

Вместо того, чтобы изобретать колесо, следует признать это как вариацию хорошо известной проблемы NP-complete.

Вычислить простые коэффициенты n.
Вычислить логарифмы этих факторов
Проблема переводится как разбиение этих журналов на три суммы, которые как можно ближе.
Эта проблема известна как вариация проблемы Bin Packing, известной как Многопроцессорное планирование

Учитывая тот факт, что проблема многопроцессорного планирования NP-полная, неудивительно, что трудно найти алгоритм, который не ищет все пространство задачи и находит оптимальное решение.

Но я предполагаю, что уже существует несколько алгоритмов, которые имеют дело с Bin-Packing или Multiprocessor-Scheduling и позволяют найти оптимальные решения эффективно.

Другая связанная проблема (обобщение) - это планирование магазина заданий. См. Описание википедии со многими ссылками на известные алгоритмы.

То, что wikipedia описывает как (часто используемый алгоритм LPT-алгоритма (самое длинное время обработки), именно то, что первым предложил Андерс Линдаль.