2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 67  След.
 
 Re: Prime Sums
Сообщение15.10.2012, 07:27 
Аватара пользователя


21/02/10
1594
Екатеринбург
Придумать интересную задачу очень и очень трудно. Поэтому всегда относился с большим уважением к организаторам подобных конкурсов. Представляю сколько потрачено времени на подготовку задачи конкурса.

Текущая задача немного не в моем вкусе. Нет математики. Нет фундаментальных статей. Задача чисто на написание эвристических приближенных алгоритмов. Ограничение, что только 2n линий должно равняться простому числу, приводит к тому что глубоких локальных минимуов в ней нет. А значит всякие алгоритмы отжига должны давать довольно сильные результаты.

Прибросил несколько идей. По моим оценкам они должны дать результаты не меньше 0,8 от нынешних рекордов. К тому же в этой задаче можно немного читерить. Например текущий рекорд для N=5 502. Легко подбором узнать какие простые числа входят в состав этого рекорда. Эту информацию можно использовать в своих алгоритмах.

Всегда подчеркивал, что для меня процесс важнее результата. Вот думаю стоит ли делиться с общественностью своими идеями?!

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 07:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Заглянула на конкурс. Ни одного участника он-лайн :D
На третий день конкурса уже 5 участников имеют 49 баллов с хвостиком.
Ну, не верю я, что тут обошлось без кластеров :D
Задача явно переборная.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 07:48 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #631102 писал(а):
Текущая задача немного не в моем вкусе. Нет математики. Нет фундаментальных статей. Задача чисто на написание эвристических приближенных алгоритмов. Ограничение, что только 2n линий должно равняться простому числу, приводит к тому что глубоких локальных минимуов в ней нет. А значит всякие алгоритмы отжига должны давать довольно сильные результаты.

Имено этого я и боялся :(
Nataly-Mak в сообщении #631103 писал(а):
Например текущий рекорд для N=5 502. Легко подбором узнать какие простые числа входят в состав этого рекорда.


Думаю это не сработает для больших N

-- 15.10.2012, 13:34 --

dimkadimon в сообщении #631105 писал(а):
Ну, не верю я, что тут обошлось без кластеров :D


Я верю что можно без кластеров, но они конечно помогают.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 08:06 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon
вы немножко перепутали авторов цитат :D
В последнем случае очень смешно получилось: в цитате сказано, что вы не верите, а в вашем ответе на цитату сказано, что верите.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 08:23 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #631105 писал(а):
Думаю это не сработает для больших N


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

-- Пн окт 15, 2012 10:42:47 --

Вот еще вспомогательная задача.

Заполнить квадрат NxN числами от 1 до N^2. Так чтобы сумма чисел во всех строках и во всех колонках равнялась различным простым числам.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 09:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #631112 писал(а):
Вот еще вспомогательная задача.

Заполнить квадрат NxN числами от 1 до N^2. Так чтобы сумма чисел во всех строках и во всех колонках равнялась различным простым числам.

Вы хотите сказать, что можно прекрасно обойтись и без диагоналей? :D

Так, буду писать книгу, а программку для квадрата 5х5 всё же запустила, пусть себе крутится :-)
Она мне не мешает работать. Вот исподволь нашлось небольшое улучшение для максимума: 730 (было 710), на конкурсе текущий максимум 790, по крайней мере, позавчера был. Может быть, уже есть новый рекорд.

Кстати, наверное, можно прикинуть граничные значения для минимума и для максимума.
Весь набор возможных простых сумм известен для каждого N.

Например, для N=5 возможные простые суммы:

Код:
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113

Это я просто по максимуму и минимуму прикинула, фактически, может, и не все из этих сумм возможны, надо проверить.

Тогда верхняя граница для максимальной суммы равна 954, а нижняя граница для минимальной суммы равна 340.
Наверное, и более точные оценки можно найти :?:

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 09:49 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #631131 писал(а):
Вы хотите сказать, что можно прекрасно обойтись и без диагоналей?

Для получения вполне приличных начальных результатов этого вполне достаточно.

1) Задача становится совсем простой.
2) Результат можно посчитать на берегу. Сумма решения будет N*(N-1).

Например для N=5. Результат будет 600. Что при нынешних рекордах даст 600/790 и 502/600 итого 1,59616. Для начала совсем неплохо.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 10:02 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #631134 писал(а):
Например для N=5. Результат будет 600. Что при нынешних рекордах даст 600/790 и 502/600 итого 1,59616. Для начала совсем неплохо.

Вы неправильно считаете баллы, надо коэффициент брать в квадрате.

-- Пн окт 15, 2012 11:08:17 --

Pavlovsky в сообщении #631134 писал(а):
Задача становится совсем простой.
2) Результат можно посчитать на берегу. Сумма решения будет N*(N-1).

Ничего не поняла. Сумма решения будет N*(N-1)=5*4=20??

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 10:11 
Аватара пользователя


21/02/10
1594
Екатеринбург
Сорри N^2*(N^2-1)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 10:17 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #631134 писал(а):
Для получения вполне приличных начальных результатов этого вполне достаточно.


А что если диагонали дадут добавочные простые числа? - тогда в вашем решении будет слишком много простых чисел

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 10:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #631140 писал(а):
А что если диагонали дадут добавочные простые числа? - тогда в вашем решении будет слишком много простых чисел


Это уже легко решаемые мелочи.

Алгоритм получается приблизительно такой.
1) подсчитываем сумму E=N^2*(N^2-1)/2
2) Ищем две группы с различными простыми числами. Сумма чисел в каждой группе равна E.
3) Упрядочиваем числа в группах в порядке убывания.
4) Первая группа это будут суммы строк. Вторая группа это будет сумма колонок.
5) Заполняем квадрат числами начиная с N^2, N^2-1,.. и так далее. Каждое очередное число ставим в ячейку, где остаточная сумма строки и колонки наибольшая.
6) Начиная с некоторого числа N0 переходим на полный перебор.

Это база для дальнейшего совершенствавания алгоритма.

-- Пн окт 15, 2012 12:42:29 --

Усовершенствование алгоритма Вариант №1.

1) подсчитываем сумму E=N^2*(N^2-1)/2
2) Ищем четыре группы с простыми числами. В группах должно быть как можно больше различных простых чисел. Сумма чисел в каждой группе приблизительно равна E.
3) Упрядочиваем числа в группах в порядке убывания.
4) Первая группа это будут суммы строк. Вторая группа это будет сумма колонок. Третья группа сумма прямых диагоналей. Четвертая группа сумм обратных диагоналей.
5) Заполняем квадрат числами начиная с N^2, N^2-1,.. и так далее. Каждое очередное число ставим в ячейку, где остаточная сумма строки, колонки и диагоналей наибольшая.
6) Начиная с некоторого числа N0 переходим на полный перебор. Ищем все решения где 2N линий дают простое число. И подсчитываем минимальную и максимальную сумму.

-- Пн окт 15, 2012 12:46:37 --

Усовершенствование алгоритма Вариант №2.

Выделяем в квадрате две зоны A и B. Зону A заполняем большими числами, начная с N^2 и далее. Зону B заполняем маленькими числами, начная с числа 1. Выбираем 2N линий которые не проходят через зону A, но проходят через зону B. В этих линиях будем выставлять сумму равную различным простым числам. Далее алгоритм аналогичный вышеприведенному. Сначала заполняем зону A. Зону B заполняем в последнюю очередь.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 10:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #631131 писал(а):
Например, для N=5 возможные простые суммы:

Код:
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113

Это я просто по максимуму и минимуму прикинула, фактически, может, и не все из этих сумм возможны, надо проверить.

Проверила, все перечисленные суммы фактически возможны.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 11:06 
Аватара пользователя


21/02/10
1594
Екатеринбург
Немного теории пандиагональных магических квадратов.
Следующие преобразования сохраняют суммы в строках, колонках и диагоналях:
1) Перенос на торе.
2) Зеркальное отражение относительно диагонали квадрата.
3) М- преобразования.
http://www.natalimak1.narod.ru/preobraz3.htm

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 11:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Насколько помню, М-преобразования сохраняют суммы в строках, столбцах и главных диагоналях. Пандиагональность они не сохраняют.

Цитата из указанной статьи о М-преобразованиях:

Цитата:
Следует обратить внимание на то, что М-преобразования не изменяют наборы чисел ни в строках, ни в столбцах, ни в главных диагоналях. Поэтому М-преобразования сохраняют те свойства исходного квадрата, которые зависят от наборов чисел в строках, в столбцах и в главных диагоналях. Например, если исходный квадрат бимагический, то все квадраты, полученные из него М-преобразованиями, тоже будут бимагическими.

А для нашей задачи это даже и хорошо, что М-преобразования не сохряняют суммы по ломаным диагоналям :-)

-- Пн окт 15, 2012 13:08:20 --

Сумму 502 для N=5 можно получить, например, так:

Код:
17+23+31+37+53+59+61+67+71+83

Это я просто подбором нашла.
Но единственный ли это вариант?

 Профиль  
                  
 
 Re: Prime Sums
Сообщение15.10.2012, 12:24 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #631170 писал(а):
17+23+31+37+53+59+61+67+71+83


Думаю нельзя одновремено иметь 17 и 23. Я думал зафиксировать одну линию самой большой (или маленькой) суммой, а искать только остальные. Еще не пробовал, но думаю остальные суммы пострадают.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group