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

[maxal]

Nataly-Mak
trimagic - это тот, который остается магическим после возведения всех элементов как в квадрат, так и в куб.

[ice00]

This morning I finish to build the program for order 6 to 9 of Smith.
I start it for order 6 to see if it works. It is extremely low: in 5 hours it has test 295 loops of 2233 max. This means that just for order 7 it will need verly lot of time (I insert however the possibility to restart the program giving the value to use for the external loop).
Maybe I need to test it with a 5 order to see if working.

[Nataly-Mak]

maxal
Спасибо за перевод термина. Теперь буду знать. Да, это сложный квадрат получается.
ice00
Вот я и опасалась, что количество комбинаций будет очень большим и программа будет долго выполняться. Тут приходится надеяться, что повезёт и нужная комбинация окажется недалеко от начала проверки всех комбинаций. Нам ведь достаточно найти один магический квадрат, то есть программу можно выполнять до первого магического квадрата. Чем дальше будет нужная комбинация, тем дольше будет выполняться программа.
Да, конечно, для порядка 5 программа должна выполняться быстрее, так как количество всех комбинаций будет значительно меньше. Наверное, надо попробовать начать с порядка 5. Кроме того, нам нужна программа для порядка 5 для поиска наименьшего магического квадрата из последовательных смитов. Мы такой ещё не нашли, у нас есть только наименьший магический квадрат 5-го порядка из произвольных смитов (кстати, его недавно построил 12d3 по своей программе, улучшив результат, полученный раньше Бодигримом). Пользователь 12d3 сообщал, что он проверил по своей программе для порядка 5 смиты до миллиона и магического квадрата из последовательных смитов не нашёл. У меня почему-то его программа для порядка 5 не работает (а для порядка 6 работает).

[ice00]

I wrote the program even for order 4 other that 5 and so I find that there is a bug in some points of the code. But when I start to search for the bug I realize that there is a missing features into the program (columns reorder), so in this state the program will not test all the combinations. I'm try to thinking of how to implement this part that maybe will slow the program even more and more

[Nataly-Mak]

ice00
К сожалению, перевод вашего сообщения очень плохой. Вы пишете, что есть ошибка в некоторых пунктах кода. Кода программы или алгоритма?
Вы проверили программу для порядка 5?
Я тестировала отдельные части своей программы для порядка 6 (о чём уже очень подробно здесь рассказала). У меня всё получалось, за исключением того, что я не могу сделать ту часть алгоритма, которая получает все наборы из 4 строк, так как их очень много получается. В остальном я не вижу ошибки в своём алгоритме. Комбинации должны быть получены абсолютно все.
Возьмём известный магический квадрат порядка 6, рассмотрим в нём 4 первые строки, эти 4 строки обязательно должны быть получены по алгоритму. А затем программа обязательно должна достроить эти готовые 4 строки до магического квадрата, это неизбежно произойдёт. Вы согласны?
Приведите, пожалуйста, результаты теста для квадрата порядка 5. Что не получается? В каком именно пункте? Для порядка 5 мы будем брать все возможные наборы из 3 строк, а потом достраивать их до магического квадрата. Понятно, что оригинальных наборов из 3 строк будет меньше и вариантов этих наборов тоже будет значительно меньше, чем для порядка 6. Тут можно очень хорошо протестировать программу. Возьмите известный магический квадрат 5-го порядка из смитов, например, вот этот:

4 166 634 762 265 
382 346 663 355 85 
645 517 454 121 94 
526 483 58 202 562 
274 319 22 391 825

Жду результатов теста для квадрата порядка 5.

-- Пн дек 07, 2009 12:55:20 --

Вот сейчас выполнила первый этап своего алгоритма - формирование строк с суммой чисел равной магической константе квадрата $1831$ (для приведённого выше магического квадрата 5-го порядка). Программа выдала всего 236 строк. Вот несколько первых строк:

4  22  346  634  825 
 4  22  454  526  825 
 4  22  517  526  762 
 4  22  526  634  645 
 4  58  382  562  825 
 4  85  346  634  762 
 4  85  355  562  825 
 4  85  391  526  825 
 4  85  454  526  762 
 4  85  517  562  663 
 4  94  274  634  825 
 4  94  346  562  825 
 4  94  382  526  825 
 4  94  391  517  825 
 4  94  454  517  762 
 4  94  454  634  645 
 4  94  526  562  645 
 4  121  319  562  825 
 4  121  355  526  825 
 4  121  382  562  762 
 4  121  517  526  663 
 4  166  202  634  825 
 4  166  265  634  762 
 4  166  274  562  825 
. . . . . . . . . . . . . . . . . .

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

[ice00]

Bug is in the program as I obtain (in one stage):

ORDER=5  MAGIC=1831

square number 1
Start calculating combinations
End calculating combinations
Found: 236 combinations (0.444193%)
external loop=0
...
external loop=230
4   166 634 762 265
4   166 634 762 265
645 517 121 526 22
454 483 58  562 274
94  202 319 391 825

and here two rows are equals and this should never happen.

[Nataly-Mak]

Поняла, в чём ошибка: почему-то первая строка продублирована. Однако эта строка уже верная, она точно такая, как в магическом квадрате.
Вам осталось совсем чуть-чуть, вы близки к цели.

[Nataly-Mak]

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

4 166 265 634 762
85 346 355 382 663
94 121 454 517 645

Далее пишу программу следующего этапа: получаю из этого оригинального набора все варианты путём перестановки элементов в строках (строки не переставляю). Даже на Бейсике программа этого этапа полностью выполняется за 2 минуты и, разумеется, находит нужный вариант набора:

4 166 634 762 265
382 346 663 355 85
645 517 454 121 94

На следующем этапе этот вариант набора без проблем достраивается до магического квадрата.
Из оригинального набора из трёх строк всего получается перестановкой элементов в строках 120^3 вариантов. Если сделать ещё перестановку строк, то вариантов будет 6*120^3. Это для одного набора, а для $n$ наборов надо будет проверить n*6*120^3 вариантов.
Вся программа (всех этапов) здесь должна выполниться быстро.

Попробовала построить из этого массива магический квадрат по программе пользователя 12d3. Программа работала несколько минут, а потом выдалось сообщение, что слишком мало виртуальной памяти.
И 12d3 пропал

ice00
Я так и не поняла, почему у вас продублировалась первая строка. Вы нашли ошибку в программе? Получается, что ошибка у вас на этапе формирования оригинальных наборов из трёх строк. Ведь оригинальный набор должен состоять из всех разных чисел.

Я очень много думала над алгоритмом, анализировала все этапы. И для квадрата порядка 5, мне кажется, всё очень просто должно получиться.
Для следующих порядков резко увеличивается количество вариантов, но всё равно надо попытаться. К сожалению, на Бейсике я не могу этого сделать.

[ice00]

Цитата:

ice00
Я так и не поняла, почему у вас продублировалась первая строка. Вы нашли ошибку в программе? Получается, что ошибка у вас на этапе формирования оригинальных наборов из трёх строк. Ведь оригинальный набор должен состоять из всех разных чисел.

I had not time in this two holiday days to work on finding the bug
However coding in C++ with pointers is very easy to make a bug in program. This is why I use Java normally for creating programs.

[Nataly-Mak]

(Оффтоп)

Уважаемые коллеги!

Человек работает над сложной задачей. У него что-то не получается...

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

Неужели сейчас эта традиция напрочь исчезла?

[Nataly-Mak]

Начала писать статью "Общие формулы магических квадратов", которая давно написана вчерне, но отвлекли магические кубы. На время оставила кубы

Просьба к коллегам высказывать критические замечания к статье, а также пожелания по её содержанию. Планирую дописать статью в ближайшие 2-3 дня.

Далее в планах новая книга о магических квадратах: "Нетрадиционные магические квадраты". В ней будет рассказано о нетрадиционных магических квадратах вообще и о квадратах из простых чисел и чисел Смита - в частности.
Вообще-то все материалы к этой книге уже написаны и выложены на сайте, осталось только их собрать и систематизировать.

Я пригласила ice00 в соавторы, потому что у него очень интересные материалы по магическим квадратам из простых чисел, а также уникальные программы построения таких квадратов. Он вроде бы согласился

[Nataly-Mak]

К высказанным выше гипотезам о наименьших магических квадратах из смитов порядков 8 – 9 добавлю ещё одну.
Сегодня попыталась построить наименьший магический квадрат 8-го порядка из произвольных смитов. Теоретическая минимальная константа такого квадрата по моим расчётам равна $5856$. Но полумагические квадраты мне удалось получить только для константы $5861$. Высказываю гипотезу, что магический квадрат из произвольных смитов с такой магической константой существует. Для построения этого квадрата берутся первые 64 смита, но число 1642 заменяется на число 1776. Вот пример полумагического квадрата из указанного массива смитов, в котором нет магической суммы только в одной диагонали:

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

Таких полумагических квадратов получается очень много.

[ice00]

Цитата:

Я пригласила ice00 в соавторы, потому что у него очень интересные материалы по магическим квадратам из простых чисел, а также уникальные программы построения таких квадратов. Он вроде бы согласился

Yes, I agree

[Nataly-Mak]

ice00 в сообщении #270055 писал(а):

Цитата:

Я пригласила ice00 в соавторы, потому что у него очень интересные материалы по магическим квадратам из простых чисел, а также уникальные программы построения таких квадратов. Он вроде бы согласился

Yes, I agree

Очень рада!
Нам надо найти ещё хорошего переводчика, чтобы перевёл русскую часть книги на английский, а английскую часть книги на русский.

Обращаюсь к форумчанам: кто согласен стать нашим переводчиком?

[Nataly-Mak]

В качестве лирического отступления: на многих формулах есть смайлик – бьюсь об стенку головой. Жалко, что здесь нет такого… Он мне очень нравится, а главное – здорово подходит

Ну и задала я всем задачу! Тут ведь наверное есть кандидаты и доктора математических наук. Или нет? Или такие важные персоны считают мои задачи не стоящими внимания. Ну, пишет там чего-то старая бабка про квадраты… Чего там решать?

А между тем, для порядка 5 мой алгоритм реализуется ЭЛЕМЕНТАРНО даже на Бейсике. Я не бросила эту задачу, продолжаю над ней работать. Реализовала самую сложную часть алгоритма: полное преобразование одного оригинального набора из трёх строк с последующим достраиванием каждого варианта набора до магического квадрата. В программе я не заложила перестановку строк в наборе, заложила полную перестановку всех чисел в строках. Эти 120^3 вариантов даже Бейсик щёлкает запросто. Находятся абсолютно все варианты набора из трёх строк и получаются магические квадраты. Вот пример. Ввожу в программу такой набор из трёх строк:

58 85 391 454 648
4 319 355 382 576
27 202 346 526 535

Программа выдаёт такой магический квадрат:

85 454 391 58 648
576 355 4 382 319
535 27 346 202 526
274 94 517 729 22
166 706 378 265 121

Подробно о реализации алгоритма для порядка 5 рассказано в первой части статьи. Сейчас пишу вторую часть статьи, она посвящена общим формулам и схемам магических квадратов 6-го порядка.

Код программы на языке QBASIC, реализующий указанный этап алгоритма для построения магических квадратов порядка 5 из смитов, здесь. Подчеркну, что предложенный мной алгоритм идеально подходит именно для магических квадратов из смитов, потому что из смитов формируется мало строк с заданной суммой чисел в строках, а чем меньше таких строк, тем проще (быстрее) выполнится программа.

А между тем, уважаемые коллеги, этот алгоритм до сих пор не реализован для порядков 6 – 9 (тоже имеется в виду построение магических квадратов из смитов). Признайтесь хоть, по крайней мере, кто-нибудь попытался это сделать (кроме ice00)?
Ну, вот, например, для порядка 6 это сделал пользователь 12d3 (кстати, по моей просьбе, отправленной ему в личном сообщении). Правда, он придумал свой алгоритм, но квадраты построить удалось по его программе.
И что же: порядок 7 уже непреодолим? Или просто не хотим преодолевать?

По поводу квадратов 6-го порядка возникла такая интересная задача. Для построения нетрадиционного ассоциативно квадрата надо сформировать массив, все числа которого разбиваются на 18 комплементарных пар чисел. Из произвольных натуральных чисел такой массив сформировать очень просто. А вот можно ли сформировать такой массив из простых чисел или из чисел Смита?
Пример ассоциативного магического квадрата 6-го порядка из произвольных натуральных чисел:

1 47 6 48 5 43
35 17 30 16 31 21
36 12 41 13 40 8
42 10 37 9 38 14
29 19 34 20 33 15
7 45 2 44 3 49

Этот квадрат обсуждался здесь давно, он не только ассоциативный, но и пандиагональный, то есть идеальный.

Можно начинать новую последовательность – из магических констант наименьших пандиагональных квадратов из простых чисел. Пандиагонального квадрата 3-го порядка не существует. Наименьший пандиагональный квадрат 4-го порядка я уже построила. Пандиагональный квадрат 6-го порядка из последовательных простых чисел здесь был приведён. Надо выяснить, является ли он наименьшим. Может быть, из произвольных простых чисел есть квадрат с меньшей константой. Наименьший пандиагональный квадрат 5-го порядка пока не построен; точнее мной не построен, а вообще, возможно, кем-то уже построен.

Кстати, с последовательностями в OEIS происходит пробуксовка. Я отправила последние результаты для последовательностей А164843 и А073502 19 октября. Получены члены обеих последовательностей до порядка 35 включительно; это результаты, полученные совместно с ice00 (кроме квадрата порядка 15 для последовательности А164843, этот квадрат я построила по своей программе). Однако по сей день эти результаты в OEIS не появились. Думаю, что два месяца вполне достаточный срок, чтобы внести новые результаты.

Помощник главного редактора OEIS maxal указывает мне на то, что сообщения в OEIS должны писаться на английском языке. Придётся искать переводчика. Впрочем, maxal обещал отправить результаты в Энциклопедию. Подожду ещё пару месяцев (счёт пошёл с 16 декабря), потом буду искать переводчика и начинать всё сначала, насколько хватит сил.

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

Обратилась за помощью и в теме "Программирование", но тоже абсолютная тишина. Некоторые просто дают тривиальный совет: освойте современный язык программирования. Ну, я не за таким советом сюда прихожу...