2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Posted automatically
Сообщение17.12.2012, 19:06 
Аватара пользователя
 i  Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
Причина переноса: формулы на оформлены ТеХом

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

 
 
 
 Posted automatically
Сообщение17.12.2012, 19:47 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 19:52 
wcl.AleX,

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

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 20:03 
Алексей К. в сообщении #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$, растущей не быстро (не быстрее многочлена, например, а может и еще меньше).
Вообще, ТС наверное пытается строить простые числа таким образом. А может и нет...

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 20:10 
Аватара пользователя
http://projecteuler.net/problem=266

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 20:20 
ИСН в сообщении #659861 писал(а):
http://projecteuler.net/problem=266
Здесь 42 простых числа.

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 20:21 
Аватара пользователя
Один хрен.

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

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 22:33 
Аватара пользователя
У меня выходит, что минимальная разность для 40 простых - это число из 23 цифр, которое кончается на ...1009.

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 22:59 
ИСН в сообщении #659922 писал(а):
У меня выходит, что минимальная разность для 40 простых - это число из 23 цифр, которое кончается на ...1009.
Same here.

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 23:16 
можно посмотреть на математическую модель программы. На примере 35 простых , разность должна получиться 44413798987295791

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

 
 
 
 Re: Распределение простых чисел
Сообщение17.12.2012, 23:40 
Квадратов между чем и чем? Покажите, пожалуйста, на примере , без двойки, с числами 3,5,7,11,13
Числа должны быть 105 и 143

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

 
 
 [ Сообщений: 50 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group