Распределение простых чисел

[wcl.AleX]

Уважаемые члены форума. Никак не могу понять как решить задачу.
Даны первые 40 простых чисел. Каждое из чисел можно использовать только 1 раз. Нужно получить два многочлена, состоящих из произведений только этих простых чисел, так , чтобы разность этих многочленов была минимальной.
Пример : даны первые 16 простых чисел. вид этих многочленов в данной ситуации будет таким:
$ 2\cdot7\cdot13\cdot23\cdot29\cdot31\cdot37\cdot41 - 3\cdot5\cdot11\cdot17\cdot19\cdot43\cdot47\cdot53 = 208303 $
Точно уверен , что решение существует. Сам написал программу которая находит решения в течении пары минут, до первых 35 простых чисел.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: формулы на оформлены ТеХом

Наберите формулы ТеХом, как написано здесь или здесь (или в этом видеоролике), после чего сообщите в теме Сообщение в карантине исправлено и тогда тема будет возвращена.

[zhoraster]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[Алексей К.]

wcl.AleX,

я лишь замечу (авось, сгодится): то, что Вы так называете многочленом, таковым не является. Посмотрите определения, если интересно.

[Sonic86]

Алексей К. в сообщении #659841 писал(а):

я лишь замечу (авось, сгодится): то, что Вы так называете многочленом, таковым не является. Посмотрите определения, если интересно.

Он спрашивает следующее: $P_n=\{p_1,...,p_n\}$, $P_n$ надо разбить на $A_n\cup B_n, A_n\cap B_n=\varnothing$ так, что $\left|\prod\limits_{p\in A_n}p-\prod\limits_{p\in B_n}p\right|\to\min$

Задача скорее всего имеет переборное решение, тут интересно подумать, можно ли как-то существенно ограничить пространство перебора. Надо отказываться от рассмотрения простых и переходить к рассмотрению произвольной возрастающей последовательности $x_n$, растущей не быстро (не быстрее многочлена, например, а может и еще меньше).
Вообще, ТС наверное пытается строить простые числа таким образом. А может и нет...

[ИСН]

http://projecteuler.net/problem=266

[venco]

ИСН в сообщении #659861 писал(а):

http://projecteuler.net/problem=266

Здесь 42 простых числа.

[ИСН]

Один хрен.

[venco]

Похоже задача таки переборная.
Остаётся оптимизировать перебор:
1) вместо произведений считать их логарифмы (суммированием) с точностью double (хватает),
2) вовремя отсекать ветви (когда оставшихся множителей не хватает до нужной величины),
3) заранее посчитать и отсортировать все возможные наборы из некоторого количества последних множителей (чтобы потом использовать бинарный поиск).
После этого даже из 42 множителей ответ будет находиться за секунду.

[ИСН]

У меня выходит, что минимальная разность для 40 простых - это число из 23 цифр, которое кончается на ...1009.

[venco]

ИСН в сообщении #659922 писал(а):

У меня выходит, что минимальная разность для 40 простых - это число из 23 цифр, которое кончается на ...1009.

Same here.

[wcl.AleX]

можно посмотреть на математическую модель программы. На примере 35 простых , разность должна получиться 44413798987295791

[VAL]

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

[wcl.AleX]

Квадратов между чем и чем? Покажите, пожалуйста, на примере , без двойки, с числами 3,5,7,11,13
Числа должны быть 105 и 143

[Nacuott]

Перемножить все заданные простые, извлечь квадратный корень и затем икать произведение половины чисел менее всего отличающееся
от полученного числа, после извлечения корня.Как раз получаются 105 и 143 ближе всего к 122