Prime Sums

[Nataly-Mak]

mertz
я получила новую версию программы. Спасибо.
Понимаю, что надо выбрать конфигурацию в том случае, если конфигураций несколько. Ещё не пробовала новую программу.

У меня работала предыдущая версия. Я пыталась искать максимум для N=6 по введённому решению 1758.
Довольно долго работала программа. Лучший результат найден 1746:

6  18:52:06  (1720)  [103,109,127,131,137,139,149,151,157,163,173,181] (3,14,5,28,1,25,22,9,33,16,32,18,2,17,6,24,4,27,34,10,23,15,21,19,12,29,11,36,8,35,30,7,31,20,26,13
6  18:52:42  (1724)  [103,113,127,131,137,139,149,151,157,163,173,181] (3,13,5,29,1,25,31,8,34,16,21,17,2,18,6,22,4,28,32,9,30,20,23,15,11,27,12,36,10,35,24,7,26,14,33,19
6  18:53:13  (1734)  [97,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,22,4,32,34,11,26,16,23,17,7,31,10,36,12,35,24,9,30,18,29,13
6  18:53:15  (1746)  [109,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18
6  18:55:52  (1746)  [109,113,127,131,137,139,149,151,163,167,179,181] (3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18
6  18:55:52  [1746]  26    swappin  3,19,5,33,1,25,27,8,28,14,21,15,2,20,6,24,4,30,34,11,26,13,23,16,7,31,12,36,10,35,22,9,32,17,29,18

Во введённом решении была схема с теоретической оценкой 1760.

Теперь я хочу попробовать искать с конфигурацией, имеющей оценку 887/1777.
Моё предположение: в вашем алгоритме нужна большая удача, чтобы найти самое максимальное решение.

[mertz]

Just sent another version.

Prevents running multiple searches at the same time. Searches deeper.

N < 8 needs swapping to find optimal. The search provided is generic. Works good for N=8 to N=29. N=4k + 2 will not find optimal, needs a different version.

Click on any line in the Configurations box to select.

[Nataly-Mak]

mertz в сообщении #670825 писал(а):

N < 8 needs swapping to find optimal.

Это не поняла в переводе

Есть шансы найти оптимальные решения для N<8?
Это сейчас самое актуальное
При этом интересуют не те решения, что уже найдены конкурсантами, а более оптимальные.

[mertz]

Pavlovsky N=6 Max

0 (  2) 1,2
1 ( 14) 3,4,5,6,7,8,9,10,11,12,13,14,15,19
2 ( 19) 16,17,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,38
3 ( 10) 35,36,37,39,40,41,42,43,44,45
4 (  4) 46,47,48,49

16 and 19 swapped.
35 and 38 swapped.

N < 8 requires different search.

[Nataly-Mak]

mertz в сообщении #670831 писал(а):

Pavlovsky N=6 Max

0 (  2) 1,2
1 ( 14) 3,4,5,6,7,8,9,10,11,12,13,14,15,19
2 ( 19) 16,17,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,38
3 ( 10) 35,36,37,39,40,41,42,43,44,45
4 (  4) 46,47,48,49

mertz
Вы хотели сказать N=7 Max?

Сейчас запустила последнюю версию вашей программы. Выбрала конфигурацию с оценкой 896/1768: 4,10,8,10,4.

Для этой схемы у меня тоже есть программа. Моя программа не даёт решений 1760,1762 и т.д. Существуют ли такие решения
Пока никто не дал ответ на этот вопрос.

[mertz]

I finished 14th. I did not solve N=6 or N=7. I have no program.

[Nataly-Mak]

Забавные решения нашлись для "шестёрки":

(1644)[61,61,89,89,127,131,137,139,149,151,157,163,163,167,173] (15,24,6,33,17,25,23,4,21,7,32,2,9,18,5,27,8,19,36,10,30,14,34,13,20,31,12,35,22,29,28,3,16,11,26,1
(1650)[67,89,89,89,127,131,137,139,149,151,157,163,163,167,173] (16,25,10,34,22,32,29,4,17,6,28,5,12,19,2,24,11,18,33,8,27,14,36,9,15,30,13,35,21,23,26,3,20,7,31,1

В первом решении трое "двойняшек" (пар одинаковых зачётных линий: 61,61; 89,89; 163,163); во втором решении - "тройняшки" и "двойняшки"
Правда, решения не максимальные.

-- Сб янв 12, 2013 22:12:51 --

mertz в сообщении #670854 писал(а):

I finished 14th. I did not solve N=6 or N=7. I have no program.

У вас очень интересная программа! Мне нравится.

Я и мой коллега whitefox тоже не решили задачу для N=7.
А решения для N=6 больше 1758 даже и не искали. Как я понимаю, их вообще никто не искал. Но ведь 1758 далеко от теоретического максимума
Тут надо думать Надо тогда доказать теоретически (строго математически!), что решений больше 1758 не существует. Иначе задача остаётся открытой.

-- Сб янв 12, 2013 22:27:28 --

Решение Pavlovsky 7max.
Эх, до чего же хороша весовая раскраска! Гармония

[dmd]

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

Надо тогда доказать теоретически (строго математически!), что решений больше 1758 не существует.

Это вряд ли возможно, ведь задача связана с простыми числами. В гораздо более простых задачах очень сложно получать строго детерминированные оценки вокруг простых чисел. С другой стороны, именно в этой задаче при больших $N$, насколько понимаю, получена детерминированная оценка максимума и минимума сумм простых. Достаточно уникальный случай с простыми числами.

[Nataly-Mak]

Ну, нет ничего невозможного
Вспоминается: никак не могла доказать, что построенный мной магический квадрат 7-го порядка из чисел Смита является наименьшим. А числа Смита не менее (простых чисел) капризны!
Доказательство блестяще выполнил 12d3. Он использовал для этого представление чисел Смита (элементов квадрата) в виде вычетов по модулю 9.
Лень искать это доказательство в теме "Магические квадраты", очень давно это было.

Чтобы доказать минимальность пандиагонального квадрата 6-го порядка из чисел Смита, мы с коллегами трудились несколько месяцев. А для простых чисел задача была решена svb довольно быстро. Тут надо отметить, что доказательство было переборным, увы! Математического доказательства не нашли.

[mertz]

Can you put the last version as PrimeSums2.zip? Thanks for hosting the files.

[Nataly-Mak]

mertz
я выложила на файлообменник самую последнюю версию вашей программы (от 12/01/13 г.)
http://narod.ru/disk/65433245001.887dcd ... 5.zip.html

-- Вс янв 13, 2013 21:09:33 --

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

Решение Pavlovsky 7max.
Эх, до чего же хороша весовая раскраска! Гармония

Просмотрела все решения нашей команды. Нашла решение, похожее по весовой раскраске на показанное решение Pavlovsky. Это 5min.



Ещё три решения - 6min, 8min, 8max - имеют шахматный порядок весовой раскраски. Одно из решений для N=8 было показано выше.
Больше у нас нет решений с интересной весовой раскраской.

-- Вс янв 13, 2013 21:40:39 --

А так красиво?
Преобразовала показанное выше решение 5min (параллельный перенос на торе).



Симметрия весовой раскраски относительно главной диагонали сохранилась.

[mertz]

here are my solutions to N=5:

492/808 (2,5,9,9,0) 
 (790)  [59,61,67,71,73,79,83,89,101,107]
9,11,20,13,8,3,21,22,6,7,14,12,25,2,1,17,23,24,19,18,5,4,16,10,15
0 (  2) 1,2
1 (  4) 3,4,5,10
2 ( 13) 6,7,8,9,11,12,14,15,16,17,18,19,24
3 (  4) 13,20,22,25
4 (  2) 21,23

490/810 (2,4,13,4,2) 
 (502)  [29,31,41,43,47,53,59,61,67,71] 7,11,12,9,14,6,13,5,1,16,10,18,20,2,24,17,21,19,15,8,3,23,25,4,22
0 (  2) 24,25
1 (  5) 15,20,21,22,23
2 (  9) 8,10,11,12,13,16,17,18,19
3 (  9) 1,2,3,4,5,6,7,9,14
4 (  0)

[Nataly-Mak]

И ещё одна картинка, решение Pavlovsky 7max, перенесённое на торе:



У кого есть решения с красивой весовой раскраской, покажите, пожалуйста.

Кстати, БД на конкурсе в этот раз открывать не собираются?

-- Вс янв 13, 2013 22:37:49 --

Интересный момент: для N=5 есть решения только с 4 весовыми категориями; элементы с весом 4 отсутствуют. Такое решение есть у нашей команды - 5min (см. иллюстрацию выше), и mertz привёл такое решение.
Есть ли такие решения для "шестёрки" и "семёрки"? Предположу, что нет.

[Nataly-Mak]

Эх!.. тишина
Сайт конкурса у меня не открывается. Наверное, решили его совсем закрыть до лучших времён

Тут все пропали. Может, все всё сказали уже?

Я долго крутила программу Эда. Увы, новых рекордов она не даёт

Что ж, будем готовиться к новому конкурсу - на сайте AZ.
Напомню: старт конкурса 19 января тут.

[Pavlovsky]

Двойная схема.

Возьмем схему порядка 7 с оценкой 1802
Схема 1,2,3,4,8,9,10,11,15,16,17,22,25,26
Структура 1,17,16,11,4

Будем искать набор из 7-ми линий, который можно заполнить так чтобы минмально возможная сумма этих линий была меньше заданного порога.
Для вышеприведенной схемы подсхемы меньше или равные порогу 757

Сумма = 756 3,4,9,15,17,22,25
11(7),22(5),21(6),33(2),32(5),31(4),42(2),41(2)
Сумма = 755 3,9,15,16,17,22,25
11(7),22(4),21(8),33(2),32(4),31(5),42(3),41(1)
Сумма = 755 4,8,9,16,17,25,26
11(6),22(6),21(6),33(2),32(4),31(5),42(2),41(2)
Сумма = 756 4,9,15,16,17,22,25
11(7),22(3),21(9),33(2),32(6),31(3),42(2),41(2)
Сумма = 755 4,11,15,16,17,22,25
11(7),22(4),21(8),33(2),32(4),31(5),42(3),41(1)

Запись 21(6) означает 2 - группа для основной схемы; 1 - группа для подсхемы; 6 - количество ячеек обладающих такими свойствами.

1) Получается, что множество чисел мы разбиваем на 5 групп основной схемой, а затем каждую группу еще разбиваем на подгруппы подсхемой.
2) Линии основной схемы делятся на два набора, первый N линий в сумме дают сумму N наименьших простых чисел. Остальные - остальное.

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

Число 757, в примере, это сумма первых семи чисел в наборе простых чисел
97,101,103,107,109,113,127,131,137,139,151,157,163,167