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

[Nataly-Mak]

Ого! Вот спасибо! С таким массивом можно поработать.
У вас есть программа генерации смитов? Тоже хотела её написать, но пошла по простейшему пути (умножение простых чисел на $n$). Как часто бывает, простейший путь оказывается самым длинным.

[tolstopuz]

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

У вас есть программа генерации смитов?

Да там двадцать строк, это самая легкая часть задачи.

[Бодигрим]

tolstopuz в сообщении #229640 писал(а):

Я надеюсь, вы перебираете только два числа помимо магической константы?

М-да, два года кодинга на PHP (когда привыкаешь скорее программировать, а не думать) явно не пошли мне на пользу. Я перебирал четыре числа, не считая магической константы.

Сейчас написал другой алгоритм - перебираю четыре числа, но не перебираю магическую константу. На моем Celeron 2400 программа укладывается в 1.5 секунды.

А каким образом вы перебираете только два элемента и константу?

[tolstopuz]

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

А каким образом вы перебираете только два элемента и константу?

Константа равна утроенной центральной клетке. Дальше берем, например, первые две клетки верхней строки, остальные считаются через эти три.

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

На моем Celeron 2400 программа укладывается в 1.5 секунды.

У вас большая фора, паскаль - компилируемый язык

[Nataly-Mak]

Если не ошиблась в вычислениях, нетрадиционный пандиагональный (а значит, совершенный) магический квадрат 4-го порядка из простых чисел, образующих арифметическую прогрессию, получается такой:

341976204789992332577 2735809638319938660497 4445690662269900323297 4103714457479907990737
4787666867059892655857 3761738252689915658177 683952409579984665137 2393833433529946327937
1367904819159969330257 1709881023949961662817 5471619276639877320977 3077785843109930993057
5129643071849884988417 3419762047899923325617 1025928614369976997697 2051857228739953995377

Магическая константа квадрата равна 11627190962859739307108.

-- Пт июл 17, 2009 21:56:49 --

До кучи приведу нетрадиционные магические квадраты 3-го порядка из простых чисел, образующих арифметическую прогрессию.
По указанной ссылке взяла две прогрессии из 9 членов.
Первая прогрессия: 199 + 210*n, n=0, 1, … , 8.
Магический квадрат получается такой:

829 1879 409
619 1039 1459
1669 199 1249

Магическая константа квадрата равна 3117.
Вторая прогрессия: 11 + 155577*7#*n, n = 0, 1, … , 8.
Магический квадрат из членов этой прогрессии:

98013521 261369371 32671181
65342351 130684691 196027031
228698201 11 163355861

Магическая константа этого квадрата равна 392054073.
А теперь задача: можно ли составить аналогичные квадраты 3-го порядка из составных смитов?

[Бодигрим]

tolstopuz в сообщении #229694 писал(а):

Константа равна утроенной центральной клетке.

Хм, не знал.

Что любопытно - оптимизация с четырех вложенных циклов до трех ускорило программу незначительно, где-то раза в полтора. Укладывается за секунду :) Я вот думаю, через компилятор Delphi прогнать, а то FreePascal ему существенно проигрывает по оптимизации компилированного кода.

Теперь за 5 минут находятся все квадраты из смитов до 100000. Приводившаяся в предыдущем сообщении база была исправлена: http://grafline.com.ua/uploads/smiths2.log.

Upd.: Да, Delphi компилирует лучше: программа работает вдвое быстрее.

[Nataly-Mak]

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

Квадрат порядка 3 из смитов, магическая константа которого тоже является смитом, построить можно, если иметь очень большой массив смитов.
У меня на настоящий момент этот массив содержит 196 чисел. Составив простенькую программку, я определила все те смиты, которые остаются смитами после утроения. В моём массиве нашлось всего 6 таких смитов: $636,654,762,852,1284,8466$. Далее у меня есть программа построения магического квадрата 3х3 из смитов по заданной магической константе (эта программа приведена в статье Нетрадиционные магические квадраты из простых чисел). По этой программе магический квадрат удалось построить только для магической константы $25398=8466*3$. Для остальных значений магических констант квадраты не построились.

Бодигрим, а это сообщение вы не читали? Или просто совсем не вникали? Если бы вникли, то поняли бы, что магическая константа любого квадрата 3-го порядка равна утроенному элементу, находящемуся в центральной ячейке. Всякий магический квадрат 3-го порядка ассоциативен, то есть сумма любых двух элементов, симметрично расположенных относительно центра квадрата, равна одному и тому же числу, это число равно удвоенному центральному элементу. Впрочем, об этом подробно говорилось в одном из моих сообщений много выше (в этой ветке).
А вот для меня было открытием (спасибо tolstopuz'у), что в любом магическом квадрате 4-го порядка сумма четырёх центральных элементов равна магической константе.

[tolstopuz]

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

А вот для меня было открытием (спасибо tolstopuz'у), что в любом магическом квадрате 4-го порядка сумма четырёх центральных элементов равна магической константе.

У Чебракова, кстати, это тоже есть.

[Nataly-Mak]

Книгу Чебракова я читала по диагонали, выбирая самое для меня интересное. Этот момент пропустила.

[Бодигрим]

tolstopuz в сообщении #227955 писал(а):

С константой 1195 больше нет, а вообще тысячи их.

Таки да, я отладил предлагаемую вами к написанию программу и она выдает их просто море. Вот начало листинга, и это даже не 1/32000 всего набора.

[Nataly-Mak]

Есть ли в этом море хоть один квадрат 4х4 из разных составных смитов, элементы которого образуют арифметическую прогрессию? Есть ли такой квадрат порядка 3?

[tolstopuz]

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

tolstopuz в сообщении #227955 писал(а):

С константой 1195 больше нет, а вообще тысячи их.

Таки да, я отладил предлагаемую вами к написанию программу и она выдает их просто море. Вот начало листинга, и это даже не 1/32000 всего набора.

Задачу, кстати, предложила Nataly-Mak.

Только, пожалуйста, если вы вдруг найдете четыре таких квадрата с одинаковой константой и непересекающимися множествами чисел, не публикуйте их нигде, в частности в этой ветке, лучше обменяемся ими в ЛС. Я все еще надеюсь, что эту задачу примут на projecteuler, а выяснится это где-то к осени.

[Бодигрим]

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

Есть ли в этом море хоть один квадрат 4х4 из разных составных смитов, элементы которого образуют арифметическую прогрессию? Есть ли такой квадрат порядка 3?

Я ведь верно понимаю, что по сути ваш вопрос сводится к существованию среди составных чисел Смита арифметических прогрессий длины 16 и 9 соответственно?

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

9895 139765 269635 399505 529375 659245 789115 918985 1048855

[Nataly-Mak]

Замечательно! Вероятно, вы первый, кто нашёл такую прогрессию из чисел-смитов. Ваша прогрессия даже длины 10. В книге Чебракова есть такая задача: определите, сколько магических квадратов 3х3 можно построить из $K$ натуральных чисел, образующих арифметическую прогрессию. (стр. 215)
Если $K$ равно 9, то можно построить всего один квадрат (с точностью до основных преобразований). Какой ответ при $K>9$?
Думаю, что из вашей прогрессии длиной 10 можно построить 2 разных квадрата. Вот один из них:

399505 1048855 139765
269635 529375 789115
918985 9895 659245

Квадрат построен на основе магического квадрата Ло Шу.
Если бы прогрессия была большей длины, тогда можно было бы ещё построить квадраты.
Предлагаю всем решить эту задачу для квадратов 4х4 из разных составных смитов. Для этого надо найти арифметическую прогрессию из составных смитов длиной 16.
А это новая задача: построить составной квадрат 9х9 (состоящий из 9 квадратов 3х3) из разных составных чисел-смитов.

[tolstopuz]

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

А это новая задача: построить составной квадрат 9х9 (состоящий из 9 квадратов 3х3) из разных составных чисел-смитов.

Минимальная константа оказалась очень красивой - 454446. Решение не единственно, но, к сожалению, без чисел меньше 100000 обойтись нельзя.

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

А из чисел меньше 100000 собирается квадрат с константой 339102 и одним повторяющимся числом 34582.

-- Вс июл 19, 2009 12:27:12 --

Я проверил составные квадраты 9x9 из простых чисел - чебраковские действительно минимальны.