Магические квадраты

[Nataly-Mak]

Завершила статью "Наименьшие магические квадраты из чисел Смита".
Напомню, что в данной серии магических квадратов не найдены квадраты порядков 7 - 9. Я построила квадраты до порядка 35 включительно.
Можно продолжить дальше, программы ice00 сделал уже до порядка 64.
Но надо что-то придумывать для квадратов порядков 7 - 9. Досадный пробел в этой серии магических квадратов!
Ещё раз повторю просьбу ко всем, кто интересуется темой: желательно проверить найденные мной минимальные магические константы. Возможны их улучшения в смысле уменьшения (моя программа не даёт точного результата).
***
Реализовала приведённую выше схему для идеальных квадратов 5-го порядка для случая традиционных магических квадратов. Программа работает, но очень долго. Для случая нетрадиционных магических квадратов тоже очень просто написать программу, но на Бейсике писать нет смысла.

[Ираклий]

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

не найдены квадраты порядков 7 - 9

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

[Nataly-Mak]

Нет, я не пробовала строить МК в другой системе счисления. Мне кажется, что от смены системы счисления аддитивные свойства смитов не улучшатся. Если, например, набор из $n$ смитов не даёт нужной суммы в десятичной системе, то он не будет её давать в любой другой системе счисления.

[Someone]

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

Мне кажется, что от смены системы счисления аддитивные свойства смитов не улучшатся. Если, например, набор из $n$ смитов не даёт нужной суммы в десятичной системе, то он не будет её давать в любой другой системе счисления.

Но сами смиты станут другими. Однако задачи о составлении магических квадратов из смитов в различных системах счисления следует считать различными задачами и не смешивать их решения в одну кучу.

[Nataly-Mak]

Someone в сообщении #264426 писал(а):

Но сами смиты станут другими.

Да, я предполагала такой смысл в предложении Ираклия. Но тогда надо будет построить для таких смитов (в другой системе счисления) уже построенные в десятичной системе магические квадраты порядков 3 - 6 и 10 - 35. Не стоит овчинка выделки!

[Nataly-Mak]

Продолжаю тему построения нетрадиционных идеальных квадратов 5-го порядка.
Понятно, что идеальный квадрат легко построить из членов арифметической прогрессии длины 25. Из простых чисел такие арифметические прогрессии есть, и идеальный квадрат мной уже построен. Вот он:

6171054912832631 7969283390638391 6906693835571351 7233644467899671 7478857442145911
7315382125981751 7642332758310071 6252792570914711 7805808074474231 6743218519407191
7887545732556311 6579743203243031 7151906809817591 7724070416392151 6416267887078871
7560595100227991 6498005545160951 8051021048720471 6661480861325111 6988431493653431
6824956177489271 7070169151735511 7397119784063831 6334530228996791 8132758706802551

Но для смитов у нас нет пока арифметической прогрессии длиной 25. Оказывается для построения идеального квадрата 5-го порядка достаточно иметь пять арифметических прогрессий длины 5 с одинаковой разностью, но эти прогрессии должны удовлетворять одному условию. Обозначим a_i первый член i-ой прогрессии.
Условие таково: a_1 + a_2 = a_3 + a_5 = 2*a_4.
Так, арифметическая прогрессия длины 25, из которой составлен показанный выше идеальный квадрат, может быть разбита на 5 арифметических прогрессий так, что:
a_1 = 6171054912832631, a_2 = 7805808074474231, a_3 = 6579743203243031, a_4 = 6988431493653431, a_5 = 7397119784063831.
Указанное условие здесь выполняется.
Приведу более наглядный пример из обычных натуральных чисел. Возьмём пять таких арифметических прогрессий с разностью 5:

3, 8, 13, 18, 23
5, 10, 15, 20, 25
1, 6, 11, 16, 21
4, 9, 14, 19, 24
7, 12, 17, 22, 27

Здесь a_1 = 3, a_2 = 5, a_3 = 1, a_4 = 4, a_5 = 7. Очевидно, что указанное выше условие выполняется. Обратите внимание, что числа этих пяти прогрессий не составляют сплошную прогрессию длины 25 (как это было в первом примере); это пять отдельных прогрессий с одинаковой разностью. Вот идеальный магический квадрат, построенный из чисел этих прогрессий:

3 15 21 19 12
24 22 8 5 11
10 1 14 27 18
17 23 20 6 4
16 9 7 13 25

Я уже попыталась найти пять таких арифметических прогрессий из простых чисел. Но, увы! У меня массив простых чисел в интервале от 1 до 25000. В этом интервале я нашла 37 арифметических прогрессий с разностью 30. Но среди этих прогрессий нашлись только три прогрессии, удовлетворяющие нужному условию:

107 137 167 197 227
2879 2909 2939 2969 2999
1493 1523 1553 1583 1613

Здесь a_1 = 107, a_2 = 2879, a_4 = 1493.
Из этих трёх прогрессий я составила идеальный квадрат, но, понятно, что числа в нём повторяются (в качестве третьей и пятой прогрессий я взяла опять первую и вторую):

107 2939 227 1583 2909
1613 2969 137 2879 167
2909 107 1553 2999 197
2939 227 2969 137 1493
197 1523 2879 167 2999

Из смитов тоже попробовала искать такие арифметические прогрессии. У меня есть несколько арифметических прогрессий длины 5, которые любезно выложил на форуме Портала ЕН пользователь 12d3. Но пока мне не удалось найти нужные прогрессии. Три прогрессии (аналогично приведённому примеру для простых чисел) тоже есть, а вот пять прогрессий не находится.
Замечу, что из смитов пока нет ни одного идеального квадрата 5-го порядка (как, впрочем, и других порядков).

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

[Nataly-Mak]

Да, товарищи! Светлые праздники помощи здесь случаются крайне редко. Вот 12d3 помог с квадратами порядков 5 и 6 из смитов и исчез. А с квадратами порядков 7 – 9 никто уже не хочет помочь. Говорят: помогают тому, кто сам везёт. Это, наверное, не про меня. Или я сама не везу что ли?
На одном форуме меня назвали МРК. Расшифровывать аббревиатуру не буду, догадайтесь сами

МРК в отчаянии: наименьшие магические квадраты порядка 9 не строятся ни из последовательных, ни из произвольных смитов.
Вчера занималась квадратом порядка 9 из последовательных смитов. Наименьший кандидат в такой квадрат составляется из массива: 27, 58, …, 2038, 2067. Магическая константа равна $9179$.

Сначала сгенерировала по своей программе 140 полумагических квадратов таких, что магической суммы нет только в одной диагонали. Квадраты генерировала из 10 различных наборов из 9 строк. Вот пример такого полумагического квадрата:

166  1284  922  535  1633  861  1795  728  1255 
 1678  1755  729  2038  562  648  346  438  985 
 265  576  627  378  1962  654  1219  1626  1872 
 454  27  1449  958  666  1894  663  1903  1165 
 706  762  391  634  1642  319  1952  1921  852 
 1736  1908  1966  645  85  1086  915  202  636 
 1507  1858  778  1581  690  1376  913  355  121 
 1842  483  1935  1822  58  274  94  895  1776 
 825  526  382  588  1881  2067  1282  1111  517

Далее обработала все эти полумагические квадраты по программе ice00 (pms_diag9_). Ничего! Метод c3 возвращает такие же полумагические квадраты с магической суммой в одной диагонали; другие методы вообще не понимаю, что там делают, например, портятся строки и столбцы квадрата, но делаются правильными диагонали.
Затем сделала свою программу так, что она генерирует из тех же 10 наборов строк тысячи полумагических квадратов (уже не стала делать сумму в одной диагонали, в обеих диагоналях нет магической суммы). Пропускаю первую порцию – 1440 полумагических квадратов – через программу ice00. Ничего! Пропускаю вторую такую же порцию, снова ничего. Я в полной растерянности! Надо ли считать результаты этих экспериментов признаком того, что магический квадрат из данного массива смитов не существует? Мне кажется, что такой вывод нельзя делать. А что вы скажете, уважаемые коллеги?

У меня конкретный вопрос к ice00: какими способами вы пользуетесь для того, чтобы сделать в полумагическом квадрате диагонали?
Я, например, в своей программе пользуюсь для этой цели только перестановкой строк (для маленьких порядков - перестановкой строк и столбцов). Понятно, что при таком способе суммы чисел в строках (столбцах) квадрата сохраняются. У вас же в некоторых случаях эти суммы нарушаются. Не могли бы вы подробно объяснить, что делаете с числами в квадрате в таких случаях? Может быть, ваши методы натолкнут меня на какие-нибудь идеи.
И заодно второй вопрос: как у вас идут дела с реализацией моего алгоритма? Вы его ещё не забросили? Есть ли надежда, что он будет реализован?

И наконец нелицеприятный вопрос ко всем участникам: неужели здесь нет квалифицированных программистов, которые могли бы реализовать предложенный мной алгоритм построения нетрадиционных магических квадратов порядков 5, 6, 7, 8, 9 из смитов? Насколько я поняла из сообщения ice00, алгоритм вполне пригоден для реализации. Что же: из всех желающих его реализовать у нас есть только один ice00? Печальный факт!

[ice00]

QUOTE]
У меня конкретный вопрос к ice00: какими способами вы пользуетесь для того, чтобы сделать в полумагическом квадрате диагонали?
Я, например, в своей программе пользуюсь для этой цели только перестановкой строк (для маленьких порядков - перестановкой строк и столбцов). Понятно, что при таком способе суммы чисел в строках (столбцах) квадрата сохраняются. У вас же в некоторых случаях эти суммы нарушаются. Не могли бы вы подробно объяснить, что делаете с числами в квадрате в таких случаях? Может быть, ваши методы натолкнут меня на какие-нибудь идеи.
[/QUOTE]

Here the algorithm for making diagonal magic for each method of solution:

$DIAGONAL1$ used in $A1$, $A2$, $A3$, $B1$, $B2$, $B3$
$DIAGONAL2$ used in $C1$, $C2$, $C3$
$DIAGONAL3$ used in $C3$ if time-out is enabled (it is a $DIAGONAL2$ that goes for a limited period of time, then exit without solution)
$DIAGONAL4$ used in $D1$, $D2$, $D3$, $D4$

$DIAGONAL1$:
it makes the two diagonals magic in the same time by using two rows that are already magic (and let all the other part of magic square to be not magic after this process).

It is different for odd or even orders:

$EVEN$:
The first row (that is to be magic) is copied onto the diagonal \, then the last row (that is to be magic) is copied to the diagonal /.
Diagonals are now magic, while all the other are not more magic (but then the algorithm that comes after goes again to make all rows and columns magic without toach the diagonals).

$ODD$:
The same idea of even order, but now we copy the half row to the diagonal \ and the half column to diagonal / (all row and column where take this values are to be magic).


$DIAGONAL2$:
Makes the diagonal \ magic and see if diagonal / become magic, or repeat forever (e.g to the end of loop)
This is a recursive algorithms that calculate all the permutation of the number of row for the given order
For example:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
..
4 3 2 1

That it goes to change the rows position (that did not change the magic state of all unless the diagonals), until it make the diagonal \ magic. Now it look if diagonal / is magic and if not, it goes again with another permutation.


$DIAGONAL4$:
this is a little more complicated as it uses to do two passate of permutation with two different algorthm:

In the fist it make diagonal / magic using the same algorithm of $DIAGONAL2$, but then when find the column \ magic it stops and passes to the second phase.
Here it goes to permutation all the rows for making diagonal / magic without changing the magic state of column \, but changing not row position, but a single value of a cell in that position.


I think that "Google Translate" will translate this not so good as this is very technical argument, however into the source is more easy to look at the implementation for the people that know c++ language.

Цитата:

И заодно второй вопрос: как у вас идут дела с реализацией моего алгоритма? Вы его ещё не забросили? Есть ли надежда, что он будет реализован?

I'm implementing it (started the last weekend as conversion to object oriented implementation of all programs was done).
Due to order 6 alreay completed, the algoritms must be able to goes to upper orders and I have some ideas for extending this, but before I want to have the program implemented and working until the reach of that point.

[Nataly-Mak]

Да, ice00, вы правы: перевод плохо понятен. Ну, может быть, будет польза тому, кто знает язык С++
Более того, я даже ответ на второй вопрос не поняла. Вы хотите сказать, что программа для построения квадратов порядка 6 из смитов уже не актуальна и поэтому вы будете делать программы для следующих порядков? Это логично.

[Nataly-Mak]

У меня тут просили общую алгебраическую формулу магического квадрата 5-го порядка. Я давала общую схему из книги Ю. В. Чебракова. Напомню, что в формуле, приведённой в указанной книге, 15 свободно варьируемых переменных. Мне удалось сделать общую схему так, что свободных переменных всего 14 (каждая из них пробегает значения от 1 до 25, так же и по формуле из книги). Не буду здесь подробно излагать свою схему. Готовлю статью об общих формулах магических квадратов порядков 3, 4 и 5.
Я уже реализовала свою схему построения нетрадиционного магического квадрата 5-го порядка (на QBASIC). Понятно, что схема пригодна и для построения традиционных магических квадратов 5-го порядка (просто в качестве исходного массива в этом случае надо ввести первые 25 натуральных чисел).
Протестировала свою программу сначала на традиционных магических квадратах, а затем на нетрадиционных. Так как в полном объёме моя программа будет выполняться очень долго, я сделала так: искусственно зафиксировала 7 переменных, остальные 7 переменных пробегают все значения от 1 до 25, как и положено. В таком случае программа довольно быстро выполняется (примерно 5 минут) и выдаёт правильные результаты. Например, для традиционных магических квадратов программа выдаёт такие решения (зафиксированы переменные 1, 23, 10, 17, 21, 13, 9):

 1  23  10  14  17 
 8  15  19  21  2 
 25  4  13  7  16 
 22  5  20  12  6 
 9  18  3  11  24 

 1  23  10  14  17 
 15  19  2  21  8 
 22  6  13  20  4 
 18  5  24  7  11 
 9  12  16  3  25 

 1  23  10  14  17 
 15  19  2  21  8 
 16  12  13  20  4 
 24  5  18  7  11 
 9  6  22  3  25 

 1  23  10  14  17 
 15  19  6  21  4 
 22  2  13  20  8 
 18  5  24  7  11 
 9  16  12  3  25 

 1  23  10  14  17 
 20  18  4  21  2 
 11  7  13  19  15 
 24  5  22  8  6 
 9  12  16  3  25 

А для нетрадиционных магических квадратов получается такое решение (исходный массив – простые числа от 13 до 113):

79  13  71  37  113 
 59  41  83  23  107 
 31  109  73  53  47 
 101  61  19  103  29 
 43  89  67  97  17

Здесь зафиксированы те же самые (по расположению) переменные: 79, 13, 71, 113, 23, 73, 43.

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

Очень интересен вопрос, как долго программа будет выполняться при построении всех традиционных магических квадратов 5-го порядка. Что там за программа была у американских математиков, мы не знаем. Знаем, что им потребовалось 100 часов машинного времени, чтобы построить все традиционные магические квадраты 5-го порядка. Ну, можно строить не все, а, например, только начинающиеся с числа 1. Тогда количество свободно варьируемых переменных будет 13, и все они будут пробегать значения от 1 до 24. Это уменьшит время работы программы.

Если кто-то желает получить код программы, пишите.

[ice00]

About the squares of Smith of missing orders:
today I test the first phase of the algorithm for low order based onto sequences (calculating and storing objects for late use).
Here some results:

ORDER=6  MAGIC=3873 Found: 2233 combinations (0.114643%)
ORDER=6  MAGIC=2475 Found: 1290 combinations (0.0662288%)
ORDER=7  MAGIC=4167 Found: 41294 combinations (0.0480719%)
ORDER=8  MAGIC=6496 Found: 1626923 combinations (0.0367569%)
ORDER=9  MAGIC=9179 Found: 54173206 combinations (0.0207649%)

The first is the line for order 6 that we now have the square: only 0.11% of possible sequences available from all the combinations.
In the other levels, the sequences are less and less (instead we expect an increase at order being increased). This is why it is very difficult to build such squares.

The positive fact is that until order 9 the program is very quickly (at this stage), so when all the algorithm will be coded it is expected to have a resonable execution time.
Instead at order 9, time increases for enumerating all the sequences and it tooks lot of memory usage (with 2GB of main memory I got other 2GB of swap).

However I will continue to code the algorithm: maybe it will be used only for order 7 and 8.

[Nataly-Mak]

ice00
Большое вам спасибо, что вы работаете над алгоритмом (по-русски и по-старинному надо сказать так: низкий вам поклон). Наверное, всего два человека в мире занимаются построением магических квадратов порядков 7 - 9 из смитов: вы и я. А задача-то ведь стоящая, для её решения нужно иметь немалый опыт и навыки в программировании. Однако почему-то задача больше никого не интересует

Я предложила эту задачу на нескольких форумах. Нигде не нашлись желающие хотя бы попытаться её решить. Одни называют задачу бессмысленной, другие - совсем неинтересной. Ну, это известный ход: когда задача сложная и решить её сразу (известными методами) не получается, многие говорят: неинтересная задача!

[Nataly-Mak]

Очень много работала с квадратами порядков 7 – 9 из последовательных смитов.
Выдвигаю гипотезу: магические квадраты порядков 8 – 9 из последовательных смитов существуют уже для первого потенциального массива:

n = 8   массив:  58, …, 1776   S = 6496
n = 9   массив:  27, …, 2067   S = 9179

Пока могу представить только полумагические квадраты, “хромые” на одну диагональ:

n = 8

922  1755  483  382  346  861  166  1581 
 94  535  690  1776  274  913  1626  588 
 1255  636  1165  1449  85  391  852  663 
 1507  454  895  915  1376  265  378  706 
 319  1642  1219  58  985  634  355  1284 
 1111  627  438  576  666  517  1736  825 
 762  645  958  562  1086  1633  729  121 
 526  202  648  778  1678  1282  654  728

n = 9

 634  825  645  1255  526  654  1842  1903  895 
 1678  517  627  1755  1736  319  85  1376  1086 
 922  1642  2038  265  1581  913  454  636  728 
 1881  1282  762  1165  778  2067  535  588  121 
 706  1952  1966  985  1284  391  1111  94  690 
 1894  58  1633  1908  346  958  729  27  1626 
 648  1858  274  915  202  166  1795  1872  1449 
 378  483  852  576  1507  1935  666  861  1921 
 438  562  382  355  1219  1776  1962  1822  663

Таких полумагических квадратов получается очень много (несколько сотен или даже тысяч). Это даёт основание предполагать, что существуют и магические квадраты из данных массивов смитов.

А вот для первого кандидата в магический квадрат порядка 7 из последовательных смитов (массив: 58, …, 1165, S = 4167) мне пока не удалось получить ни одного полумагического квадрата. Так что существование такого магического квадрата под большим вопросом.

Ещё много экспериментировала с наименьшими магическими квадратами порядка 9 из произвольных смитов. Здесь тоже могу высказать гипотезу, что наименьший магический квадрат порядка 9 с магической константой $8737$ существует. Тоже получено очень много полумагических квадратов, в которых нет магической суммы только в одной диагонали. Кажется, я уже приводила пример такого полумагического квадрата.

-- Чт дек 03, 2009 10:04:34 --

ice00
Как опытный программист вы хорошо знаете, насколько важно иметь некоторые известные результаты, чтобы тестировать программу. Приведу для этой цели известные магические квадраты порядков 7 – 9 из смитов. Надеюсь, что они могут быть вам полезны.

Квадрат порядка 7 мне известен всего один:

567274 3279802 5859274 20502022 33961666 75835678 191489962
75839458 191484922 562234 3274762 5863054 20505802 33965446
20500762 33960406 75843238 191488702 566014 3278542 5858014
3282322 5861794 20504542 33964186 75838198 191483662 560974
191487442 564754 3277282 5856754 20499502 33967966 75841978
33962926 75836938 191482402 568534 3281062 5860534 20503282
5855494 20507062 33966706 75840718 191486182 563494 3276022

Этот квадрат построен из семи арифметических прогрессий длины 7 с одинаковой разностью (прогрессии любезно предоставил Mathusic).
Для порядка 8 известны два магических квадрата. Первый составной, автор квадрата tolstopuz:

526  2038 634  2067 778  2614 915  958
3390 319  1282 274  2155 690  1966 454
1255 1822 1842 346  1894 1903 706  762
94   1086 1507 2578 438  58   1678 3091
391  3226 985  663  654  1921 517  2173
1284 265  3595 121  1633 535  2461 636
3505 922  483  355  2974 627  1642 22
85   852  202  4126 4    2182 645  2434

Следующий квадрат построен из восьми арифметических прогрессий длины 8 с одинаковой разностью (прогрессии тоже найдены пользователем Mathusic):

395842 4504819 69062134 78721402 92055415 129027406 159620935 171743665
69963034 77820502 1296742 3603919 160521835 170842765 92956315 128126506
93857215 130829206 157819135 169941865 2197642 6306619 67260334 76919602
158720035 169040965 94758115 129928306 68161234 76018702 3098542 5405719
125423806 88451815 168140065 156017335 8108419 3999442 82325002 72665734
167239165 156918235 124522906 89352715 81424102 73566634 7207519 4900342
9910219 5801242 80523202 70863934 127225606 90253615 166338265 154215535
79622302 71764834 9009319 6702142 165437365 155116435 126324706 91154515

И, наконец, единственный известный магический квадрат 9-го порядка, он тоже составной и автор его tolstopuz:

12442 51682 49342 27814 81418 57586 35806 60142 78214
74722 37822 922 85378 55606 25834 100462 58054 15646
26302 23962 63202 53626 29794 83398 37894 55966 80302
51286 87034 73858 27562 50926 72994 2722 57298 30766
93298 70726 48154 95926 50494 5062 58306 30262 2218
67594 54418 90166 27994 50062 73426 29758 3226 57802
4594 77845 46363 20362 50242 65542 34186 76306 79006
84703 42934 1165 90562 45382 202 107986 63166 18346
39505 8023 81274 25222 40522 70402 47326 50026 92146

Затаив дыхание, жду ваших результатов

[ice00]

Thanks for the squares.
If I apply such sequences, I obtain:

ORDER=7  MAGIC=331495678 Found: 60691 combinations (0.0706526%)
ORDER=8  MAGIC=10530   Found: 1878989 combinations (0.0424518%)
ORDER=8  MAGIC=168260706  Found: 0 combinations (0%)

The negative point here is that there is a bug in program (3° line has 0 combintations, that it is impossible).
The positive is that % of combinations is about the same for the sequence of Smith we have not jet a square.
However I haveto fix the bug before going on.

[Nataly-Mak]

На сайте о магических кубах нашла ссылку на какой-то странный магический квадрат 32-го порядка, написано так:

A 32nd-order trimagic square

Скажите, пожалуйста, что означает "trimagic square"? Google перевёл так: "trimagic квадратный"
Ну, что это квадрат, я сама знаю, а вот какой квадрат? Впервые встречаю такой термин.
Квадрат скопировала, смотрю на него и не вижу ничего особенного. Магическая константа равна 16400, как и положено ей быть.