Prime Sums

[Nataly-Mak]

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

Посмотрела на своё решение 1758 для N=6.
Структура: 2,14,8,6,6.
Разбиение:

$M_0=(1,2,3,4,5,6)$
$M_1=(7,8,9,10,11,12)$
$M_2=(13,14,15,16,17,18,19,20)$
$M_3=(21,22,23,24,25,26,27,28,29,30,31,32,33,36)$
$M_4=(34,35)$

Есть несколько способов сделать из этого разбиения разбиение с оценкой Q=1752.
Например, переставить числа с весом 3 и 4 - 28 и 34 (или 29 и 35).

У меня есть программа полного перебора для этой схемы. По этой программе получено решение 1758. Можно попробовать покрутить эту программу с разными разбиениями, дающими оценку Q=1752.

Pavlovsky
какое разложение 1752 на 12 простых вы рекомендуете?
У меня есть такие два варианта:

103,113,127,131,139,149,151,157,163,167,173,179
107,109,127,131,139,149,151,157,163,167,173,179

Возвращаясь к решению 1752...
Я его искала немножко - и по своей программе, и по программе whitefox.

В моей программе задаётся на входе разложение 1752 на 12 простых чисел. И разложение это я не угадала. В цитате приведены два моих варианта разложения.
В решении Vovka17 такое разложение:

109,113,127,131,137,139,149,151,163,173,179,181

А выбранная мной схема с теоретической оценкой 1760 ближе к искомому решению 1752
Попробовать надо проверить свою программу для разложения на простые, как у Vovka17. Может быть для такого разложения решение найдётся.

И вот она - конкретика. Естественное разбиение даёт для выбранной схемы оценку Q=1760. Ищется решение 1752. Сколько будет разбиений для одной выбранной схемы?
whitefox привёл очень хороший алгоритм нахождения всех разбиений при заданной разности теоретической оценки схемы и искомого решения.
В данном примере эта разность равна всего 8. Так что здесь количество разбиений должно быть намного меньше, чем при разности равной 25.

Важно отметить, что программа полного перебора в том случае, когда задаётся конкретное разложение Q на 12 простых, работает намного быстрее, нежели в общем случае, когда массив простых не ограничивается 12 числами.

[Nataly-Mak]

Есть решение 1752!

Итак, ещё раз - выбрано:

Структура: 2,14,8,6,6.
Разбиение естественное.
Схема:

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

Оценка Q=1760.
Ищется решение 1752. Приготовилась проверять n разбиений, но не пришлось
Образовала первое разбиение, поменяв местами числа с весами 3 и 4 - 36 и 28.
Запустила программу, через 15 минут выдано готовое решение:



Вывод: очень многое зависит от разложения Q на простые числа. Прав Pavlovsky!
С другой стороны: не угадав правильное разложение, я не смогла найти решение. Поэтому прав и svb, который не ориентируется на конкретное разложение на простые числа.
Если бы я не задавала в своей программе конкретное разложение (набор только из 12 простых), а выполнила бы полный перебор для всего массива возможных значений зачётных линий, то решение, конечно же, нашлось бы (куда б ему деваться, если оно в этой схеме-разбиении "сидит"). Однако такой перебор выполняется намного дольше.
Такая вот конкретика

[whitefox]

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

whitefox привёл очень хороший алгоритм нахождения всех разбиений при заданной разности теоретической оценки схемы и искомого решения.

В том сообщении я оговорился.
Приведённый там алгоритм даёт нижнюю границу числа разбиений.
Но для малых $top$ это значение точное.

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

Пусть $top$ означает разность между оценкой искомого разбиения и оценкой схемы. И пусть $top \ne 0$.
При поиске минимума $top>0$, а при поиске максимума $top<0$.

Всем числам из множества $M=\{1,\dots,N^2\}$ присвоим вес в соответствии со структурой выбранной схемы и "естественным" разбиением.

Рассмотрим все различные не единичные циклы из разных чисел множества $M$, такие что любые два смежных элемента такого цикла принадлежат разным весовым классам (имеют различный вес).

Каждому такому циклу $(a_1,a_2,\dots,a_r)$ присвоим вес равный $a_1(v_2-v_1)+a_2(v_3-v_2)+\dots+a_r(v_1-v_r)$, где $v_1,v_2,\dots,v_r$ веса соответствующих элементов цикла.
Очевидно, что при поиске минимума эти веса циклов будут положительными, а при поиске максимума -- отрицательными.

Найдём все наборы не пересекающихся циклов, такие что сумма их весов равна $top$. Каждому такому набору взаимно однозначно соответствует разбиение с нужной оценкой.

Число таких наборов и есть число разбиений.

[Nataly-Mak]

Очень хочется теперь поискать решение 1760, взяв структуру с теоретической оценкой Q=1768. Тут тоже разность равна 8.
Эх! Не успела спросить у Pavlovsky, какие он берёт разложения на 12 простых для числа 1760, а собиралась ведь спросить и забыла. Какие самые предпочтительные?

svb
вы не подскажете, какое разложение 1760 на простые числа последнее в списке, как рекомендует Pavlovsky?

Вдруг всё-таки решение 1760 существует на 0,01%.

-- Чт янв 10, 2013 01:06:51 --

Продолжила эксперимент с решением 1752.
Стало любопытно, найдётся ли решение с другим разбиением. Образовала второе разбиение, теперь поменяла во множествах чисел с весами 3 и 4 числа 27 и 35.
Решение найдено за 12 минут:

4,18,5,35,1,33,
23,11,30,16,31,20,
2,19,6,32,3,28,
29,9,25,14,21,15,
8,34,10,27,12,36,
26,7,22,13,24,17

Как всё просто, когда задача решена

[svb]

Nataly-Mak

Цитата:

svb
вы не подскажете, какое разложение 1760 на простые числа последнее в списке, как рекомендует Pavlovsky?

Вот хвостик списка, на нолики не обращайте внимания

(Оффтоп)

181 179 173 167 163 157 151 149 139 137 127 37 0
181 179 173 167 163 157 151 149 139 137 103 61 0
181 179 173 167 163 157 151 149 139 137 97 67 0
181 179 173 167 163 157 151 149 139 131 127 43 0
181 179 173 167 163 157 151 149 139 131 109 61 0
181 179 173 167 163 157 151 149 139 131 103 67 0
181 179 173 167 163 157 151 149 139 131 97 73 0
181 179 173 167 163 157 151 149 139 127 113 61 0
181 179 173 167 163 157 151 149 139 127 107 67 0
181 179 173 167 163 157 151 149 139 127 103 71 0
181 179 173 167 163 157 151 149 139 127 101 73 0
181 179 173 167 163 157 151 149 139 113 109 79 0
181 179 173 167 163 157 151 149 139 109 103 89 0
181 179 173 167 163 157 151 149 139 103 101 97 0
181 179 173 167 163 157 151 149 137 131 113 59 0
181 179 173 167 163 157 151 149 137 131 101 71 0
181 179 173 167 163 157 151 149 137 131 89 83 0
181 179 173 167 163 157 151 149 137 127 109 67 0
181 179 173 167 163 157 151 149 137 127 103 73 0
181 179 173 167 163 157 151 149 137 127 97 79 0
181 179 173 167 163 157 151 149 137 113 107 83 0
181 179 173 167 163 157 151 149 137 113 101 89 0
181 179 173 167 163 157 151 149 131 127 109 73 0
181 179 173 167 163 157 151 149 131 127 103 79 0
181 179 173 167 163 157 151 149 131 113 107 89 0
181 179 173 167 163 157 151 149 131 109 103 97 0
181 179 173 167 163 157 151 149 127 113 103 97 0
181 179 173 167 163 157 151 149 127 109 107 97 0
181 179 173 167 163 157 151 149 127 109 103 101 0
181 179 173 167 163 157 151 139 137 131 109 73 0
181 179 173 167 163 157 151 139 137 131 103 79 0
181 179 173 167 163 157 151 139 137 127 113 73 0
181 179 173 167 163 157 151 139 137 127 107 79 0
181 179 173 167 163 157 151 139 137 127 103 83 0
181 179 173 167 163 157 151 139 137 127 97 89 0
181 179 173 167 163 157 151 139 137 113 103 97 0
181 179 173 167 163 157 151 139 137 109 107 97 0
181 179 173 167 163 157 151 139 137 109 103 101 0
181 179 173 167 163 157 151 139 131 127 113 79 0
181 179 173 167 163 157 151 139 131 127 109 83 0
181 179 173 167 163 157 151 139 131 127 103 89 0
181 179 173 167 163 157 151 139 131 113 109 97 0
181 179 173 167 163 157 151 139 131 109 107 103 0
181 179 173 167 163 157 151 139 127 113 109 101 0
181 179 173 167 163 157 151 139 127 113 107 103 0
181 179 173 167 163 157 151 137 131 113 107 101 0
181 179 173 167 163 157 151 137 127 113 109 103 0
181 179 173 167 163 157 149 139 137 131 113 71 0
181 179 173 167 163 157 149 139 137 131 101 83 0
181 179 173 167 163 157 149 139 137 127 109 79 0
181 179 173 167 163 157 149 139 131 113 107 101 0
181 179 173 167 163 157 149 139 127 113 109 103 0
181 179 173 167 163 157 149 137 131 127 113 83 0
181 179 173 167 163 157 149 137 131 127 107 89 0
181 179 173 167 163 157 149 137 131 113 109 101 0
181 179 173 167 163 157 149 137 131 113 107 103 0
181 179 173 167 163 157 139 137 131 127 109 97 0
181 179 173 167 163 151 149 139 137 131 107 83 0
181 179 173 167 163 151 149 139 137 131 101 89 0
181 179 173 167 163 151 149 139 137 113 107 101 0
181 179 173 167 163 151 149 139 131 127 103 97 0
181 179 173 167 163 151 149 137 131 127 113 89 0
181 179 173 167 163 151 149 137 131 113 109 107 0
181 179 173 167 163 151 139 137 131 127 109 103 0
181 179 173 167 163 149 139 137 131 127 113 101 0
181 179 173 167 157 151 149 139 137 131 113 83 0
181 179 173 167 157 151 149 139 137 131 107 89 0
181 179 173 167 157 151 149 139 137 127 103 97 0
181 179 173 167 157 151 149 139 131 127 109 97 0
181 179 173 167 157 151 149 137 131 127 107 101 0
181 179 173 167 157 149 139 137 131 127 113 107 0
181 179 173 163 157 151 149 139 137 131 127 73 0
181 179 173 163 157 151 149 139 137 131 103 97 0
181 179 173 163 157 151 149 139 137 127 107 97 0
181 179 173 163 157 151 149 139 137 127 103 101 0
181 179 173 163 157 151 149 139 131 127 113 97 0
181 179 173 163 157 151 149 139 131 127 109 101 0
181 179 173 163 157 151 149 139 131 127 107 103 0
181 179 173 163 157 151 149 137 131 127 109 103 0
181 179 173 163 157 151 139 137 131 127 113 109 0
181 179 167 163 157 151 149 139 137 131 127 79 0
181 179 167 163 157 151 149 139 137 131 109 97 0
181 179 167 163 157 151 149 139 137 127 113 97 0
181 179 167 163 157 151 149 139 137 127 109 101 0
181 179 167 163 157 151 149 139 137 127 107 103 0
181 179 167 163 157 151 149 139 131 127 113 103 0
181 179 167 163 157 151 149 139 131 127 109 107 0
181 173 167 163 157 151 149 139 137 131 109 103 0
181 173 167 163 157 151 149 139 137 127 113 103 0
181 173 167 163 157 151 149 139 137 127 109 107 0
181 173 167 163 157 151 149 139 131 127 113 109 0
179 173 167 163 157 151 149 139 137 131 113 101 0

Попробуйте последнюю строчку.

[Nataly-Mak]

svb
спасибо большое за разложения.
Начинаю эксперимент

-- Чт янв 10, 2013 09:26:50 --

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

896/1768 (4,10,8,10,4)
1,2,3,4,7,8,13,15,17,19,21,23
1,2,3,4,7,9,13,15,17,19,21,23
1,2,3,4,7,10,13,15,17,19,21,23
1,2,3,5,7,8,13,15,17,19,21,23
1,2,3,5,7,10,13,15,17,19,21,23
1,2,4,5,7,8,13,15,17,19,21,23
1,2,4,5,7,9,13,15,17,19,21,23
1,2,4,5,7,10,13,15,17,19,21,23

Здесь строки занумерованы числами от 1 до 6, столбцы -- числами от 7 до 12, прямые диагонали (идущие слева вниз) -- числами от 13 до 18, обратные диагонали (идущие слева вверх) -- числами от 19 до 24.

Структура (4,10,9,8,5) означает, что схема имеет 4 элемента веса 4, 10 элементов веса 3, и т.д.

Выбираю первую схему из этого списка.
В естественном разбиении переставляю два числа с весами 3 и 4 - 28 и 36. В результате получаю оценку Q=1760, то есть ту, что собираюсь искать.
Пишу программу полного перебора.
Задаю на входе конкретное разложение 1760 на 12 простых, мне больше понравилась вторая строчка от конца в списке, приведённом svb:

181 173 167 163 157 151 149 139 131 127 113 109

Запускаю программу, 10 зачётных линий выставляются мгновенно! Появление 11-ой зачётной линии - это уже финиш, так как 12-ая зачётная линия получается уже автоматически. Но вот 11-ую зачётную программа пока не нашла, работает, жду, что скажет

Вот решение с 10 правильными выставленными зачётными линиями:

33,20,25,8,32,9,
15,28,6,26,7,31,
34,21,24,x,36,x,
16,35,x,29,x,27,
23,5,22,4,18,2,
10,30,3,19,1,17

Не выставлены две строки - третья и четвёртая, в них неизвестные элементы обозначены крестиком. Не выставлены зачётные линии со значениями 109 и 163, и выставить их в этом примере уже невозможно (из неиспользованных чисел с весом 1).

Программа может и не найти решение для выбранного мной конкретного набора из 12 простых чисел. Как я уже писала в описании предыдущего эксперимента, это разложение можно и не угадать. Следовательно, надо выполнять полный перебор для всех возможных значений зачётных линий, но это будет очень долго.
Может быть, и разбиение выбрано неудачно, а разбиений будет тоже много. Значит, надо проверять их все.

Так вот посмотреть: задача-то получается отнюдь не простенькая. А все нашли решение 1758 и на этом успокоились. Самое сложное и интересное осталось за бортом. Никто не доказал и никто не уверен, что 1758 - максимум для "шестёрки". А вдруг и нет?

[Nataly-Mak]

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

Have you found that N=6 MIN=890 is optimal? I have proved it. Only the sum=888 would be possible. For all possible patterns of 2N lines (up to symmetry) distribute the numbers from 1-N^2 in such a way that the sum on the 2N lines is 888 (you can do this only 4 ways, because the easy bound is 887) a backtracking code checked all possible grids (for each pattern), and found no solution.

It was an interesting case, since the same code would run much-much longer time on the smaller N=5 value, because there we are far from the easy upper/lower bounds.

Gerbicz
а доказательство для N=6, max=1758 у вас есть?
А для N=5, min=502?

[Nataly-Mak]

Эксперимент провела не до конца. Предварительные результаты таковы:

1. При фиксированном наборе из 12 простых легко выставляются 10 зачётных линий, однако дальше этого дело не идёт.
2. При неограниченном наборе простых легко выставляются 11 зачётных линий, но! 12-ая зачётная линия имеет либо не простое значение, либо повторяет одно из первых 11 значений. Так, чтобы все 12 зачётных линий были простые различные числа, пока не получилось.

Программа почему-то выполняется очень долго даже в пункте 1. Может быть, плохо написана (в смысле оптимизации).

Выше я уже показывала решение, в котором две одинаковые зачётные линии (то решение найдено по другой схеме, с теоретической оценкой 1760).
Покажу решение, найденное сейчас, в котором значение 12-ой зачётной линии не простое число (135):



В общем, задача сложная, и решать её надо объединёнными усилиями. А вот с этим у нас всегда было плохо Усилия объединять мы не умеем, у нас все большие индивидуалисты

Кстати, если я правильно поняла перевод сообщения Gerbicz, процитированного чуть выше, он писал, что доказательство оптимальности для минимума "шестёрки" - это был простой счастливый случай. А вот уже для N=5 доказательство оптимальности минимума весьма проблематично (если выполнять его точно таким же образом, как для "шестёрки").

[mertz]

Neil said he was going to try to fix it soon.

Send me an email using the ISS site ( click on my name in any forum post, click contact tab ) and give me an address to email the application.

[Nataly-Mak]

mertz
на этом форуме тоже есть раздел для личных сообщений.
Я сейчас отправила вам личное сообщение.
Вы можете его прочитать, войдя в ваш личный раздел.
В сообшении я указала свой e-mail.

-- Чт янв 10, 2013 21:19:39 --

mertz
Спасибо.
Я получила вашу программу и выложила её на файлообменник narod.ru:
http://narod.ru/disk/65342709001.b2ff43 ... 2.zip.html

Теперь её могут скачать все желающие.
Я уже попробовала запустить программу у себя. Всё нормально. Только работу программы я ещё не опробовала. Для этого мне нужно разобраться с описанием, которое вы выложили на форуме конкурса.

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

[mertz]

Thanks Natalya. I put the link on ISS.

Import one of your solutions. It displays all that has been discussed on this site. The other option is to generate starting grids for the people that did not understand some of the methods.

A little over a week until AZPC factorials contest. Is everyone ready?

[Nataly-Mak]

Пока я вижу это (для введённого решения)



Это хорошая полная информация о конфигурации.

-- Чт янв 10, 2013 22:33:20 --

Теперь вижу это:



Интересная программа!

-- Чт янв 10, 2013 22:59:18 --

И ещё одна картинка
Здорово! Почти максимум для N=10 за несколько секунд.

[mertz]

My method was perturb and hill climb. After the random Fill, the repair routine makes it a valid solution with minimum effort but does not always produce a valid solution. Probably should have took that out.

Let me know of any errors or changes you want.

[whitefox]

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

Каждому такому набору взаимно однозначно соответствует разбиение с нужной оценкой.

Это не верно.

Пример.
Пусть числа $a$ и $b$ имеют вес $v_1$, а числа $c$ и $d$ -- вес $v_2$.
Тогда циклу $(a,c,b,d)$ соответствует тоже самое разбиение, что и произведению циклов $(a,c)(b,d)$.

Таким образом первый мой алгоритм даёт нижнюю границу числа разбиений, а второй -- верхнюю. Для малых $top$ первый алгоритм даёт точное значение.

[svb]

(Оффтоп)

Интересный квадрат