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

[Nataly-Mak]

Да-а-а-а...
Оказывается о магических квадратах пишут очень серьёзные научные статьи:
http://www.ncstu.info/content/_docs/pdf ... /07/22.pdf

Цитата:

При решении данной задачи (имеется в виду задача построения магического квдарата порядка N) методом перебора потребуется N^2! перестановок, что весьма трудоёмко. Приемлемое приближённое решение может быть найдено с помощью нейронной сети Хопфилда, для чего требуется переформулировать задачу на языке оптимизации функции Ляпунова

Мне непонятно, как можно построить магический квадрат приближённо. Кто-нибудь может объяснить?
Дальше пыталась читать статью, но поскольку статья научная, мне ничего не удалось в ней понять.

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

[Nataly-Mak]

Товарищи! Все, кто занимался проверкой квадратов 4-го порядка из последовательных смитов. Убедительно прошу сообщить, до каких пределов были проверены потенциальные массивы из 16 последовательных смитов.
Собираюсь продолжить проверку, maxal подбросил смитов в интервале от 1 до 2 миллионов. Как я уже сообщала, проверила 800 кандидатов, это давно. Последний проверенный массив такой:

97906, 97915, ..., 98126, 98144

Начинаю проверку с 801-го кандидата:

97915, ..., 98150   S = 392194

Пожалуйста, сообщите, если кто-то проверял, чтобы мне не выполнять пустую работу. Может быть, tolstopuz проверил всех кандидатов до миллиарда, а я буду опять стараться, компьютер зря нагружать

И, наконец, в конце концов: кто-нибудь же может довести до ума программу построения магических квадратов 5-го порядка из смитов?????!!!!!

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

Да, кстати, здесь были выложены программы построения квадратов 5-го и 6-го порядков пользователем 12d3. Но, к сожалению, для порядка 5 у меня программа не хочет работать, а для порядка 6 работает.
И 12d3 куда-то пропал. И ice00 тоже пропал

Вчера начала поиск новых коллег. Нашла интересную страничку о магических квадратах, я такую ещё не видела. И представлены на страничке два магических квадрата - 6-го и 7-го порядков. И написано, что построены они по некоторому рекуррентному алгоритму. Но самого алгоритма на страничке нет. Уже написала письмо автору, жду ответ.
Может быть, кто-нибудь встречал рекуррентные формулы для магических квадратов? Это в связи с тем, что я сейчас работаю над статьёй "Общие формулы магических квадратов".

[Nataly-Mak]

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

a1 a2 a3 a4 x1
a5 a6 a7 a8 x2
x11 x12 a9 a12 x7
x10 a10 x8 a11 x6
x3 x13 x8 x5 x4

Подробности в статье.

Схема реализована на языке QBASIC. Программа работает. Для тестирования взяла известный пандиагональный квадрат 5-го порядка. В программе 12 вложенных циклов, все переменные циклов принимают 25 различных значений. Полностью у меня программа не выполняется за реальное время (вообще много времени не даю программе на “раздумья”, если программа за час не справляется, я её прерываю). Тогда применяю такой приём: искусственно фиксирую значения первых 6 свободных переменных. В этом случае программа работает несколько секунд и выдаёт тот квадрат, который взят для тестирования программы.

Этот пандиагональный квадрат из простых чисел построен по другой формуле (формула приведена в указанной статье, см. рис. 34):

7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397

Магическая константа квадрата равна $853$. Думаю, что это не наименьший подобный квадрат.
Предлагается улучшить мой результат.

ЗАДАЧА: построить наименьший пандиагональный квадрат 5-го порядка из простых чисел. Ну, а также из чисел Смита.

Из чисел Смита мной тоже построен пандиагональный квадрат 5-го порядка (по той же формуле с рис. 34), но он наверняка не наименьший:

627 11989273 4619515 4653553 6633247
4653562 6633265 636 11989255 4619497
11989264 4619479 4653544 6633274 654
6633256 663 11989282 4619488 4653526
4619506 4653535 6633238 645 11989291

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

Напомню, что наименьший пандиагональный квадрат 4-го порядка из простых чисел мной построен (он, кажется, здесь приведён). Известен и пандиагональный квадрат 6-го порядка из простых чисел (он есть в этой ветке post245866.html#p245866)
Этот квадрат построен из последовательных простых чисел. Вот только является ли он наименьшим среди пандиагональных? Раньше этот квадрат был приведён в OEIS в качестве наименьшего квадрата 6-го порядка из последовательных простых чисел. Но потом выяснилось, что это не так: есть магический квадрат (не пандиагональный) 6-го порядка из последовательных простых чисел с меньшей магической константой, его построил ice00.
Как известно, пандиагональных квадратов 3-го порядка не существует (ни классических, ни нетрадиционных).

ice00
Могли бы вы заложить в свои программы построения магических квадратов из простых чисел проверку пандиагональности строящихся квадратов? Это ведь несложно сделать.

Для порядка 6 я тоже разработала схему построения пандиагональных квадратов (разумеется, нетрадиционных, потому что для данного порядка не существует традиционных пандиагональных квадратов). Смотрите эту схему в статье.

[ice00]

Цитата:

Могли бы вы заложить в свои программы построения магических квадратов из простых чисел проверку пандиагональности строящихся квадратов? Это ведь несложно сделать.

Tell me for what orders did you want my programs to produces such kind of squares and I email you the executable

[Nataly-Mak]

О, ice00, рада вашему ответу!
Тут все дружно замолчали, как будто у всех одновременно пропал интерес к магическим квадратам Говорят, не могу я заинтересовывать... Однако тема эта вот уже почти два года активна.
Давайте попробуем построить наименьшие пандиагональные квадраты из простых чисел порядков 4 - 10. Этого будет вполне достаточно.
А ещё сделайте, пожалуйста, программу для одного большого порядка, например 20. По этой программе попробую построить наименьший пандиагональный квадрат из чисел Смита. Заранее благодарю вас!

[maxal]

Вот нашёлся-таки минимальный квадрат 3x3 из последовательных смитов:

84138954584 84138954498 84138954532
84138954486 84138954538 84138954590
84138954544 84138954578 84138954492

Магическая константа равна $3\cdot 84138954538 = 252416863614$.

Эта находка стала возможной, благодаря реализации просеивания смитов, про которую я тут писал ранее:

maxal в сообщении #256127 писал(а):

Если хотите ускорить генерацию смитов, то нужно использовать что-то типа решета Эратосфена, где при прогоне каждого простого $p$ и его степени к соответствующим элементам массива нужно прибавлять сумму цифр $p$. Тогда сумма цифр простых делителей будет накапливаться в элементах массива без всякой факторизации. Но реализация этого алгоритма для достижения предела $10^{10}$ будет уже не три строчки и сильно зависеть от объёма доступной памяти.

Текущий выбранный потолок $10^{12}$ с этим решетом достигается за трое суток. Можно попробовать поискать квадрат 4x4...

[maxal]

Следующий 3x3 квадрат из последовательных смитов:

864515353870 864515353860 864515353844
864515353832 864515353858 864515353884
864515353872 864515353856 864515353846

Здесь элементы уже на порядок больше чем в предыдущем.

[Mathusic]

maxal в сообщении #276508 писал(а):

Следующий 3x3 квадрат из последовательных смитов:

864515353870 864515353860 864515353844
864515353832 864515353858 864515353884
864515353872 864515353856 864515353846

Здесь элементы уже на порядок больше чем в предыдущем.

Поздравляю! Сильно - практически квадратиллион.

[Nataly-Mak]

maxal в сообщении #275573 писал(а):

Можно попробовать поискать квадрат 4x4...

А зачем?
Глупые, пустые головоломки, "не имеющие никакой ценности"!..

[Nataly-Mak]

Вот!
Никто ничего не отвечает...
Магические квадраты из смитов порядка 7 - 9 (из произвольных и из последовательных) так никто и не построил.
У ice00 не получилось, а больше никто не хочет. Я очень хочу, но не могу.
К тому же, для этих квадратов не нужны квадриллионы, даже миллиарды с миллионами не нужны. Квадраты построятся из смитов в интервале (1, 100000), в чём я почти уверена.

Но вот никому неинтересна задача и всё тут!

Квадрат 4-го порядка из последовательных смитов я уже искала, проверила 1000 кандидатов, но поскольку на Бейсике всё это крайне утомительно делать, бросила.

Я уже обращалась с просьбой помочь решить задачу к нескольким форумчанам (и не только на этом форуме). Но всюду получила отказ.

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

[Nataly-Mak]

Продолжаю свои "страдания"

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

202  778  654  454  121  1165  346 
 4  913  895  535  355  391  627 
 382  762  648  645  166  852  265 
 690  27  85  825  706  526  861 
 562  588  319  576  915  94  666 
 958  378  483  22  728  634  517 
 922  274  636  663  729  58  438

Таких ПМК я могу сгенерировать как угодно много.
Но вот со второй программой у меня закавыка вышла.
Я спросила ice00, какой способ он использует в этой программе для получения магичности главных диагоналей. Он ответил, что использует перестановку строк. Но это же очень мало! Это сработало для квадратов порядка 10, а для квадратов порядков 7 - 9 не срабатывает. Я предложила ему сделать в программе перестановку строк с одновременной перестановкой всех столбцов. Это намного повысит вероятность получения магической суммы в главных диагоналях. Он сделал такую программу и прислал её мне. Но, увы, она у меня не работает.
На этом зксперимент закончился.

Я написала на Бейсике программу, в которой переставляются все строки с одновременной перестановкой 6 столбцов. Это всего 5040*720 вариантов. Такая программа выполняется примерно 35-40 минут. Понятно, что для меня это неприемлемо, так как мне надо обработать не один, а сотни ПМК.

Обращаюсь ещё раз ко всем с этой вполне конкретной задачей. Может ли кто-нибудь сделать исполняемую программу перестановки всех строк с одновременной перестановкой всех столбцов в ПМК 7-го порядка с целью получения магической суммы в главных диагоналях?
Программа эта очень простая! Её может написать даже школьник.
(В программу надо заложить ввод файла, содержащего $n$ полумагических квадратов. Этот файл может иметь, например, такое имя: mk.txt).

С такой программой я могу продолжить обработку ПМК 7-го порядка, имея гораздо больше шансов найти магический квадрат.

[maxal]

Перенесено из темы Магические кубы.

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

Насчёт двух магических квадратов (один содержит число 0, а другой его не содержит, потому что все числа увеличили на 1), везде и всюду два таких магических квадрата никто не различает, это один и тот же магический квадрат.

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

[Nataly-Mak]

maxal в сообщении #285314 писал(а):

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

Насчёт двух магических квадратов (один содержит число 0, а другой его не содержит, потому что все числа увеличили на 1), везде и всюду два таких магических квадрата никто не различает, это один и тот же магический квадрат.

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

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

Вы уходите в другую область. Мы обсуждаем обычные магические кубы из произвольных натуральных чисел.
О специальных нетрадиционных магических кубах (из простых чисел или из чисел Смита) я здесь не говорила.
Специальный вид кубов накладывает свои ограничения!

-- Ср фев 03, 2010 08:55:32 --

Цитата:

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

Вам известны такие формулы? Ну, например, для магического квадрата 4-го (или 5-го) порядка? Чтобы все параметры представляли собой элементы квадрата.
Я знаю только такие формулы, в которых элементы являются суммой или разностью параметров, и только один элемент является параметром в чистом виде.

[maxal]

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

Вам известны такие формулы? Ну, например, для магического квадрата 4-го (или 5-го) порядка? Чтобы все параметры представляли собой элементы квадрата.

Вот для 4-го порядка:

a, a-b+c-f+h, -a+b-c+e+f, -a+f+g,
-a+b+c+d-e, -a-c+e+f+g, a-b+h, a-d+e,
-b-c-d+e+f+g+h, b, c, d,
e, f, g, h

-- Wed Feb 03, 2010 00:13:55 --

Для 5-го порядка:

a, a-c+d-g+i-l+o, -2*a+2*b+c+e+2*f+2*j-2*k-2*d-m, -b+d-e-f+g-i-j+2*k+l+m, -b-f-j+k+l+m+n,
-a+c+e+f+h+j-2*k+d+g+i-l-m-n-o, -a+k-d-i+l+m+n, 2*a-2*b-c-e-2*f-h-2*j+3*k+d+l+m+n+o, b-d+f-g+j-k+o, b,
-c-d-e-f+k+l+m+n+o, c, d, e, f,
-g-h-i-j+k+l+m+n+o, g, h, i, j, 
k, l, m, n, o

[Nataly-Mak]

В этой формуле не все элементы квадрата суть параметры в чистом виде, есть ведь также их суммы и разности.
То есть, вы хотели сказать, что каждый параметр является самостоятельным элементом квадрата. Так?
Ну и что это даёт? Какая особенная выгода? Да, эти 7 параметров будут пробегать только значения из множества простых чисел, но ведь остальные элементы могут и не быть при этом простыми.
Чем же в этом смысле хуже известная формула Бергхольта? Правда, в этой формуле 8 параметров (в этом она уступает вашей).
В формуле Бергхольта, кажется, только 4 параметра являются элементами квадрата. Зато, формула Бергхольта одновременно даёт возможность получать ассоциативные и пандиагональные квадраты (при определённых условиях для входящих в неё параметров).
А по вашей формуле можно получать ассоциативные и пандиагональные квадраты?

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

Ох, простите, неправильно посчитала параметры в вашей формуле. У вас их тоже 8! Как и в формуле Бергхольта.