Prime Sums

[Nataly-Mak]

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

Запускаю программу, программа сразу выдаёт несколько решений с 13 правильными зачётными линиями, при этом на экран выводится значение 14-ой зачётной линии.
Показываю окно программы. Значения 14-ой зачётной линии получились 105 и 109. Второе значение уже хорошо, но повторяет одно из первых 13 значений.

Эх-ма! Сижу гляжу, как программа работает, и иногда мозги поворачиваются немножко
Думаю: если программа нашла 13 зачётных линий из множества 14 значений, которое я задала для проверки, то значение 14-ой зачётной линии обязано принадлежать этому же множеству и быть как раз оставшимся 14-ым значением. Откуда же тогда появились значения 109 и 115? надо искать ошибку в программе.
Вот балда! Сплю на ходу У нас затяжной дождичек, ну прямо льёт беспрестанно.

-- Пт дек 07, 2012 17:30:27 --

Ошибку нашла
Снова кручу программу. Теперь появление квадрата с 13 правильными зачётными линиями будет означать, что найдено правильное решение с 14 зачётными линиями.
На экран вывожу теперь решения с 12 правильными зачётными линиями, их выводится море. Как бы в них не утонуть

-- Пт дек 07, 2012 17:41:15 --



Раскинулось море широко,
Квадраты стояли вдали...


Эх, улетела от меня удача

[Nataly-Mak]

Вот такая разница (0,0001) у моей команды тоже была

Цитата:

12 Jim Gillogly 49.971800 12-02-2012 @ 04:59:35
13 Klaus Müller 49.971700 12-07-2012 @ 17:20:46

Кстати, сильный участник Klaus Müller из Германии. Кандидат в десятку.

Pavlovsky
поторопитесь

[whitefox]

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

Неизоморфных схем от 1798 до 1802 всего 1158 штук.

Pavlovsky
Не совсем так.
Неизоморфных схем немного больше -- 1901.

А именно:

Структура      Оценка   Количество
2,15,16,13,3   1798      360
2,16,13,16,2   1798      81
3,13,16,15,2   1798      360
1,18,13,14,3   1800      43
3,14,13,18,1   1800      43
1,17,16,11,4   1802      131
3,12,19,12,3   1802      752
4,11,16,17,1   1802      131

А вот Ваши количества:

Распределение   Сумма   Количество
2,15,16,13,3   1798   238
2,16,13,16,2   1798   51
3,13,16,15,2   1798   199
1,18,13,14,3   1800   29
3,14,13,18,1   1800   26
1,17,16,11,4   1802   103
3,12,19,12,3   1802   453
4,11,16,17,1   1802   59

То что эта таблица не верна видно уже из того, что взаимно дополнительные схемы представлены в разном числе.
Хотя по соображениям симметрии их должно быть поровну.

[Pavlovsky]

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

То что эта таблица не верна видно уже из того, что взаимно дополнительные схемы представлены в разном числе.Хотя по соображениям симметрии их должно быть поровну.

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

Все задачи решены, кроме N=6. Что то задача оказалась сложнее чем ожидал. Или где то ошибка в рассуждениях. whitefox У вас сколько получилось неизоморфных схем для N=6 с суммой 887? У меня получилось 6.

4,10,9,8,5   887   3
5,8,9,10,4   887   3

[whitefox]

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

Напомню для простоты, я рассматривал схемы хотя бы с одной ячейкой веса 4. И еще, рассматривал схемы, количество строк, колонок и два вида диагоналей примерно равно. Плюс минус единица.

В этом и причина различий в наших данных. Я рассмотрел абсолютно все схемы, без сделанных Вами исключений.

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

У вас сколько получилось неизоморфных схем для N=6 с суммой 887? У меня получилось 6.

Подтверждаю.

-- 08 дек 2012, 22:59 --

Для приведённых Вами двух структур существует всего по 40 разбиений множества 1 . . . 36 на пять не пересекающихся весовых классов с оценкой 890.

Итого требуется перебрать всего 6 х 40 = 240 варианта.
Так как при этом числа выбираются только из своего весового класса, то перебор выполняется быстро.

[Nataly-Mak]

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

Итого требуется перебрать всего 6 х 40 = 240 варианта.

Так вот, иногда перебрать 1158 вариантов оказывается проще, чем перебрать 240 вариантов. Случай Pavlovsky

При поиске максимума для N=6 я все n вариантов не перебирала: удача улыбнулась на втором варианте
whitefox прислал мне 14 разбиений с оценкой 1758 для той структуры-схемы, для которой я написала программу полного перебора (а структура-схема была выбрана тоже ведь произвольно, с небольшой наводкой). Я прогнала программу для первого разбиения, мимо. Потом интуиция подсказала: проверь 14-ое разбиение из списка всех разбиений. Загнала его во входной файл, запустила программу, на второй минуте получила готовое решение.

whitefox
а сколько надо было перебрать всего вариантов для поиска решения 1758?

Кстати, ещё одно опровержение закона Мёрфи: решение существует, и оно было найдено в самом начале полного перебора

Немного о терминологии...
Поясню, что означает термин "структура-схема" в моей терминологии.
Это структура: 1,17,16,11,4.
Это одна из схем с такой стуктурой (не показываю полностью, чтобы не дразнить Gerbicz ):

0 0 0 3 1 3 3
1 0 1 1 3 2 2
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x

Вот эта пара и есть "структура-схема".

Для одной и той же структуры может существовать несколько разбиений на непересекающиеся множества чисел с весами 0,1,2,3,4.

Назовём разбиение на множества естественным, если числа во множествах с весами 0,1,2,3,4 следуют в порядке убывания/возрастания. Будем обозначать эти множества чисел с весами 0,1,2,3,4 $M_0,M_1,M_2,M_3,M_4$.
Для приведённой выше структуры имеется естественное разбиение на множества $M_0,M_1,M_2,M_3,M_4$:

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

Обозначим $S_i$ сумму чисел множества $M_i$, $i=1,2,3,4$. Обозначим $Q$ оценку данной структуры. Тогда

$Q=S_1+2S_2+3S_3+4S_4$

Для приведённой структуры оценка $Q=1802$.

Какие есть возражения по терминологии?

[Pavlovsky]

Так и сделаю. Буду всегда начинать перебор с 14-го варианта.

[Nataly-Mak]

Не-а, у вас должна быть подсказка своей интуиции.
В вашем списке удачное разбиение может оказаться 13-ым

Кстати, Pavlovsky, вы первым повторили уникальные рекорды для "семёрки".
Считаю, что второе место вам принадлежит по праву. Дерзайте!

(Оффтоп)

Ох, боюсь, как бы Gerbicz не запустил снова свои остановленные программы. Тогда может быть потеряно и первое место Владимира Чиркова
Вдруг есть решения 1798 или 1800 для "семёрки". Владимир писал, что не уверен в несуществовании этих решений.

[Nataly-Mak]

Борьба за место в десятке сильнейших будет очень острой.

Цитата:

9 Rick Hennig 49.982800 12-09-2012 @ 02:57:09
10 Ed Mertensotto 49.978400 11-20-2012 @ 23:38:02
11 Jim Gillogly 49.976300 12-09-2012 @ 08:16:13

Джим только что вплотную приблизился к десятке.
Rick Hennig сегодня обошёл Эда.

-- Вс дек 09, 2012 12:12:28 --

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



А мне "семёрка" никак не поддаётся

[svb]

Nataly-Mak

Цитата:

Какие есть возражения по терминологии?

Пока установился только один термин - схема. Для любой схемы однозначно определяются количества клеток с весами $a_i$, см., например, сообщение. Наборов ($a_4,a_3,a_2,a_1$,$a_0$) для заданной минимальной суммы существует несколько, но они мало, что дают, только возможность вычисления минимальной и максимальной сумм. Минимальная и максимальная сумма однозначно определяется заданием схемы, я их обознаю $S_\min$ и $S_\max$, но вводить специальное обозначение для этих величин не считаю необходимым (вам больше понравилась $Q$). Для некоторого разбиения $M_0,M_1,M_2,M_3,M_4$ определяется своя сумма.
Суммирую. Более или менее установились термины:
схема;
минимальная сумма,максимальная сумма - для характеристики некоторой схемы;
разбиение - ($M_0,M_1,M_2,M_3,M_4$);
сумма (оценка) - для характеристики некоторого решения.
В отношении конкретных обозначений я бы повременил.

[Nataly-Mak]

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

Пока установился только один термин - схема. Для любой схемы однозначно определяются количества клеток с весами $a_i$

Начнём сначала
Поясните, пожалуйста, что вы понимаете под установившимся термином "схема".
Полагаю, что вы понимаете вот это: 1,17,16,11,4. Правильно?

Тогда как вы назовёте вот это:

0 0 0 3 1 3 3
1 0 1 1 3 2 2
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x

Pavlovsky это называет схемой.
Получается, что не совсем этот термин установился. Я, например, не понимаю, что такое схема.
Ведь запись 1,17,16,11,4 и запись в форме квадрата, заполненного символами 0,1,2,3,4, - это разные вещи. Надо их различать, а значит, надо их назвать по-разному. Если и то, и другое назвать схемой, получается неразбериха.

Поэтому я и предложила для записи 1,17,16,11,4 термин структура.
Такая запись определяет, сколько в схеме чисел с весами 4,3,2,1,0 соответственно.

Теперь по поводу $Q$. Здесь очень часто употребляли термин оценка. Для этого термина я и ввела обозначение.
Поскольку оценка полностью определяется структурой (например, 1,17,16,11,4), логично говорить об оценке структуры.

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

-- Вс дек 09, 2012 13:41:10 --

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

В отношении конкретных обозначений я бы повременил.

А почему повременили бы?
Что или кто мешает нам сейчас определиться с терминологией и обозначениями?
Ведь это облегчит нам дальнейшее обсуждение задачи: будем лучше понимать, о чём говорит каждый из участников дискуссии, если все будут придерживаться одной терминологии.

-- Вс дек 09, 2012 13:53:27 --

Кстати, вот здесь

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

А именно:

Структура      Оценка   Количество
2,15,16,13,3   1798      360
2,16,13,16,2   1798      81
3,13,16,15,2   1798      360
1,18,13,14,3   1800      43
3,14,13,18,1   1800      43
1,17,16,11,4   1802      131
3,12,19,12,3   1802      752
4,11,16,17,1   1802      131

whitefox уже придерживается предложенной мной терминологии. Следовательно, он её принимает
В третьей колонке таблицы указывается количество неизоморфных схем для данной структуры (первая колонка). Например, для структуры 2,15,16,13,3 существует 360 неизоморфных схем.
Во второй колонке указана оценка данной структуры $Q$.
Вот так мне понятно, о чём идёт речь.

-- Вс дек 09, 2012 14:09:15 --

Цитата:

Теперь по поводу $Q$ . Здесь очень часто употребляли термин оценка. Для этого термина я и ввела обозначение.
Поскольку оценка полностью определяется структурой (например, 1,17,16,11,4), логично говорить об оценке структуры.

А вот здесь, наверное, не так.
Оценка не определяется полностью структурой. Правильно? Для определения оценки нужно знать ещё разбиение на множества $M_0,M_1,M_2,M_3,M_4$.

Тогда у меня возникает такой вопрос
whitefox
вы в вашей таблице какие разбиения использовали для определения оценки структуры? Может быть, по умолчанию всегда использовалось естественное разбиение?

Вот, возьмём, к примеру, структуру 1,17,16,11,4. Если брать естественное разбиение на множества $M_0,M_1,M_2,M_3,M_4$, то оценка этой структуры будет 1802. Но если взять другое разбиение на множества, то оценка ведь изменится.

[whitefox]

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

Напомню для простоты, я рассматривал схемы хотя бы с одной ячейкой веса 4. И еще, рассматривал схемы, количество строк, колонок и два вида диагоналей примерно равно. Плюс минус единица.

Провёл поиск всех неизоморфных схем с оценкой не более 1802 при Ваших ограничениях, а именно в схеме имеется хотя бы она ячейка веса 4 и в каждом подмножестве линий (строки, столбцы, прямые диагонали, обратные диагонали) зачётными являются либо три, либо четыре линии.

Результаты получились те же самые, что и без этих ограничений:

Структура      Оценка   Количество
2,15,16,13,3   1798      360
2,16,13,16,2   1798      81
3,13,16,15,2   1798      360
1,18,13,14,3   1800      43
3,14,13,18,1   1800      43
1,17,16,11,4   1802      131
3,12,19,12,3   1802      752
4,11,16,17,1   1802      131

-- 09 дек 2012, 14:35 --

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

whitefox
а сколько надо было перебрать всего вариантов для поиска решения 1758?

Имеется всего две неизомрфные схемы с оценкой 1760.
Для каждой из них имеется по 14 разбиений с оценкой 1758.
Итого нужно было проверить максимум 2 х 14 = 28 сочетаний схема-разбиение.

Если бы для этих схем решение не нашлось бы, то пришлось бы рассматривать схемы с оценкой 1768, а для них разбиений с оценкой 1758 слишком много.

[svb]

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

Поясните, пожалуйста, что вы понимаете под установившимся термином "схема".

Схема это некоторое множество из $2N$ линий без конкретного числового заполнения.

Цитата:

Полагаю, что вы понимаете вот это: 1,17,16,11,4. Правильно?

Этот набор однозначно определяется схемой, но не наоборот.

Цитата:

Тогда как вы назовёте вот это:

0 0 0 3 1 3 3
1 0 1 1 3 2 2
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x
x x x x x x x

Pavlovsky это называет схемой.

По схеме однозначно строится эта матрица. Возможно, с большой долей вероятности, по этой матрице можно восстановить схему, но это нужно доказать.

Цитата:

Получается, что не совсем этот термин установился. Я, например, не понимаю, что такое схема.
Ведь запись 1,17,16,11,4 и запись в форме квадрата, заполненного символами 0,1,2,3,4, - это разные вещи. Надо их различать, а значит, надо их назвать по-разному. Если и то, и другое назвать схемой, получается неразбериха.

Конечно. Набор 1,17,16,11,4 заведомо может соответствовать разным схемам. В отношении матриц немного сложнее, нужно специально рассмотреть возможность однозначного восстановление набора линий.

Цитата:

Поэтому я и предложила для записи 1,17,16,11,4 термин структура.
Такая запись определяет, сколько в схеме чисел с весами 4,3,2,1,0 соответственно.

Можно, конечно, использовать, но уж очень это вторично. Для этих наборов слово структура слишком "высоко". Если исследовать схемы, то разумно вводить эквивалентность схем на основе изоморфизма. Две схемы называются изоморфными, если между ними (между наборами линий) можно установить взаимно однозначное отображение, сохраняющее "пересечения" линий.

Цитата:

Теперь по поводу $Q$. Здесь очень часто употребляли термин оценка. Для этого термина я и ввела обозначение.

Ранее я использовал $S$ исходя из понятия суммы, чем $Q$ лучше? Но это условность, вам нравится, используйте.

Цитата:

Поскольку оценка полностью определяется структурой (например, 1,17,16,11,4), логично говорить об оценке структуры.

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

Я высказал свои соображения и попробовал объяснить их - смотрите.

Цитата:

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

В отношении конкретных обозначений я бы повременил.

А почему повременили бы?
Что или кто мешает нам сейчас определиться с терминологией и обозначениями?
Ведь это облегчит нам дальнейшее обсуждение задачи: будем лучше понимать, о чём говорит каждый из участников дискуссии, если все будут придерживаться одной терминологии.

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

[Nataly-Mak]

Всё стремительно меняется!

Цитата:

9 Rick Hennig 49.982800 12-09-2012 @ 02:57:09
10 Andrews 49.982700 12-09-2012 @ 13:18:37
11 Ed Mertensotto 49.978400 11-20-2012 @ 23:38:02
12 Jim Gillogly 49.976300 12-09-2012 @ 08:16:13

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

whitefox
и всего-то надо было перебрать 28 вариантов Фи!
Ну, а я перебрала всего 2 Всё-таки повезло.

[Pavlovsky]

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

Результаты получились те же самые, что и без этих ограничений:

Значит все таки где то напутал. Хорошо, что ошибка оказалась не фатальной. Ведь рекордные решения для N=7 найдены. Естетвенно не буду сейчас искать ошибку.