Дьявольские магические квадраты из простых чисел

[Nataly-Mak]

Дык вот моя-то ссылка была на последнюю задачу, а ваша ссылка на задачу появилась только что (и это, конечно, другая задача).
А я назвала не только тему, а дала ссылку на конкретную задачу, которая была рассмотрена последней.
В этой теме много переборных задач. И многие из них относятся к пандиагональным квадратам.
Так что, вам надо было с самого начала указать и тему, и задачу.

Ладно, проехали.

Вернёмся к этой теме.
Вы пишете, что теретически можно доказать, что $c>4$.
Трудно мне сейчас представить, что вы имеете в виду и что доказываете, ибо не знаю точного определения $c$.
Вы пишете, что это число наборов, удовлетвояющих условию пандиагональности.
Что это за "условие пандиагональности"? Решётки Россера?

И дальше приводите наборы с $c<4$. Это что за наборы?

[svb]

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

Вы пишете, что теретически можно доказать, что $c>4$.
Трудно мне сейчас представить, что вы имеете в виду и что доказываете, ибо не знаю точного определения $c$.

Вы пишете, что это число наборов, удовлетвояющих условию пандиагональности.
Что это за "условие пандиагональности"? Решётки Россера?

1. Разбиение набора на 9 групп с одинаковыми суммами.
2. Проверка выстраивания строк с магической суммой для каждого такого разбиения.

Проверки вертикалей и диагоналей нет.

Цитата:

И дальше приводите наборы с $c<4$. Это что за наборы?

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

Для более точной оценки минимума $c$ требуется достаточно глубокий анализ, которого у меня нет. Любое рассматриваемое разбиение отсортировано внутри групп. Группы тоже отсортированы по минимальным элементам каждой группы. Самый маленький элемент расположен в первой группе и в первой строке. Этот элемент может входить в строку, вертикаль и две диагонали. Это уже дает 4 варианта, но эта оценка явно сильно занижена, что подтверждает и практическая проверка.

-- Сб дек 13, 2014 09:36:15 --

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

[svb]

Цитата:

Более точный анализ может показать, что я ошибся.

Что и произошло. Проверка строк была проведена с ошибкой. С одной стороны, это должно меня расстраивать - ошибки неприятно совершать. Но, с другой стороны, общие соображения были правильными и, к тому же, появился шанс найти квадрат.

Дополнительно хочу заметить, что для отсеивания вариантов хотелось бы использовать решетки $L(2)$. Их 4 и суммы элементов в них одинаковые.

До последнего момента мне не нравилось использование проверки строк, есть в этом что-то некрасивое.Любителей практических результатов прошу меня извинить за поспешность.

[Nataly-Mak]

Вчера проверила массив, подающий большие надежды (из приведённых svb)

0 6 12 16 22 28 30 40 42 46 48 60 72 76 78 82 88 90 100 106 112 118 120 126 130 132 142 156 160 162 166 180 186 196 198 202

Вообще-то, я его конечно, проверяла и раньше, когда только начинала поиск второго квадрата.
Программа svb проверяла этот массив почти 7 часов!!

Summa=588
Time: 24546.88 sec

Судя по информации, выведенной на экран, существует решение всего с 2 дырками (34 элемента найдены).
Причём находится это решение на первых минутах поиска.
Жалко, что само это решение не выводится программой. Было бы очень интересно посмотреть на решение с 2 дырками!

Написала на скорую руку программу построения по общей формуле, которая приведена чуть выше. Никаких оптимизаций, не использовала отклонения, только общая формула и больше ничего. В программе 15 свободных переменных из 35, перебор огромный, выполнить полностью - надо сутками крутить программу.
Но часа за 2 нашлось решение с 4 дырками:

0 132 72 180 6 198
118 60 112 156* -30* 172*
156 12 196 16 186 22
166 76 82 46 178* 40
28 202 78 90 160 30
120 106 48 100 88 126

$S=588$

Плохое приближение, есть даже отрицательное число (такой перекос в структуре квадрата). Число 156 правильное, но повторено.
Однако, на фоне построения пандиагонального квадрата 5-го порядка из последовательных простых чисел (в котором не могли до сих пор сложить даже 4 полных строки) пандиагональные квадраты 6-го порядка выглядят намного успешнее (недаром и первый квадрат уже давно найден).
Как уже сказала, для данного потенциального массива существует решение с 2 дырками.
Это уже очень близкое приближение! И крайнее, - в том смысле, что решения с одной дыркой в этой задаче быть не может: если встанет на место 35-ый элемент, автоматически встанет на место и 36-ой.

Вот такие эксперименты.
И какой поразительный контраст: потенциальные массивы, которые проверялись у меня в последнее время, проверяются за несколько секунд (самое большее - 10 минут). А тут - почти 7 часов! Программа проверки одна и та же, компьютер один и тот же.

-- Вс дек 14, 2014 08:13:20 --

Проделала интересный эксперимент.
Очень интересно посмотреть на решение с 2 дырками!
Делаю следующее: расширяю исходный массив, добавляя к нему 14 чисел:

0 6 12 16 22 28 30 40 42 46 48 60 72 76 78 82 88 90 100 106 112 118 120 126 130 132 142 156 160 162 166 180 186 196 198 202
34 36 54 58 66 94 98 136 148 152 172 178 188 192 

Запускаю программу поиска квадратов, и... квадраты посыпались, как из рога изобилия

1:
 188 198  28  16 136  22
  40  48 166 178  90  66
 196  78   6  94  88 126
  36  58 180 152   0 162
  98 172  60  76  82 100
  30  34 148  72 192 112
Time: 2.59 sec
2:
 188 198  28  16 136  22
  30  40 202 100  98 118
  78 120  60  46 112 172
  36  58 186 152   0 156
 180 160   6  82  94  66
  76  12 106 192 148  54
Time: 2.61 sec
3:
 188 198  28  16 136  22
  12 130  94 120 166  66
 142  78  72  76  88 132
  36  58 186 152   0 156
 162  90  60  98   6 172
  48  34 148 126 192  40
Time: 2.62 sec
4:
 188 198  28  16 136  22
  76 100  78 130 132  72
  98 106  66 118  88 112
  36  58 162 152   0 180
 156 120  82  30  40 160
  34   6 172 142 192  42
Time: 2.70 sec
5:
 188 198  28  16 136  22
  34  54 178 142 132  48
 156  66  82  30  94 160
  36  58 162 152   0 180
  98 166  60 118  40 106
  76  46  78 130 186  72
Time: 2.72 sec
6:
 188 198  22  16  46 118
  40  12 196 172 162   6
 178  90  30  88  76 126
  36 148  66 152   0 186
  98 106 132  82 112  58
  48  34 142  78 192  94
Time: 3.53 sec
. . . . . . . . 

За 5 секунд нашлёпалось море квадратов!
Кстати, имеем модели массивов из 36 последовательных простых чисел. И таких шаблонов можно сделать сотни. Только вот найти хотя бы один массив, соответствующий этим шаблонам, никак не получается

Ах да, теперь надо из этого моря решений выудить решение с 2 дырками.
Можно попробовать уменьшить расширение массива, добавить не 14 чисел, а меньше.

[Nataly-Mak]

Выудить решение с 2 дырками оказалось не так просто.
Вот оно:

16 120 118 48 196 90
76 142 160 82 22 106
162 94* 6 88 198 40
126 46 72 202 30 112
78 186 66* 156 42 60
130 0 166 12 100 180

$S=588$

Вместо нужных чисел из массива 28 и 132 в решении присутствуют числа 66 и 94.
Если бы нашёлся такой нормализованный массив из 36 последовательных простых чисел:

0  6  12  16  22  30  40  42  46  48  60  66  72  76  78  82  88  90  94  100  106  112  118  120  126  130  142  156  160  162  166  180  186  196  198  202

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

Итак, есть приближение к решению с 2 дырками. Крайнее приближение: лучшего - с одной дыркой - быть уже не может. Однако до самого решения пока как до неба.

[12d3]

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

1. Разбиение набора на 9 групп с одинаковыми суммами.

Долго ли работает это разбиение и сколько получается разбиений примерно?

[Nataly-Mak]

12d3
пока не пришёл svb с ответом на ваш вопрос...
Вы помните программу, которую давно делали для построения обычного магического квадрата 6-го порядка из заданного массива, состоящего из 36 чисел?
Замечательная программа! Она у меня и сейчас сохранилась. Работает! Решения находит мгновенно, если они существуют. Правда, когда не существуют, полная проверка идёт долго. Ну, это вполне понятно. Так всегда.

Вот бы вам чуточку эту программу изменить с учётом пандиагональности квадрата.

[12d3]

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

Вот бы вам чуточку эту программу изменить с учётом пандиагональности квадрата.

По программе svb быстрее выйдет. Мне собственно, после разглядывания решения системы пришла в голову идея делить на 9 наборов. Потом пролистал тему и увидел, что я не оригинален.

[Nataly-Mak]

Да работает программа svb вполне прилично, но... старая программа проверяет по одному массиву.
А новой хорошей программы пока нет.
svb взялся модифицировать алгоритм проверки на предмет построения квадрата, а я просила его модифицировать только ввод массивов для проверки.

[svb]

12d3 в сообщении #946809 писал(а):

Долго ли работает это разбиение и сколько получается разбиений примерно?

Вполне терпимо - зависит от конкретного набора 36 чисел (часто 0, для единственного известного квадрата меньше 2000000). Алгоритм примитивный:

procedure permq(x:word);
var i,j,k,m:word;
    q1,q2,q3:qword;
begin
  if (x=37) then  begin
    inc(c);
    exit;
  end;
  for i:=x+1 to 34 do for j:=i+1 to 35 do for k:=j+1 to 36 do begin
    sb:=p[x]+p[i]+p[j]+p[k];
    if sb>2*Sc then break;
    if sb=2*Sc then begin
      q1:=p[i];q2:=p[j];q3:=p[k];
      for m:=k downto j+2 do p[m]:=p[m-1];
      for m:=j+1 downto i+3 do p[m]:=p[m-2];
      for m:=i+2 downto x+4 do p[m]:=p[m-3];
      p[x+1]:=q1;p[x+2]:=q2;p[x+3]:=q3;
      if ver(x+3) then permq(x+4);
      for m:=x+1 to i-1 do p[m]:=p[m+3];p[i]:=q1;
      for m:=i+1 to j-1 do p[m]:=p[m+2];p[j]:=q2;
      for m:=j+1 to k-1 do p[m]:=p[m+1];p[k]:=q3;
    end;
  end;
end;

Начальный массив $p[1..36]$ отсортирован по возрастанию. Отсев идет с помощью функции $ver()$ (проверка $ver(y)$ идет при $y\bmod 12 = 0$). Запуск перебора $permq(1)$. Без отсева время работы точно не замерял - секунда, две.
Без ограничения общности можно считать, что первые две группы по 4 элемента (p[1]<p[5]<p[13]) такого перебора принадлежат одной строке/вертикали/диагонали. Третью группу нужно подбирать, еще умножаем на 7. Это, если проверять возможность выборки 6 элементов с магической суммой из 3-х групп по 4.

С получением 9 групп проблем нет. Различных 4-ок не так уж много. Далее есть над чем подумать. Прежде всего, для каждой группы всего 3 положительных отклонения от комплементарности, а среди 9 отклонений всего 4 независимых. Мне кажется, этот подход для отсева эффективнее, но нужно проверять.

[svb]

Предложенный перебор годится для получение всех 9-ок, но далее необходимо рассматривать $C_5^2 = 10$ выборок 2-х групп по 4 элемента (светлые кружочки)
$\left( { \bullet \bullet \bullet } \right)\left( { \bullet \circ \circ } \right)\left( { \circ \circ \circ } \right)$
для проверки на магичность строк. Здесь мне пока не ясно, как лучше сделать, чтобы отсеивать раньше. Получается, что все же нужен массив всех 4-к, получаемый при генерации 9-ок.

[svb]

Маленькое замечание по отсеву наборов из 36 чисел.
Если число четных (и число нечетных) чисел в наборе не делится на 4, то из такого набора нельзя составить пандиагональный квадрат.

[Nataly-Mak]

И снова
дьявольские магические квадраты из простых чисел!

Теперь это не просто пандиагональные квадраты, но ещё и обладающие свойством ассоциативности.
Итак, конкурс стартовал:
http://primesmagicgames.altervista.org/wp/competitions/

Дорогие коллеги! Уважаемые форумчане и гости форума!
Приглашаю принять участие в конкурсе.

Чтобы не создавать новую тему, предлагаю здесь обсуждать задачу конкурса.

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

Пожалуйста, задавайте ваши вопросы, предлагайте ваши идеи и алгоритмы.
Разрешается выкладывать всё, кроме готовых решений.

Я уже начала разбираться с состоянием дел в этой области квадратостроения
В теме "Магические квадраты" смотрите с этого поста:
post977181.html#p977181

Пока мало что имеем в наличии, для $n=10$ нет ни одного решения.
В конкурсе требуется найти решения до порядка $n=16$ включительно.

Небольшое пояснение к правилам конкурса. В правилах написано следующее:

Цитата:

Known solutions:

n = 7, S = 4613 (author N. Makarova)
n = 8, S = 2640 (author N. Makarova)
n = 9, S = 24237 (author A. Chernov)

Contestant shall not be deemed a winner, if he would submit only solutions with known magic constants

Здесь уточняю: разумеется, победителем не будут признаны те участники, которые представят решения только с известными магическими константами и/или с магическими константами больше известных и только для данных порядков.
Это существенное дополнение. Собственно, это я и имела в виду, но ice00 не совсем меня понял.
Языковой барьер

[jcmeyrignac]

Why don't you announce it on primepuzzles.net ?

[Nataly-Mak]

jcmeyrignac в сообщении #981460 писал(а):

Why don't you announce it on primepuzzles.net ?

Планируется головоломка # 777 на этой неделе.