Prime Sums

[Pavlovsky]

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

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

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

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

[Nataly-Mak]

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

[dimkadimon]

Pavlovsky в сообщении #631102 писал(а):

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

Имено этого я и боялся :(

Nataly-Mak в сообщении #631103 писал(а):

Например текущий рекорд для N=5 502. Легко подбором узнать какие простые числа входят в состав этого рекорда.

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

-- 15.10.2012, 13:34 --

dimkadimon в сообщении #631105 писал(а):

Ну, не верю я, что тут обошлось без кластеров

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

[Nataly-Mak]

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

[Pavlovsky]

dimkadimon в сообщении #631105 писал(а):

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

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

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

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

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

[Nataly-Mak]

Pavlovsky в сообщении #631112 писал(а):

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

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

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

Так, буду писать книгу, а программку для квадрата 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.
Наверное, и более точные оценки можно найти

[Pavlovsky]

Nataly-Mak в сообщении #631131 писал(а):

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

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

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

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

[Nataly-Mak]

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??

[Pavlovsky]

Сорри N^2*(N^2-1)

[dimkadimon]

Pavlovsky в сообщении #631134 писал(а):

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

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

[Pavlovsky]

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 заполняем в последнюю очередь.

[Nataly-Mak]

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

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

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

[Pavlovsky]

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

[Nataly-Mak]

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

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

Цитата:

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

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

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

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

17+23+31+37+53+59+61+67+71+83

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

[dimkadimon]

Nataly-Mak в сообщении #631170 писал(а):

17+23+31+37+53+59+61+67+71+83

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