Prime Sums

[svb]

Nataly-Mak

(Оффтоп)

Цитата:

Ах, так это мы его обидели?!

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

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

Еще мне нравится: "Задача плохая - никак не решается".

[Nataly-Mak]

Сейчас хотела определить схему для приведённого выше решения с 13 выставленными зачётными линиями для Q=3100, и заодно определить побочную зачётную линию.
Ни черта не получается!

whitefox
не поможете?
У меня во-первых, мозги замёрзли, а во-вторых, все волнения сегодняшнего утра...
Ничего не соображаю
Может быть, я не те решения просматриваю? Вполне возможно.
Сейчас попробую нарисовать одно из решений с 12 выставленными зачётными линиями из той же порции решений (Q=3100).

Я рассуждаю так: если у вас программа выбрала схему-разбиение для Q=3100, то сумма всех 14 зачётных линий должна быть 3100, даже если не все эти линии будут иметь простые значения. Правильно?
Но в приведённом решении с 13 выставленными зачётными линиями я никак не могу набрать сумму 3100.

-- Ср дек 19, 2012 18:59:45 --

Нет, порцию решений я не перепутала.
Вот решение с 12 выставленными зачётными линиями из этой же порции (Q=3100):



И здесь всё получается. Значения 12 выставленных зачётных линий:

233,251,211,199,197,223,239,227,193,241,191,229

Сумма этих значений равна 2634, разность: $3100-2634=466$.
Это значение дают в сумме две зачётные линии: 234 и 232.
Всё правильно. Правда, схему не рисовала.

А с 13 зачётными линиями что-то никак не разберусь

[whitefox]

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

Может быть, я не те решения просматриваю? Вполне возможно.

Скорее всего.
Сумма 14 наибольших чисел даёт только 3040.

-- 19 дек 2012, 19:07 --

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

Я рассуждаю так: если у вас программа выбрала схему-разбиение для Q=3100, то сумма всех 14 зачётных линий должна быть 3100, даже если не все эти линии будут иметь простые значения. Правильно?

Да.

[Nataly-Mak]

Нет, как я уже сказала, это решение из той же порции, из которой я привела решение с 12 выставленными зачётными линиями.
Это и странно! С 12 линиями всё получается, а с 13 линиями не получается.
Что же за схема выбрана в решении с 13 линиями?

Вот эти решения из одной и той же порции, я их просматриваю с самого утра:

(Оффтоп)

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

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


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

В конец я записала все решения с 12 выставленными зачётными линиями.
Звёздочкой пометила решение с 13 выставленными зачётными линиями, которое здесь приведено. Те решения, что выше, ещё не просматривала. Все прочие, что были ниже решения, помеченного звёздочкой, удалены. Там были решения с разными количествами зачётных линий от 14 до 18. Но в самом файле решения сохранены. Могу вам их прислать все.

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

[Gerbicz]

svb:

"Maybe he fiercely hates all Russian in 1956 and this hatred manifests itself in such a strange way?"

No, I don't hate Russians. It has no connection with History, what I also know pretty well. Have I said that I have participated also on team contests in History as a child?

My father is working on a book about the Hungarian Revolution of 1956 and on Kádár era (1956–1989), named as http://en.wikipedia.org/wiki/Goulash_Communism . He talkes with survivors of the Revolution. Btw he is not a writer. Sometimes I have a feel that we are the last polyhistor family in the world.

Nataly:
"In protest, I will leave the contest"
Nobody asked it. But it would be fair to merge the accounts/results on the contest with the other Russians.

[svb]

Gerbicz

(Оффтоп)

Извините, но 1956 год я упомянул с долей иронии. Просто странно ваше объединение различных участников соревнования по национальности. Например, Alex Chernov всегда выступает в одиночестве - он то чем провинился? Vladimir Chirkov нам также неизвестен, как и вам. Мы даже не знаем из какого он города (реальный Бобруйск находится не в России, но есть мифический Бобруйск). Какие претензии к нему?
Ранее существовала "команда": Natalya Makarova, Valery Pavlovsky и Serg Belyaev, но по различным причинам она распалась - в настоящем конкурсе мы участвуем по одиночке, общаемся только через этот форум. С какого перепуга мы должны объединяться под одним account-ом? Может вы предполагаете, что мы втайне общаемся между собой? Но это предположение лежит на вашей совести и не имеет отношения к реальности.
"contest with the other Russians" - это омерзительный расизм, но пусть в этом разбираются организаторы конкурса, нам в России своих проблем хватает. Лично я, конечно, больше не собираюсь общаться ни с расистами, ни с людьми их поддерживающими.
Я воспитывался на книгах Д. Пойа, поэтому очень симпатизирую венграм, а вас отношу к неприятному недоразумению.

[Nataly-Mak]

whitefox
я всё поняла, проанализировав следующие решения (выше решения со звёздочкой).
Дело в том, что ваша программа объединила две порции решений: с Q=3086 и с Q=3100. Накануне я искала решение с Q=3086. На другой день стала искать решения с Q=3100, но забыла переименовать последний файл с решениями (хотя всегда это делаю, чтобы не смешивать разные решения). И программа продолжила записывать решения в этот же файл.
Решение со звёздочкой с 13 выставленными зачётными линиями относится к решениям с Q=3086. 14-ая зачётная линия в нём имеет значение 195. Всё верно.

Кстати, вот ещё пример, который показывает, что ваша программа не привязана к конкретным разложениям Q на 14 простых чисел. Если бы она была привязана к этим разложениям, то такое решение не появилось бы. При 13 выставленных зачётных линиях в этом случае 14-ая зачётная линия получается автоматически и правильно, то есть она тоже обязана быть простым числом.

(Оффтоп)

svb
я очень надеялась, что на этот раз никто не будет отвечать Gerbicz.
Он ещё имеет наглость тут появляться!
Да, кстати, почему это вы говорите о моей щепетильности? Gerbicz обвиняет в воровстве не лично меня, а всех русских участников конкурса, следовательно, и вас тоже.

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

[svb]

Nataly-Mak

(Оффтоп)

Цитата:

Да, кстати, почему это вы говорите о моей щепетильности? Gerbicz обвиняет в воровстве не лично меня, а всех русских участников конкурса, следовательно, и вас тоже.

Согласен, не совсем корректно я выразил свою мысль, поэтому рекомендую, все же, прочитать мой прощальный ответ - я же у вас пока не в "игноре" .

[Gerbicz]

svb: ""Contest with the other Russians" - racism is disgusting,"
"I'm not going to talk to any racist"

I don't know why you interpret my sentences in this way. You can also include Herbert Kociemba from Germany to Russians as cheaters. But I think then I will be also Nazi. (http://en.wikipedia.org/wiki/Nazi)

[Nataly-Mak]

Выше я приводила решение для Q=3102 с 12 выставленными зачётными линиями.
Более подробно об этом решении, чтобы не пропало в ворохе моих черновиков.
Структура: 2,15,16,13,3.
Схема:

4 3 2 1 1 3 4
3 2 0 1 0 2 3
3 3 2 1 3 3 3
1 2 1 2 1 3 1
1 1 2 2 2 1 2
3 3 2 3 2 3 2
2 3 1 0 1 2 2

Разбиение естественное.
Решение:



Подчеркну: это не готовое решение, а только приближение к решению; такие приближения в прошлом конкурсе выкладывали пачками не только на нашем форуме, но и на форуме конкурса (раскраски с "дырками", раскраски с ошибками, раскраски, заполненные единичками).

Может быть, полное решение для Q=3102 существует, но его пока никто не нашёл. Однако ведь никто и не доказал, что оно не существует (?).

Сейчас раскопаю в своих черновиках решение для Q=1798 тоже с 12 выставленными зачётными линиями.

-- Чт дек 20, 2012 06:38:38 --

N=7, Q=1798.
Структура: 2,16,13,16,2.
Схема:

0 0 1 1 2 3 3
2 1 1 3 4 3 3
1 1 1 1 3 2 1
1 3 3 2 2 3 3
2 1 2 1 1 1 2
3 3 1 2 3 2 3
2 2 2 1 3 4 3

Разбиение естественное.
Решение:



Выставлено 12 зачётных линий.
Отмечу: решения найдены по программе whitefox. Я только покрутила программу n часов, потом просмотрела выведенные в файл решения.

Если кто-то нашёл решения для Q=1798 и Q=3102 с 13 выставленными зачётными линиями, пожалуйста, по окончании конкурса покажите. Интересно!
Мне пока такое решение программа не выдала.

Для Q=3100 выше показала решение с 12 выставленными зачётными линиями.
Сейчас запущу программу на поиск решений для Q=3098 и Q=1800.

[Pavlovsky]

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

У меня вопрос о количестве неизоморфных схем. Это количество было получено "строго"?

Для N=6,7 я перебирал все схемы. Затем по Россеру удалял изоморфные копии. Но почему то количество неизоморфных схем у меня отличается от данных whitefox. Кто то ошибся, скорее всего я.

-- Чт дек 20, 2012 08:50:46 --

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

Может быть, полное решение для Q=3102 существует, но его пока никто не нашёл. Однако ведь никто и не доказал, что оно не существует

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

Это свойство подтверждает такой факт. Рекорды для N=5,6,7:
N=5
минимум 502 (соответсвующий максимум 798)
максимум 790 (соответсвующий минимум 510)
N=6
минимум 890 (1774)
максимум 1758 (906)
N=7
минимум 1802 (3098)
максимум 3090 (1810)

Рекорды для минимума ближе к теоретическим оценкам, чем рекорды для максимума. Это объясняется тем, что для максимума используются большие простые чисала. А как известно плотность простых чисел с ростом их значений уменьшается. Поэтому маловероятно, что для минимума N=7 лучшим результатом будет 1802, а для максимума мы неожиданно найдем решение 3102.

[Nataly-Mak]

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

Для N=6,7 я перебирал все схемы. Затем по Россеру удалял изоморфные копии. Но почему то количество неизоморфных схем у меня отличается от данных whitefox. Кто то ошибся, скорее всего я.

Ну, вот и разберитесь, кто напутал, а то сразу и заняться нечем
Для науки пригодятся точные данные.
Энтузиазм проверять все 200 000 схем для поиска решения 1800 у вас пропал. Кстати, что-то вы загнули с количеством схем-разбиений-разложений, кажется мне. Опять, небось, на калькуляторе считали
Разложения по вашей теории достаточно проверять только последние, или хотя бы 2-3 последних в списке.

Сейчас попробовала применить к решению Q=3102 своё преобразование "строки-диагонали". Очень интересно превратились строки/столбцы в прямые и обратные диагонали, а прямые и обратные диагонали в строки/столбцы.
Вот такое решение получилось:



Разумеется, тоже выставлены 12 зачётных линий.

[Nataly-Mak]

Промотрела несколько решений из файла, выданного при поиске решения Q=3090.
Вот же досада: всё есть - от 13 до 18 (2 одинаковые) выставленных зачётных линий; да, и 14 зачётных линий есть, но! Q<3090 и даже Q<3086
Вот что такое не везёт

Среди решений с 14 выставленными зачётными линиями есть, например, такие:
2888, 3006, 2868, 2898, 3000, 2916, 3022, 2932, 3008, 2880. Это я ещё не просмотрела все решения, там их море.

Вот решение с 18 зачётными линиями (2 одинаковые):

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

И всё не то, что нужно. Где находится то, что нужно, я не знаю абсолютно

В решении с 13 правильными зачётными линиями 14-ая зачётная линия имеет значение 209, Q=3090. Всё замечательно за исключением того, что число 209 не простое.

[whitefox]

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

Для N=6,7 я перебирал все схемы. Затем по Россеру удалял изоморфные копии. Но почему то количество неизоморфных схем у меня отличается от данных whitefox. Кто то ошибся, скорее всего я.

Я тоже перебирал все схемы, но делал это в лексикографическом порядке.

Для этого занумеровал все строки от 1 до 7, столбцы от 8 до 14, прямые диагонали от 15 до 21, обратные диагонали от 22 до 28, а каждую схему представил упорядоченным множеством зачётных линий.

Для каждого класса изоморфных (по Россеру) схем определил каноническую схему как наименьшую в лексикографическом порядке среди всех схем этого класса.

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

На выходе получил все канонические схемы с оценкой не выше 1816.

[Pavlovsky]

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

Разложения по вашей теории достаточно проверять только последние, или хотя бы 2-3 последних в списке.

От своих слов не отказываюсь. Но при поиске рекордов для N=7 решил, на всякий случай, не использовать эту гипотезу. Получется схем 1798 больше тысячи, распределений чисел по группам 14, наборов простых чисел для каждой схемы разное, но в среднем штук 20. 1000*14*20 примерно 200 000. Только начальная подготовка займет дня два-три. Сколько будет работать основной алгоритм, посчитать на пальцах невозможно.

-- Чт дек 20, 2012 12:56:20 --

whitefox У меня алгоритм один в один с вашим. Кто у кого идею спер?
Единственоое отличие. Я перебор делал с ограничениями:
1) Количество линий каждого типа примерно одинаково. То есть для N=7 равно 3 или 4. Реализовать это ограничение при переборе не трудно.
2) Есть хотя бы одна ячейка, где пересекаются 4 линии. То есть перебираю схемы, где всегда есть линии 1,5,8,22. Это позволяет не рассматривать все N^2 переоносов на торе. А только переносы на торе, которые перемещают ячейки веса 4 в левый верхний угол.