Prime Sums

[Nataly-Mak]

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

А если я вношу изменения в программу, меняющие порядок перебора?

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

Цитата:

Я не говорю, что случайный поиск всегда лучше полного перебора. Скажем в предыдущем конкурсе, когда искал диагональные решения, у меня тоже был полный перебор. Напомню тогда у меня программа работала непрерывно целую неделю. И тоже приходилось придумывать возможность прервать программу и начинать с точки останова.

Я тоже не говорю
Всё зависит от задачи. Где-то полный перебор невыполним за реальное время, приходится прибегать к случайному перебору. Однако у случайного перебора есть свой минус: он не даёт точного ответа на вопрос, есть решение или его нет, в отличие от полного перебора.

[whitefox]

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

Есть 50 баллов!

Браво!!!
Вполне заслуженный результат.
Поздравляю от всего сердца.

С нетерпением жду Нового Года. Уж очень любопытно, что за "секретный ход" Вы нашли.

[Pavlovsky]

whitefox в сообщении #657875 писал(а):

С нетерпением жду Нового Года. Уж очень любопытно, что за "секретный ход" Вы нашли

Блин, мне тоже интересно дотерплю ли до нового года. Или проболтаюсь раньше.

PS За позравления спасибо, но вроде еще рано.

-- Чт дек 13, 2012 15:23:23 --

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

Например, Владимир в этом не уверен.

Найти 1800 для N=7 маловероятно. В этом случае и схем мало и наборов простых чисел мало. Всё протестировал довольно тщательно. Правда различные распределения чисел не проверял. Работал только с двумя видами распределения. Правда Сергей Беляев меня так и не убедил, что распределения чисел могут существенно повлиять на успех поиска.

А вот улучшить 3090 для N=7, можно попробовать. Но для начала сделаю паузу - отдохну от задачи.

-- Чт дек 13, 2012 15:40:29 --

Можно еще попробовать улучшить 1758 для N=6. Но этот результат, без меня, нашли 9 человек. Пытаться улучшить этот результат, означает что я не доверяю квалификации этих 9-ти человек.

[Nataly-Mak]

Красиво расположились россияне:

Цитата:

1 Vladimir Chirkov 50.000000 11-10-2012 @ 15:20:54
2 Valery Pavlovsky 50.000000 12-13-2012 @ 13:15:14
3 Wes Sampson 49.993000 11-07-2012 @ 01:52:19
4 Dmitry Kamenetsky 49.990800 11-01-2012 @ 04:17:50
5 Alex Chernov 49.990800 11-04-2012 @ 20:18:58
6 Robert Gerbicz 49.986400 10-23-2012 @ 22:11:05
7 Herbert Kociemba 49.986400 11-03-2012 @ 13:09:12
8 Serg Belyaev 49.985100 10-31-2012 @ 22:12:29
9 Natalya Makarova 49.985100 12-01-2012 @ 12:39:54
10 Rick Hennig 49.982800 12-09-2012 @ 02:57:09

Мне очень нравится! Пятеро в десятке. Это лучше, чем в прошлом конкурсе. Молодцы!
Теперь задача-минимум - удержать занятые позиции.
Ну, а задача-максимум, понятно, - подняться ещё выше

Что-то давно молчит Алексей Чернов (больше месяца). Уж не бросил ли вообще задачу? А ему до 3-го места совсем близко.

-- Чт дек 13, 2012 15:30:06 --

Обновлённая таблица результатов первых десяти конкурсантов:

[svb]

Nataly-Mak
Это вам будет интересно. Меня туда занесло из-за скандала вокруг Андриянова.

[Nataly-Mak]

Это мне уже давно известно.
Сообщала об этом здесь:
topic15897-105.html

Олег Заикин прислал мне несколько писем. По его просьбе я выслала ему статью [1], в которой в 1992 г. были опубликованы первые три пары ортогональных диагональных ЛК 10-го порядка.
Если статья ещё кого-то интересует, могу выложить на файлообменник.

Кстати, по данной мной ссылке Олег вышел на автора сайта, который мы обсуждали в прошлом конкурсе о раскрасках (в связи с изоморфизмом ЛК). Автор этот из Австралии (знакомец dimkadimon). Им найдены три почти попарно ортогональных ЛК 10-го порядка. Олег прислал мне ссылку на эти квадраты.
Вот цитата из его письма, содержащая эту ссылку:

Цитата:

Лучшее что он смог найти на данный момент - вот эта тройка.http://users.monash.edu.au/~iwanless/da ... MOLS10.txt
В ней, если я правильно понял, 1-ый квадрат ортогонален 2-му и 3-му, а вот 2-ой ортогонален 3-му только в 91 ячейки из 100.

[svb]

Nataly-Mak

Цитата:

Это мне уже давно известно.

Статья появилась 11 декабря 2012 года, т.е. "давно известно" вы говорите "из вредности"

[Nataly-Mak]

(Оффтоп)

Мне известно всё то, что написано в статье, из переписки с Олегом Заикиным.
Какая разница, когда появилась статья? В ней не сообщается ничего нового сверх того, что мне известно.
Абсурдное обвинение во "вредности".
Я же привела конкретные ссылки, которые подтверждают, что мне это действительно давно известно.
Б-р-р-р...

[svb]

Nataly-Mak
Я сейчас очень злой, поэтому промолчу, но "спасибо" я от вас и не ждал.

[Nataly-Mak]

(Оффтоп)

"Когда я злой бываю, семерых побиваю".
Советую вам впредь с "вредными" не связываться, особенно в тот момент, когда вы очень злой.

[Nataly-Mak]

Интересная ситуация с повторением рекордов

максимумы:

Цитата:

5 790 Mark Mammel @ 17:02:19 on 10-13-2012 31
6 1758 Robert Gerbicz @ 22:11:05 on 10-23-2012 10
7 3090 Vladimir Chirkov @ 15:20:54 on 11-10-2012 2

минимумы:

Цитата:

5 502 Wes Sampson @ 07:05:13 on 10-13-2012 28
6 890 Robert Gerbicz @ 19:04:23 on 10-18-2012 12
7 1802 Vladimir Chirkov @ 10:21:09 on 11-09-2012 2

Для N>7 рекорды нашли от 14 до 18 конкурсантов.
Рекордные решения для "семёрки" поддались пока только двоим. Это достойно восхищения!

[dimkadimon]

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

Есть 50 баллов! Чем еще заняться? Когда искал решения для N=7, попробовал искать рекорды. Но ничего даже близко не было. Похоже все рекорды найдены.

Здорово! Поздравляю!!!

-- 14.12.2012, 09:58 --

Вот как можно получить 3092:

(Оффтоп)

179 181 191 193 197 199 211 223 229 241 251 257 269 271
179 181 191 193 197 199 211 227 233 239 251 257 263 271
179 181 191 193 197 199 211 227 233 241 251 257 263 269
179 181 191 193 197 199 211 229 233 239 251 257 263 269
179 181 191 193 197 199 223 227 229 233 251 257 263 269
179 181 191 193 197 199 223 227 233 239 241 257 263 269
179 181 191 193 197 199 227 229 233 239 241 251 263 269
179 181 191 193 197 211 223 227 229 233 239 257 263 269
179 181 191 193 197 211 223 227 233 239 241 251 257 269
179 181 191 193 197 211 227 229 233 239 241 251 257 263
179 181 191 193 199 211 223 227 229 233 241 251 263 271
179 181 191 193 199 211 223 227 229 239 241 251 257 271
179 181 191 197 199 211 223 227 229 233 239 251 263 269
179 181 191 197 199 211 223 227 233 239 241 251 257 263
179 181 193 197 199 211 223 227 229 233 239 241 269 271
179 181 193 197 199 211 223 227 229 233 241 251 257 271
179 191 193 197 199 211 223 227 229 233 239 251 257 263
181 191 193 197 199 211 223 227 229 233 239 241 257 271

А вот 3094:

(Оффтоп)

179 181 191 193 197 199 211 223 227 233 257 263 269 271
179 181 191 193 197 199 211 223 227 239 251 263 269 271
179 181 191 193 197 199 211 223 233 239 251 257 269 271
179 181 191 193 197 199 211 223 239 241 251 257 263 269
179 181 191 193 197 199 211 227 229 233 251 263 269 271
179 181 191 193 197 199 211 227 229 239 251 257 269 271
179 181 191 193 197 199 211 227 233 239 241 263 269 271
179 181 191 193 197 199 211 227 233 241 251 257 263 271
179 181 191 193 197 199 211 229 233 239 251 257 263 271
179 181 191 193 197 199 211 229 233 241 251 257 263 269
179 181 191 193 197 199 223 227 229 233 239 263 269 271
179 181 191 193 197 199 223 227 229 233 251 257 263 271
179 181 191 193 197 199 223 227 233 239 241 251 269 271
179 181 191 193 197 199 223 227 233 239 241 257 263 271
179 181 191 193 197 199 223 229 233 239 241 257 263 269
179 181 191 193 197 199 227 229 233 239 241 251 263 271
179 181 191 193 197 211 223 227 229 233 239 251 269 271
179 181 191 193 197 211 223 227 229 233 239 257 263 271
179 181 191 193 197 211 223 227 229 233 241 257 263 269
179 181 191 193 197 211 223 227 229 239 241 251 263 269
179 181 191 193 197 211 223 227 233 239 241 251 257 271
179 181 191 193 197 211 223 229 233 239 241 251 257 269
179 181 191 193 199 211 223 227 229 233 239 257 263 269
179 181 191 193 199 211 223 227 233 239 241 251 257 269
179 181 191 193 199 211 227 229 233 239 241 251 257 263
179 181 191 197 199 211 223 227 229 233 239 251 263 271
179 181 191 197 199 211 223 227 229 233 241 251 263 269
179 181 191 197 199 211 223 227 229 239 241 251 257 269
179 181 191 197 199 211 223 229 233 239 241 251 257 263
179 181 193 197 199 211 223 227 229 233 239 251 263 269
179 181 193 197 199 211 223 227 233 239 241 251 257 263
179 191 193 197 199 211 223 227 229 233 239 241 263 269
179 191 193 197 199 211 223 227 229 233 241 251 257 263
181 191 193 197 199 211 223 227 229 233 239 251 257 263

Вот 1800:

(Оффтоп)

89 97 101 103 107 109 113 127 131 151 157 163 173 179
89 97 101 103 107 109 113 127 137 151 157 163 167 179
89 97 101 103 107 109 113 127 139 149 151 163 173 179
89 97 101 103 107 109 113 127 139 149 157 163 167 179
89 97 101 103 107 109 113 131 139 151 157 163 167 173
89 97 101 103 107 109 127 131 137 139 151 157 173 179
89 97 101 103 107 109 127 131 137 139 151 163 167 179
89 97 101 103 107 109 127 131 137 139 157 163 167 173
89 97 101 103 107 109 127 131 137 149 151 157 163 179
89 97 101 103 107 109 127 131 139 149 151 157 167 173
89 97 101 103 107 109 131 137 139 149 151 157 163 167
89 97 101 103 107 113 127 131 139 149 151 157 163 173
89 97 101 103 107 113 127 137 139 149 151 157 163 167
89 97 101 103 109 113 127 131 137 139 151 157 167 179
89 97 101 103 109 113 127 131 137 139 151 163 167 173
89 97 101 103 109 113 127 131 137 149 151 157 163 173
89 97 101 107 109 113 127 131 137 139 151 157 163 179
89 97 101 107 109 113 127 131 139 149 151 157 163 167
89 97 103 107 109 113 127 131 137 139 149 157 163 179
89 97 103 107 109 113 127 131 137 139 151 157 167 173
89 97 103 107 109 113 127 131 137 149 151 157 163 167
89 101 103 107 109 113 127 131 137 139 151 157 163 173
97 101 103 107 109 113 127 131 137 139 149 151 157 179
97 101 103 107 109 113 127 131 137 139 149 151 163 173
97 101 103 107 109 113 127 131 137 139 149 157 163 167

Вот 1798:

(Оффтоп)

89 97 101 103 107 109 113 127 131 139 163 167 173 179
89 97 101 103 107 109 113 127 131 149 157 163 173 179
89 97 101 103 107 109 113 127 137 139 157 167 173 179
89 97 101 103 107 109 113 127 137 149 151 163 173 179
89 97 101 103 107 109 113 127 137 149 157 163 167 179
89 97 101 103 107 109 113 131 137 139 157 163 173 179
89 97 101 103 107 109 113 131 137 151 157 163 167 173
89 97 101 103 107 109 113 131 139 149 151 157 173 179
89 97 101 103 107 109 113 131 139 149 151 163 167 179
89 97 101 103 107 109 113 131 139 149 157 163 167 173
89 97 101 103 107 109 113 137 139 149 151 157 167 179
89 97 101 103 107 109 113 137 139 149 151 163 167 173
89 97 101 103 107 109 127 131 137 139 149 157 173 179
89 97 101 103 107 109 127 131 137 139 149 163 167 179
89 97 101 103 107 109 127 131 137 149 151 157 167 173
89 97 101 103 107 113 127 131 137 139 151 157 167 179
89 97 101 103 107 113 127 131 137 139 151 163 167 173
89 97 101 103 107 113 127 131 137 149 151 157 163 173
89 97 101 103 109 113 127 131 137 139 149 151 173 179
89 97 101 103 109 113 127 131 137 139 149 157 167 179
89 97 101 103 109 113 127 131 137 139 149 163 167 173
89 97 101 107 109 113 127 131 137 139 149 157 163 179
89 97 101 107 109 113 127 131 137 139 151 157 167 173
89 97 101 107 109 113 127 131 137 149 151 157 163 167
89 97 103 107 109 113 127 131 137 139 149 151 167 179
89 97 103 107 109 113 127 131 137 139 149 157 167 173
89 101 103 107 109 113 127 131 137 139 149 151 163 179
89 101 103 107 109 113 127 131 137 139 149 157 163 173

Наверное какие то из этих комбинаций сразу отпадают. Например, наверное невозможно иметь 271 и 269 в одном решении?

[Pavlovsky]

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

179 191 193 197 199 211 223 227 229 233 239 251 257 263 
181 191 193 197 199 211 223 227 229 233 239 241 257 271

3094

181 191 193 197 199 211 223 227 229 233 239 251 257 263

1800

97 101 103 107 109 113 127 131 137 139 149 157 163 167

1798

89 101 103 107 109 113 127 131 137 139 149 157 163 173

В наборах для 1798, 1800, 1802 есть очень трудное место: 113 127 между этими числами очень большой разрыв. Мой алгоритм, когда искал решение 1802 как то перепрыгнул это место. Пробовал писать алгоритмы использующие подобные узкие места. То есть сначала заполняем линии в которых суммы равны 89 101 103 107 109 113 127. Так как набор трудный вариантов такого заполнения будет мало. Правда решения для N=7 у меня нашел алгоритм, использующий другие подходы.

[Nataly-Mak]

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

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

Откуда возникла такая эвристика?
Я приводила пример оптимального решения для N=9, в котором разложение на 18 простых совсем не последнее в упорядоченном списке разложений, кажется, третье от конца.
Не вижу причин, почему оно должно быть именно последним в списке.

[Pavlovsky]

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

Я приводила пример оптимального решения для N=9

Этот пример показывает, уже всем известный факт. Для N>=9 задача становится достаточно легкой. Значит мы можем позволить себе очень многое.

-- Пт дек 14, 2012 10:01:27 --

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

должно быть именно последним в списке

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

Есть еще ситуации неопределенности. Например:
3092

179 191 193 197 199 211 223 227 229 233 239 251 257 263 
181 191 193 197 199 211 223 227 229 233 239 241 257 271

Какой из этих наборов лучше, сказать не решусь.