Prime Sums

[Pavlovsky]

Ed Mertensotto в очередной раз написал гляделку решений. Большое спасибо ему за это!
http://infinitesearchspace.dyndns.org/c ... mment-1231

(Оффтоп)

[svb]

dimkadimon

Цитата:

Ещё была такая идея: убрать число 2N и вместо линий использовать суммы из 5ти чисел. Первое число это одна из N^2 клеток, а остальные 4 это её соседи.

Трудно что-либо сказать о новой задаче. Вот был предыдущий конкурс с задачей, имеющей историю, многое осталось неразгаданным, но так и должно быть.

Задача текущего конкурса не так уж и плоха, просто она еще не "обкатана". В ней есть интересные моменты, которые могут породить будущие интересные задачи. Кое-какие частные задачи можно было бы обсудить на этом форуме. Например, какое максимальное количество простых линий для заданного N? Или линий "полных квадратов"? Некоторые задачи окажутся простыми, но в целом будет вырисовываться любопытная картина. Схемы, которые рассматривал Pavlovsky, тоже очень любопытны для будущих задач.

[dimkadimon]

svb в сообщении #635221 писал(а):

Например, какое максимальное количество простых линий для заданного N?

Очень интересный вопрос. Я решил провести небольшое иследование на эту тему. Я старался увеличить количество простых уникальных линий и количество простых неуникальных линий. Вот таблица моих лучших результатов:

N   4N  уникальные  неуникальные
2   8   3           6
3   12  5           7
4   16  10          12
5   20  15          20*
6   24  21          22
7   28  25          28*
8   32  32*         32*
9   36  33          36*
10  40  38          38
11  44  42          44*
12  48  48*         48*
13  52  50          52*
14  56  54          54
15  60  58          60*
16  64  64*         64*

* означает что результат оптимальный. Из этой таблицы создаются вот такие впечатления:

1. Количество простых уникальных линий можно сделать максимальным только для тех N>=8 где N%4=0
2. Количество простых неуникальных линий можно сделать для всех N>=5 кроме тех N где N%4=2

Почему это так не знаю, было бы интересно узнать ответ. Вот сами решения для N=8, 12 и 16. Красота!

(Оффтоп)

8x8
50,5,43,23,55,11,41,13,
39,33,31,38,4,25,6,35,
63,15,19,8,49,21,36,18,
22,12,2,61,42,64,17,3,
40,14,53,24,32,20,54,34,
1,37,27,62,48,52,26,58,
45,7,46,16,60,29,44,10,
57,28,30,51,59,47,9,56
8x8
простые числа: 59 137 151 173 179 193 197 199 211 223 227 229 233 239 241 251 257 269 271 283 293 311 313 317 337 347 349 353 359 367 373 379

12x12
79,63,90,111,121,102,116,61,72,17,123,22,
66,83,50,141,34,126,84,93,24,81,112,47,
113,57,101,9,40,67,140,6,42,5,1,12,
13,37,71,64,23,106,100,89,14,44,53,29,
118,130,78,142,76,18,128,94,74,4,120,15,
31,80,8,88,30,103,68,99,35,28,77,36,
110,108,132,58,65,20,49,96,21,38,91,33,
122,135,98,27,143,69,109,16,51,62,133,86,
134,60,124,41,3,43,11,119,32,97,138,25,
26,48,54,127,56,144,105,137,55,139,73,75,
115,10,95,52,125,92,82,107,2,87,7,85,
136,46,70,131,45,129,117,114,39,59,19,104
12x12
простые числа: 461 541 569 593 643 653 659 661 683 701 719 733 743 761 769 773 787 797 821 827 829 839 853 857 859 883 911 919 941 947 971 977 991 997 1009 1019 1031 1039 1049 1051 1061 1063 1087 1093 1109 1117 1163 1201

16x16
213,102,36,196,189,55,140,230,28,49,50,225,17,123,34,124,
30,114,2,168,133,116,207,26,94,48,54,143,11,61,76,164,
178,251,91,169,211,57,47,88,101,152,184,24,92,163,227,126,
217,109,16,201,83,226,137,223,121,194,3,146,21,153,216,177,
180,13,89,27,233,237,203,6,19,12,15,56,44,166,148,45,
66,136,199,1,67,110,14,97,63,187,38,229,190,202,132,100,
5,183,131,95,127,239,221,29,7,41,62,10,25,105,254,37,
176,236,155,70,64,23,134,51,125,53,122,249,65,209,119,212,
185,87,139,118,69,72,224,142,103,175,86,241,240,159,244,219,
245,215,106,43,193,188,210,147,4,107,198,250,181,173,174,117,
228,60,256,208,74,35,158,157,33,135,90,77,81,115,253,79,
32,246,192,46,120,238,144,161,111,171,179,255,170,214,234,8,
160,222,252,20,22,108,9,172,235,82,156,98,197,220,68,78,
150,99,71,149,247,31,182,167,93,112,162,138,165,85,232,58,
141,96,243,151,242,130,186,113,104,59,191,248,84,40,206,75,
145,128,39,205,129,204,231,52,218,200,73,154,18,195,42,80
16x16
простые числа: 1447 1459 1483 1493 1553 1559 1571 1601 1613 1663 1693 1697 1699 1723 1777 1801 1811 1831 1861 1867 1873 1889 1901 1913 1951 1973 1987 2003 2017 2027 2039 2053 2063 2069 2099 2111 2113 2131 2141 2161 2203 2243 2267 2273 2287 2293 2297 2309 2311 2333 2351 2357 2377 2383 2423 2447 2473 2503 2521 2543 2551 2621 2659 2843

-- 25.10.2012, 09:36 --

svb в сообщении #635221 писал(а):

Или линий "полных квадратов"?

Я не понял...

[whitefox]

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

Ed Mertensotto в очередной раз написал гляделку решений.

Содержит баг

Например, 9,4,12,20,8,1,17,3,2,6,7,14,23,18,10,25,21,22,15,11,5,19,13,16,24
Имеет простые суммы: 43, 59, 53, 29, 59, 71, 73, 47, 41, 67, 61.
Всего 11 простых сумм, но различных только 10 (59 повторяется дважды).
Следовательно квадрат разрешён, и его сумма 544.

Кто зареген на том форуме, сообщите Эду о баге.

[Pavlovsky]

svb в сообщении #634770 писал(а):

Схемы можно находить и простеньким перебором

Написал простенький перебор. Уже для N=9 считает долго. Нужны хорошие процедуры отсечения вариантов. Пока придумал только это:

Утверждение. Первая строка всегда входит в оптимальную (с минимальной оценкой) конфигурацию.

Это следует из того, что перемещение на торе сохраняет свойство быть решением задачи.

Есть еще такая гипотеза. Количество линий различных типов (строки, колонки, диагонали) должно быть одинаковым, если это возможно (четные N). И отличаться на единицу, если равномерное распределение невозможно (нечетные N).

[svb]

Pavlovsky
И как первые результаты? Если сравнить с вариантом: диагонали на черных полях шахматной доски + вертикали и горизонтали уложены рядом?

Могли бы начинать с точки весом 4, хотя это и не совсем корректно.

dimkadimon

Цитата:

Я не понял...

1,2,4,9,16,25,36,...
Не обязательно такие, просто интересно оценить поведение для различных плотностей.

[Pavlovsky]

svb в сообщении #635620 писал(а):

И как первые результаты?

Я искал конфигурации только для нечетных N. Добавил в перебор гипотез. Конфигурации с оценкой соответсвующей текущим рекордам находятся быстро. Вот закономерности нет никакой. А ведь должна быть!

Результаты для нечетных N
N=5 оценка 482
N=7 оценка 1798
9<=N<=13 текущие рекорды.
Дальше довольно долго.

-- Чт окт 25, 2012 18:11:35 --

svb в сообщении #635620 писал(а):

диагонали на черных полях шахматной доски

Для нечетных N диагонали в месте разрыва меняют свой цвет.

[dimkadimon]

svb в сообщении #635620 писал(а):

1,2,4,9,16,25,36,...
Не обязательно такие, просто интересно оценить поведение для различных плотностей.

Мы пробовали использовать первые N^2 простые числа, где N нечётное. Задача становится гораздо легче, потому что легче создавать простые линии. Думаю если использовать квадраты 1, 4, 9, 16... то будет тот же еффект.

[Pavlovsky]

Похоже задача поиска оптимальной схемы (конфигурации) не очень сложная.

Гипотеза. В задаче поиска оптимальной схемы (конфигурации) нет локальных минимумов. Любой алгоритм по-координатного спуска приводит к глобальному минимуму.

Реализовал простенький алгоритм по-координатного спуска. Он быстро нашел оптимальные схемы для всех N.

В выходные приступаю к написанию основной процедуры построения квадратов. Алгоритмы для этого разработаны. Осталось их закодировать.

[dimkadimon]

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

В задаче поиска оптимальной схемы (конфигурации) нет локальных минимумов. Любой алгоритм по-координатного спуска приводит к глобальному минимуму.

Скорее всего это так, но почему это так?

[Pavlovsky]

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

Скорее всего это так, но почему это так?

Надо думать, тратить время. Для решения задачи, можно использовать и недоказанные утверждения. Лишь бы давало результат.

-- Пт окт 26, 2012 12:54:00 --

Немного думал над здачаей поиска оптимальной схемы. Вырисовывается задача минимизации квадратичной функции с линейными ограничениями.

[Herbert Kociemba]

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

Гипотеза. В задаче поиска оптимальной схемы (конфигурации) нет локальных минимумов. Любой алгоритм по-координатного спуска приводит к глобальному минимуму.

Maybe there are many local minima, but these local minima are all the same and there are lots of them.
It is also possible to find such a minimal solution for odd n just by adding randomly Floor[n/2] or Ceiling[n/2] lines of each kind.
I also found minimal solutions in all cases for odd n if I gave a certain scheme for Floor[n/2] rows and Floor[n/2] columns in advance and then added the diagonals by random. I think many schemes work, I used rows 1,2,3,4.....Floor[n/2] and columns 1,3,5,7...2*Floor[n/2]-1 and found minimal solutions for all odd n

It is also interesting, that for the minima the number of cells with weight 0,1,2,3 and 4 seem to follow a certain pattern. For n=29 I found for example 42,252,253,252,42. For other n similar patterns emerge, for n=15 for example 11,68,67,68,11.

[Gerbicz]

Заголовок: Prime Sums

Herbert Kociemba писал(а):

seem to follow a certain pattern. For n=29 I found for example ****. For other n similar patterns emerge, for n=15 for example ****.

(stars from me)

dimkadimon:
"As far as I understand, problem discussion is ok, provided no solutions are given and no code is released before the end of the contest. "

It should be forbidden to give away configurations for odd n values. Yes, this is not a code, but in this case if you see it then you don't need a code, and the other contestants (like me) needed to write a code (and also to run it!) to find them.

[Herbert Kociemba]

Gerbicz в сообщении #636084 писал(а):

Yes, this is not a code, but in this case if you see it then you don't need a code, and the other contestants (like me) needed to write a code (and also to run it!) to find them.

If I could see any help for finding solutions just by posting the number for the different weights I would not have posted these numbers. You think just with these numbers you can find a solution without coding? Or even find *better* solutions than you already have found?

[Nataly-Mak]

Цитата:

As far as I understand, problem discussion is ok, provided no solutions are given and no code is released before the end of the contest. "

It should be forbidden to give away configurations for odd n values. Yes, this is not a code, but in this case if you see it then you don't need a code, and the other contestants (like me) needed to write a code (and also to run it!) to find them.

dimkadimon
Как один из организаторов конкурса, пожалуйста, предъявите официальные правила конкурса, в которых написано, что запрещено и что разрешено.

Тогда каждый из участников конкурса прочитает эти правила и примет или не примет их.
Если кто-то не согласится принять правила конкурса, тогда он не сможет участвовать в конкурсе.
В случае нарушения официальных правил кем-то из участников конкурса этот участник может быть дисквалифицирован по решению администрации конкурса.

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

По прошлому конкурсу...
На форуме конкурса очень активно обсуждались различные алгоритмы построения решений. В частности, было выложено много квадратов, заполненных единичками, что было отличным подспорьем в дальнейшем решении задачи.
Ещё, например, был выложен алгоритм построения диагональных решений по CDS, что тоже давало неплохие результаты. И многое другое обсуждалось и выкладывалось.

И не прозвучало никаких запретов!