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

[Nataly-Mak]

На форуме Портала ЕН в теме "Латинские и магические квадраты" сегодня обнаружила интересное сообщение... Поскольку не могу ответить на том форуме (забанена), прошу позволения ответить здесь (уверена, что автор сообщения просматривает данный форум, о чём он сообщал на форуме Портала ЕН).

Цитата:

---
Ps сам заметил, что в статье много неточностей.
А судя по ссылкам, статью писали тов. Макарова и Александров.

Речь идёт о статье "Магический квадрат" в Википедии.

Уважаемый YURI! Во-первых, статьи в Википедии пишутся коллективно, кроме того, их правят. Статья "Магический квадрат" была начата задолго до того, как я её прочла и приняла в ней посильное участие. Мной вставлено в статье две-три фразы (не считая ссылок).
Во-вторых, хотелось бы узнать, какие именно неточности вы заметили в этой статье. Тем более, что вы пишете: много неточностей заметили. Это надо поправить! Пожалуйста, расскажите об этих неточностях.
***
Кстати, очень интересное совпадение: сообщение YURI на форуме Портала ЕН в точности повторяет сообщение Mathusic'а здесь.

[Mathusic]

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

На форуме Портала ЕН в теме "Латинские и магические квадраты" сегодня обнаружила интересное сообщение... Поскольку не могу ответить на том форуме (забанена), прошу позволения ответить здесь (уверена, что автор сообщения просматривает данный форум, о чём он сообщал на форуме Портала ЕН).

Цитата:

---
Ps сам заметил, что в статье много неточностей.
А судя по ссылкам, статью писали тов. Макарова и Александров.

Речь идёт о статье "Магический квадрат" в Википедии.

Уважаемый YURI! Во-первых, статьи в Википедии пишутся коллективно, кроме того, их правят. Статья "Магический квадрат" была начата задолго до того, как я её прочла и приняла в ней посильное участие. Мной вставлено в статье две-три фразы (не считая ссылок).
Во-вторых, хотелось бы узнать, какие именно неточности вы заметили в этой статье. Тем более, что вы пишете: много неточностей заметили. Это надо поправить! Пожалуйста, расскажите об этих неточностях.
***
Кстати, очень интересное совпадение: сообщение YURI на форуме Портала ЕН в точности повторяет сообщение Mathusic'а здесь.

Я Вам ответил в ЛС. А на мысль об основных авторах статьи меня меня навело обилие ссылок на Вас и г-на Александрова.

[Nataly-Mak]

У меня есть пара интересных алгоритмов для построения нетрадиционных магических квадратов из смитов порядка 6 (сотовых) и порядка 8 (составных).
Для реализации этих алгоритмов нужны арифметические прогрессии из смитов длиной 4, как можно больше (с любой разностью не равной 1).
Бодигрим, нет ли у вас таких прогрессий?
Имею несколько таких прогрессий (на форуме Портала ЕН один товарищ выложил прогрессии длиной 5 и длиной 6), но мало мне для проверки своих задумок.

[Бодигрим]

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

Бодигрим, нет ли у вас таких прогрессий?

Прогрессий длины 4 с одной и той же разностью?

[Nataly-Mak]

Нет, с разными разностями, кроме разности равной 1, потому что смитов-близнецов (четвёрок, пятёрок и шестёрок) много известно, из них я могу образовать много арифметических прогрессий с разностью 1.
Вот, в частности, у меня много прогрессий длиной 5 с разностью 36. Надо бы добавить к ним ещё прогрессии длиной 4 (с такой же разностью). С разностями 9, 18, 45, 54 и 72 тоже много прогрессий длиной 5. Кстати, интересная закономерность: больше всего прогрессий с разностями, кратными 9. Если можете добавить прогрессии длиной 4 с указанными разностями, сделайте это, пожалуйста.

-- Пн авг 24, 2009 16:36:34 --

Вот, например, первые арифметические прогрессии длиной 4 с разностью 36, образованные из арифметических прогрессий длиной 5, выложенных на форуме Портала ЕН:

67126, 67162, 67198, 67234
67162, 67198, 67234, 67270 
1704595, 1704631, 1704667, 1704703
1704631, 1704667, 1704703, 1704739 
1895422, 1895458, 1895494, 1895530
1895458, 1895494, 1895530, 1895566
3965674, 3965710, 3965746, 3965782 
3965710, 3965746, 3965782, 3965818   
7276954, 7276990, 7277026, 7277062
7276990, 7277026, 7277062, 7277098  
8713633, 8713669, 8713705, 8713741
8713669, 8713705, 8713741, 8713777   
9544918, 9544954, 9544990, 9545026
9544954, 9544990, 9545026, 9545062

У меня получилось около 140 таких прогрессий с разностью 36.
Далее у меня такой алгоритм: надо найти суммы членов каждой прогрессии. Из полученного массива сумм следует построить хотя бы один магический квадрат 3-го порядка. Если это получится, то можно будет построить сотовый квадрат 6-го порядка из смитов.
Вот с суммами такой вопрос: Бейсик представляет суммы в нормализованном виде, вот так:

268720  268864  6818596  6818740  7581904  7582048  1.586291E+07  1.586306E+07  2.910803E+07  2.910818E+07  3.485475E+07  
3.485489E+07  3.817989E+07  3.818003E+07  5.889803E+07  5.889818E+07  6.191458E+07  6.191472E+07  6.274974E+07  
6.274989E+07  6.503834E+07  6.503848E+07  7.581659E+07  7.581674E+07  7.581674E+07  7.581688E+07  7.869112E+07 … 

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

[Бодигрим]

Хм. Я выписал все прогрессии из четырех чисел-смитов до $10^6$ в файл http://grafline.com.ua/uploads/progr_smith.rar. В каждой строке первое число - разность прогрессии, второе - элементы прогрессии. Или вам надо еще больше элементов?

[Nataly-Mak]

Бодигрим, арифметические прогрессии длиной 4 из смитов скачала и посмотрела. Вы выполнили задание по максимуму (я вам указала желаемые для меня разности, а вы нашли прогрессии со всеми разностями). Спасибо! Теперь вполне достаточно имею прогрессий. Буду пытаться реализовать свои алгоритмы. Один из них уже кратко описан выше. Надо взять все арифметические прогрессии с одинаковой разностью (уже попробовала для разности 36; для этой разности больше всего прогрессий имеется), вычислить сумму членов каждой прогрессии. Из массива этих сумм попытаться построить магический квадрат 3х3. Если это получится, цель будет достигнута. Это алгоритм для построения сотового магического квадрата 6-го порядка из смитов.
Второй алгоритм - для построения составного магического квадрата 8-го порядка из смитов. Этот алгоритм описан мной на форуме Портала ЕН в теме "Числа Смита". Пока не знаю, сработает ли этот алгоритм.
Если у вас есть арифметические прогрессии из смитов длиной 8 в количестве 8 штук (с одинаковой разностью), вы можете построить магический квадрат 8-го порядка по алгоритму, представленному в статье "Нетрадиционные магические квадраты из чисел Смита". В статье приведены также вспомогательные квадраты для построения магических квадратов из смитов порядков 9 и 10. Нет только прогрессий.

[Mathusic]

Так каков максимальный порядок квадрата из смитов (разных), который уже построен?

[tolstopuz]

Mathusic в сообщении #237784 писал(а):

Так каков максимальный порядок квадрата из смитов (разных), который уже построен?

Я как-то сделал 9x9.
post229995.html#p229995

[Nataly-Mak]

Кстати, у квадрата 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 22522 35095 33169
93298 70726 48154 95926 50494 5062 40909 30262 19615
67594 54418 90166 27994 50062 73426 27355 25429 38002
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

заменив один из составляющих квадратов 3х3.

-- Вт авг 25, 2009 15:29:01 --

Построить составной магический квадрат из смитов нетрудно. Но, к сожалению, у меня программа очень медленно работает, а на больших массивах совсем затыкается. Здесь был выложен пользователем tolstopuz квадрат 8х8, в котором не хватает одного квадрата 4х4. Начав выполнение программы для фиксированной магической константы 3888, я быстро получила несколько квадратов, взяла один из них. Конечно, в этом квадрате есть такие числа, которые уже встречаются в трёх первых квадратах. Покажу полученный квадрат 8х8 просто для примера:

895 1795 663 535 1282 1642 645 319
690 94 2182 922 915 391 2227 355
2218 1086 526 58 985 636 634 1633
85 913 517 2373 706 1219 382 1581
861 2839 22 166 22 958 2218 690
562 346 2326 654 1921 861 121 985
1507 438 778 1165 663 1795 1111 319
958 265 762 1903 1282 274 438 1894

Если бы удалось найти четвёртый квадрат, состоящий из других смитов, то задача была бы решена (для данной магической константы).
Задача решена пользователем tolstopuz, но, может быть, для другой магической константы составляющих квадратов 4х4.

Точно по такой же схеме можно построить составной квадрат 12-го порядка. В этом случае можно брать квадраты 4х4 не с одинаковой магической константой, как для квадрата 8х8, а так чтобы магические константы составляющих квадратов 4х4 образовали магический квадрат 3х3. Квадрат 12-го порядка можно составлять и из квадратов 3х3, которые строятся быстрее.
Так же построен и составной квадрат 9-го порядка.

[Бодигрим]

Mathusic в сообщении #237784 писал(а):

Так каков максимальный порядок квадрата из смитов (разных), который уже построен?

Я бы не сказал, что интересно строить квадраты максимально больших порядков без дополнительных ограничений. ИМХО интересно либо стремиться к минимальной константе, либо заниматься только простыми порядками.

[tolstopuz]

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

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

Что-то на projecteuler молчат. Подожду еще месяц и выложу его сюда.

[Nataly-Mak]

Бодигрим в сообщении #237952 писал(а):

Я бы не сказал, что интересно строить квадраты максимально больших порядков без дополнительных ограничений. ИМХО интересно либо стремиться к минимальной константе, либо заниматься только простыми порядками.

Не совсем поняла ваше высказывание. Вы можете построить, например, магический квадрат 10-го порядка из смитов хотя бы и без требования минимальной магической константы? А квадрат 11-го порядка? Простой перебор здесь вряд ли поможет. Нужны алгоритмы. Один из таких алгоритмов я нашла в книге Ю. В. Чебракова (он применяет его для построения магических квадратов из простых чисел). Уже применила этот алгоритм для построения магических квадратов 5 - 7 порядков. А для порядков 8 - 10 не могу применить, потому что не имею нужных арифметических прогрессий.
А магический квадрат 5-го порядка из смитов вы построили? У меня он наверняка не наименьший. Так же, как и квадраты порядков 6 - 7.
Квадрат 10-го порядка тоже можно составить из квадратов 5х5, но для этого надо построить 4 таких квадрата с одинаковой магической константой, но из разных чисел.

[Nataly-Mak]

Бодигрим, а как у вас дела с наименьшим магическим квадратом 6-го порядка из простых чисел? Удалось построить?
Я сейчас попробовала свой алгоритм. Взяла минимально возможную для квадрата 6-го порядка из простых чисел константу, это 432. Выбрала набор из 36 простых чисел. Сгенерировала все строки по 6 чисел, так что сумма в строках равна 432. Таких строк получилось 2168. Второй этап: из этих строк формирую наборы по 6 строк, чтобы во всех строках числа были различны. С программой этого этапа у меня проблемы: в ней несколько циклов и массив довольно большой (2168 элементов). Гоняла программу долго, а выполнила, наверное, 100-ую часть. Но несколько наборов программа всё же нашла. Вот один из них:

3  5  47  109  131  137 
 7  11  13  83  151  167 
 17  19  29  79  139  149 
 23  31  37  101  113  127 
 41  43  67  71  103  107 
 53  59  61  73  89  97

На третьем этапе каждый такой набор программа пытается превратить в полумагический квадрат, то есть сделать так, чтобы суммы чисел в столбцах тоже были равны магической константе. И уже на последнем этапе попытка превратить полученный полумагический квадрат в магический, то есть получить и в диагоналях магические суммы. Вот такой длинный у меня алгоритм. Программа для этого алгоритма в случае построения традиционных магических квадратов 6-го порядка была написана мной очень давно. Для традиционных квадратов она прекрасно работает.
К третьему этапу ещё не приступала. Однако, ещё неизвестно, получится ли вообще квадрат с магической константой 432. А если и получится, то, может быть, не с таким набором чисел.
Но схему эту можно пробовать и для других констант, и для других наборов простых чисел.
Можно её применить и для построения наименьшего магического квадрата 6-го порядка из смитов.

[Nataly-Mak]

Выполнила третий этап для показанного в предыдущем сообщении набора из 6 строк и магический квадрат получился! Вот он:

3 5 47 109 131 137
89 73 53 97 61 59
151 167 83 7 11 13
71 41 107 103 67 43
17 19 29 79 139 149
101 127 113 37 23 31

Магическая константа квадрата равна 432. Меньше, по-моему, для квадрата 6-го порядка из простых чисел (без использования числа 1) быть не может.
maxal, вы писали, что можно куда-то сообщить о четвёрке минимальных констант магических квадратов из простых чисел порядков 3 - 6. Вот эта четвёрка: $177, 120, 233, 432$.
По этой же схеме попытаюсь построить наименьшие квадраты из смитов 5-го и 6-го порядков.
P. S. Может быть, этот квадрат давно построен?