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

[Nataly-Mak]

Не знаю пробовал ли кто-нибудь построение пандиагонального квадрата 7-го порядка по шаблону, предложенному мной выше.
Хочу предложить ещё один шаблон тоже из вычетов по модулю 7:

2 5 3 0 3 6 2
5 2 1 6 4 0 3
0 4 5 2 1 5 4
5 4 0 3 6 2 1
2 1 6 3 0 3 6
3 5 2 1 6 4 0
4 0 4 6 1 1 5

В этом шаблоне присутствует полная группа вычетов по модулю 7 - от 0 до 6.
Поскольку среди простых чисел есть только одно число 7=0(mod 7), то в таком виде шаблон не годится для построения из простых чисел.
Можно сделать так: заменить вычет 0 на любой другой вычет, но только одинаковый; например, везде вычет 0 заменить на вычет 1.
Тогда шаблон вполне годится.
Надо подобрать 6 групп простых чисел, соответствующих вычетам 1 - 6 по модулю 7.
И далее попробовать строить квадрат по этому шаблону.
Я не пробовала, не знаю, что из этого может получиться.

При этом интересно отметить: если мы заменим все вычеты 0 на вычет k (0<k<7), то построенный по такому шаблону квадрат будет иметь магическую константу S=k(mod 7).
Таким образом, по данному шаблону можно строить квадраты с различными магическими константами.

P.S. Преимущество этого шаблона перед тем, что приведён выше, ещё и в том, что в массиве под данный шаблон не будет так много выброшенных простых чисел.

[dmd]

dimkadimon
Думаю, WolframAlpha во многом урезана по сравнению с полной CAS.

[Nataly-Mak]

dimkadimon в сообщении #745832 писал(а):

Пытаюсь найти общую формулу для 3х3:

а1 а2 х3
а4 х5 х6
х7 х8 х9

а1, а2, и а4 независимые, а остальные нет. Ввожу в WolframAlpha вот эти уравнения:

reduce(x3=S-a1-a2, x7=S-a1-a4, x5=S-x3-x7, x6=S-a4-x5, x8=S-a2-x5, x9=S-a1-x5)

Он не понимает. Если убрать последнее уравнение, то все работает. Кто может помочь?

А попробуйте задать такую систему уравнений:

a1+a2+x3=S
a4+x5+x6=S
x7+x8+x9=S
a1+a4+x7=S
a2+x5+x8=S
x3+x6+x9=S
a1+x5+x9=S
x3+x5+x7=S

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

[dimkadimon]

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

А попробуйте задать такую систему уравнений:

Сработало! Даже решила для S. Секрет в том что зависимые должны быть х.

Вы все равно не ответили на мой вопрос: какое количество элементов могут быть зависимы, а какое независимы для любого N?

[Nataly-Mak]

Я тоже попробовала

Задала:

reduce(a1+a2+x3=S, a4+x5+x6=S, x7+x8+x9=S, a1+a4+x7=S, a2+x5+x8=S, x3+x6+x9=S, a1+x5+x9=S, x3+x5+x7=S)

Получено решение:

S = 3/4 (2*a1+a2+a4) 
and x3 = 1/4 (2*a1-a2+3*a4) 
and x5 = 1/4 (2*a1+a2+a4) 
and x6 = 1/2 (2*a1+a2-a4) 
and x7 = 1/4 (2*a1+3*a2-a4) 
and x8 = 1/2 (2*a1-a2+a4) 
and x9 = (a2+a4)/2

Я не знаю ответ на вопрос для всех N.
Вот решите систему линейных уравнений и увидите сами. Не надо заранее озадачиваться этим вопросом: какие зависимые переменные, какие независимые.
Программа решения СЛУ сама с этим разберётся.
Главное - правильно составить СЛУ, когда будете описывать магичность и пандиагональность квадрата.

-- Вс июл 14, 2013 17:27:53 --

Проверила формулу для наименьшего магического квадрата 3-го порядка из простых чисел:

17 89 71
113 59 5
47 29 101

Имеем:
a1=17, a2=89, a4=113

Решение по формуле:

S=177
x3=71
x5=59
x6=5
x7=47
x8=29
x9=101

Всё верно.

[Nataly-Mak]

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 14 Jul 2013 10:54
2 7.49 Dmitry Kamenetsky Adelaide, Australia 12 Jul 2013 00:11
3 7.37 Wes Sampson La Jolla, California, United States 13 Jul 2013 01:27
4 6.36 Dmitry Ezhov Sterlitamak, Russia 14 Jul 2013 21:09
5 6.10 Valery Pavlovsky Ekaterinburg, Russia 22 Jun 2013 20:28

А ведь результат 6.10 был в самом начале 12. Почти в два раза улучшено!

У dimkadimon +1.39, тоже неплохо. Пока он в отрыве от Wes на 0.12 балла.
Что-то начинает получаться у dmd.

Все остальные конкурсанты пока не осиливают задачу. Похоже, она не из лёгких. Вот вам и квадраты, господа

[Pavlovsky]

dimkadimon в сообщении #745870 писал(а):

какое количество элементов могут быть зависимы, а какое независимы для любого N?

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Для p=7 получаем 49-24=25 независимых переменных.


-- Пн июл 15, 2013 08:35:51 --

dimkadimon в сообщении #745677 писал(а):

Pavlovsky, a почему вы думаете что это решение близко к минимальному? Ведь магический квадрат этого размера имеет S=2470.

Наверно немного погорячился, сделав такое заявление. Это утверждение верно, если составлять квадрат порядка 10 из 4-х пандиагональных квадратов 5х5.
По Россеру, квадрат порядка 10 можно разбить на 4 множества чисел, которые будут иметь одинаковую сумму. Но не откуда не следует, что эти группы чисел должны составлять пандиагональный квадрат 5х5.

[Nataly-Mak]

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

Написала программу построения пандиагонального квадрата 7-го порядка по общей формуле и по шаблону (общую формулу см. выше).

Шаблон выбран такой (из вычетов по модулю 7):

4 6 3 5 3 5 3 
3 5 3 4 6 3 5
6 3 5 3 5 3 4
5 3 4 6 3 5 3
3 5 3 5 3 4 6
3 4 6 3 5 3 5
5 3 5 3 4 6 3

Массив простых чисел под этот шаблон (ровно из 49 чисел):
...

Дальше такая идея: добавить в каждую группу ещё немножко чисел соответствующего вида.
Будет больше шансов, что квадрат построится.

Попробовала реализовать эту идею.
Добавила во все 4 группы новые числа соответствующего вида:

Группа 1 – числа вида $7k+3$ (на картинке белые ячейки):

3 17 31 59 73 101 157
199 227 241 269 283 311 353
367 409 479 521 563 577 619
647 661 773 787 829 941 983

Группа 2 – числа вида $7k+4$ (голубые ячейки):

11 53 67 109 137 151 179
641 683 739 809 823 907 977 991

Группа 3 – числа вида $7k+5$ (сиреневые ячейки):

5 19 47 61 89 103 131
173 229 257 271 313 383 397
677 691 719 733 761 859 887 929 971

Группа 4 – числа вида $7k+6$ (розовые ячейки):

13 41 83 97 139 167 223
643 727 769 797 811 839 853 881 937

Пришлось немного увеличить и магическую константу, теперь S=1429.
По-прежнему пока в программе перебор 23 свободных переменных и поиск зависимых от них элементов.
Программа работала несколько часов, но 41 элемент нашла (см. картинку).
Остался не задействованным один свободный элемент и 7 элементов уже вычисляются.

[Nataly-Mak]

Jarek снова на месте

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 16 Jul 2013 04:46

От 12 баллов осталось всего 6.07.

Я уже перевела 4 отрывка из этой темы (перевожу наиболее важные сообщения).
Пока в дискуссионной группе Al выложил только 3.
Надеюсь, это хоть как-то поможет тем, кто не читает по-русски.
Не знаю, насколько читабельны переводы. Я не делаю обратный перевод, так как фрагменты довольно большие, неудобно переводить. Как там Google напереводил?

-- Вт июл 16, 2013 15:32:55 --

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

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

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

Покажу пример. Это пандиагональный квадрат 10-го порядка из произвольных натуральных чисел.



Магическая константа квадрата S=17130.
Те четыре группы чисел, о которых говорится в цитате, расположены по решёткам Россера. На картинке окрашена одна из решёток в голубой цвет.
Сумма чисел в этой решётке (а также и в остальных трёх решётках) равна $5S/2=42825$.

Схема такая: задаём магическую константу S будущего пандиагонального квадрата, выбираем массив простых чисел под эту константу, в этом массиве мы должны иметь четыре группы, сумма чисел в которых равна 5S/2.

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

Я так поняла процитированное свойство.

[Pavlovsky]

Правильно поняли. Правда как использовать это свойство не понятно. Проще найти 100 чисел которые можно разбить на 10 групп по 10 чисел с одинаковой суммой. Чем искать 100 чисел которые можно разбить на 4 группы по 25 чисел в каждой.

Допустим нашли мы 4 группы по 25 чисел. Как из них строить квадрат 10х10?? Добавление условия, что каждая группа из 25 чисел образует квадрат 5х5, делает построение квадрата 10х10 элементарной операцией.

[Nataly-Mak]

В одной из тем на ПЕН (не помню, в какой) я приводила пример построения пандиагонального квадрата 6-го порядка по решёткам (4 решётки по 9 чисел).
Алгоритм этот для порядка 6 работает классно. Вся задача как раз в том, как найти все разбиения массива на 4 группы по 9 чисел так, что суммы чисел в каждой группе одинаковы.

Перебор же по этим 4 решёткам выполняется секунды!!

Конечно, 4 решётки по 25 чисел - это не 4 решётки по 9 чисел. Понятное дело.
Но попытаться можно.

[Pavlovsky]

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

Но попытаться можно.

Попытка не пытка. Правда товарищ Берия? Я уже почти месяц пробую разлиные подходы. Результат пока нулевой.

[Nataly-Mak]

А для квадрата порядка 8 будет 4 решётки всего по 16 чисел.
16 чисел - это не 25
Как я уже сказала, перебор по 4 решёткам из 9 чисел выполняется очень быстро.

Но всё это вокруг и около алгоритмов Россера. Надо оторваться от этих алгоритмов.
Почти уверена, что Jarek использует какой-то совсем другой алгоритм. Такие улучшения получены!
Ну, вот никак не могу догадаться, что у него за алгоритм такой

-- Ср июл 17, 2013 07:48:39 --

Нашла тему на ПЕН, где рассматривается алгоритм построения пандиагонального квадрата 6-го порядка по 4-м решёткам из 9 чисел:
http://e-science.ru/forum/index.php?showtopic=30821

[Nataly-Mak]

Надо решить систему уравнений. Кто может помочь?
У меня в Вольфраме система не умещается в строке для ввода (может быть, это можно как-то обойти?).

Вот система уравнений:

x1-x7-x14+x16-x21-x28+x23+x30=0
x2-x6+x9-x13-x20+x24-x27+x31=0
x3-x5+x10-x12+x17-x19-x26+x32=0
-x2+x8+x9-x11+x18-x20+x27-x29=0
-x3+x7-x12+x16+x17-x21+x26-x30=0
-x4+x6-x13+x15-x22+x24+x25-x31=0
x1-x2+x3-x4-x5+x6-x7+x8=0
x1-x8-x9+x16+x17-x24-x25+x32=0

8 уравнений, 32 неизвестных.

[dmd]

x16 = -x17 - x2 + x24 + x25 + x3 - x32 - x4 - x5 + x6 - x7 + 2 x8 + x9
x15 = x2 - x20 + x22 - x25 - x27 + 2 x31 + x4 - 2 x6 + x9
x14 = -x17 - x21 + x23 + x24 + x25 - x28 + x30 - x32 - x7 + x8 + x9
x13 = x2 - x20 + x24 - x27 + x31 - x6 + x9
x12 = -x2 - x21 + x24 + x25 + x26 - x30 - x32 - x4 - x5 + x6 + 2 x8 + x9
x11 = x18 - x2 - x20 + x27 - x29 + x8 + x9
x10 = -x17 + x19 - x2 - x21 + x24 + x25 + 2 x26 - x3 - x30 - 2 x32 - x4 + x6 + 2 x8 + x9
x1 = x2 - x3 + x4 + x5 - x6 + x7 - x8