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

[Nataly-Mak]

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

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

n = 20 S = 107933 существует

Минимальная здесь на единицу меньше - 107932:

Спасибо, это хорошее уточнение. А в остальных (до порядка 28 включительно) не нашлись меньшие константы?

-- Вт окт 20, 2009 11:39:11 --

dezdlisa в сообщении #253208 писал(а):

Нашел самый меньший массив, пока что, для 6-го квадрата. Наталья, не могли бы вы попробовать на своей программке сделать полумагические квадраты?

ORDER=6  MAGIC=2726

4   22  27  265 85  636 
355 378 762 391 274 483 
121 166 202 58  438 319 
645 729 382 825 852 915 
526 648 576 588 627 94  
728 562 654 663 666 690

Я пока не поняла, что это за "самый меньший массив"? Теоретическая минимальная константа для квадрата 6-го порядка из смитов равна 2457. Массив первых 36 смитов: 4, ..., 706. Первая фактическая предполагаемая константа для такого квадрата равна 2460 (замена в массиве числа 706 на 729). Следующих кандидатов я пока не вычисляла. Если ваш массив - один из следующих кандидатов, то выложите все массивы по порядку, начиная сразу после первого кандидата, который приведён мной.

-- Вт окт 20, 2009 12:51:05 --

Вот, например, первые 5 кандидатов в нименьшие магические квадраты 6-го порядка из смитов (исходный массив везде один и тот же - первые 36 смитов, а далее указывается, какие надо произвести замены):

S = 2460   заменить 706 на 729
S = 2467  заменить 663 на 728
S = 2472  заменить числа 690 и 706 на числа 729 и 762
S = 2473  заменить числа 666 и 690 на числа 728 и 729
S = 2475  заменить числа 654 и 690 на числа 728 и 729

Список кандидатов можно продолжить.
Однако нет никакой уверенности в том, что хотя бы для одного из этих массивов магический квадрат существует. Вполне возможно, что наименьший квадрат 6-го порядка из смитов будет иметь такой же большой разброс чисел, какой мы имеем в наименьших квадратах порядков 3 - 5 из смитов. И константу этого квадрата трудно прогнозировать. У меня, например, очень много полумагических квадратов получалось для константы 2787 (я давно уже занимаюсь квадратом 6-го порядка). Эта константа намного больше теоретической минимальной. Какой при этом будет массив смитов, пока не могу сказать: я генерировала полумагические квадраты из разных массивов, кажется, в пределах первых 80 смитов.
Далее, хочу обратить ваше внимание на то, что в этой ветке мной выложена программа генерации набора из n строк из заданного массива чисел для любого порядка. В этом наборе числа во всех строках равны магической константе. Для того, чтобы моя программа генерировала полумагические квадраты, в неё надо ввети такой набор из n строк. Если хотите, я могу выложить и программу генерации полумагических квадратов для порядка 6.
Сейчас работаю с квадратом 10-го порядка из последовательных смитов, первым кандидатом. Он строится из массива: 378, ..., 2839. Магическая константа равна 15681 (напомню, что для второго кандидата магический квадрат мной построен). Уже сгенерировала первую порцию полумагических квадратов в количестве 200 штук и проверила их по программе ice00. Но увы! Пока нет результата. Надо генерировать следующую порцию.

[dezdlisa]

Да, если вас не затруднит, выложите эту программку и укажите пожалуйста на какой страничке программа генерации строк (это тоже нужно).
Попозже, постараюсь составить табличку массивов.

[Nataly-Mak]

dezdlisa в сообщении #253279 писал(а):

Да, если вас не затруднит, выложите эту программку и укажите пожалуйста на какой страничке программа генерации строк (это тоже нужно).
Попозже, постараюсь составить табличку массивов.

Страничку я не помню, а искать у меня нет времени, найдите сами.
Табличку массивов вы можете не составлять, мне она собственно не нужна; когда будет нужна, я составлю сама. Это я сказала к тому, что совершенно не поняла, что за наименьший массив вы представили.
Код программы генерации полумагических квадратов 6-го порядка из готового набора строк (который должен быть сгенерирован прежде по указанной выше программе) выложу попозже.

-- Вт окт 20, 2009 19:48:26 --

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

728  2461 562  1633 1872 1678 852  2265 1736 1894 
2785 2373 2155 391  645  1219 861  2409 922  1921 
2079 913  2218 985  2745 663  2583 762  825  1908 
1165 706  2556 2067 2605 2614 778  588  636  1966 
666  1581 1255 2576 648  2722 2578 1935 1282 438  
729  2326 1111 1626 378  1507 1962 1449 2227 2366 
535  483  895  1822 634  1952 2688 1795 2515 2362 
2434 958  2484 454  2475 1858 576  1642 2173 627  
2679 2038 690  1376 1903 1086 2286 2182 526  915  
1881 1842 1755 2751 1776 382  517  654  2839 1284 

YUPPY!!!!!!!!!!!!!!!!!
ORDER=10  MAGIC=15681

Итак, с квадратами 10-го порядка из смитов задача полностью решена - для обеих групп квадратов.
Попробовала сегодня и построение наименьшего магического квадрата 9-го порядка из произвольных смитов. Тут пока неудача. Сгенерировала 900 полумагических квадратов, и программа не нашла среди них ни одного магического. Чем меньше порядок, тем сложнее решать задачу. Похоже, что для порядка 9 (и меньших порядков) придётся искать новые идеи

[dezdlisa]

Да, на счет массива шестого квадрата: я не с того массива начал поиск. Всетаки даю на всякий случай еще несколько массивов из серии 4...706:

S=2470, заменяем 648 на 728.
S=2476, --/--/-- 648, 690 на 728, 729;
S=2478, --/--/-- 636, 690 на 728, 729

Может быть придется проверять все варианты.

[Nataly-Mak]

Да, с квадратом 9-го порядка всё плохо. Попробовала построить магический квадрат данного порядка из последовательных смитов, для первого кандидата сгенерировала 200 полумагических квадратов, но ни один из них не превратился в магический. Далее провела такой эксперимент: попробовала 5 первых кандидатов по первоначальному варианту программы ice00. Ни один вариант не дал результата. В то время как магический квадрат из последовательных простых чисел строится в долю секунды уже для первого кандидата. Вот этот квадрат:

ORDER=9  MAGIC=2211

197 173 461 433 71  137 277 331 131 
349 191 107 47  443 167 263 307 337 
53  127 449 457 293 257 59  359 157 
467 151 439 139 347 379 83  43  163 
233 67  281 479 79  389 353 101 229 
181 409 37  241 431 179 223 199 311 
251 317 283 103 397 109 383 97  271 
211 463 41  239 61  227 149 401 419 
269 313 113 73  89  367 421 373 193

Вот проверенные мной первые кандидаты в магический квадрат 9-го порядка из последовательных смитов:

27, ..., 2067  S = 9179
58, ..., 2079  S = 9407
85, ..., 2155  S = 9640
94, ..., 2173  S = 9872
121, ..., 2182  S = 10104

Замечу, что и полумагические квадраты для порядка 9 генерируются намного хуже, чем, например, для порядка 10 или 11.
Что мы имеем для квадратов порядка 9 из смитов? Только один составной квадрат, который построил tolstopuz. Один единственный квадрат! Я могла бы построить квадрат из 9 арифметических прогрессий длиной 9 с одинаковой разностью, но у меня нет таких прогрессий. Здесь, кажется, приводилась парочка таких прогрессий. Ещё не найдётся ли у кого-нибудь? Выложите, пожалуйста, если есть.
Идеи по поводу построения наименьших магических квадратов из смитов порядков 6 - 9 не забывайте предлагать

-- Ср окт 21, 2009 14:48:21 --

Воспроизведу составной магический квадрат 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

Для квадратов подобного типа (составленных из 9 квадратов 3х3) это наименьший квадрат. Магическая константа равна $454446$.
Итак, верхняя граница магической константы известна, нижняя тоже: теоретическая минимальная магическая константа квадрата 9-го порядка из смитов равна $8726$. Практически массив удаётся сформировать для константы $8737$.

[maxal]

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

теоретическая минимальная магическая константа квадрата 9-го порядка из смитов равна $8726$. Практически массив удаётся сформировать для константы $8737$.

Для констант меньших $8737$ массива попросту не существует. Можете считать, что $8737$ и есть теоретический минимум.

[Nataly-Mak]

Вчера провела эксперимент для квадратов 6-го порядка из смитов. Как я уже говорила, у меня было много полумагических квадратов с константой 2787. Ещё немного сгенерировала дополнительно, всего получилось 700 штук. Прогнала их все по программе ice00, ничего!
Расскажу о построении единственного известного мне магического квадрата 6-го порядка из смитов. В отличие от других порядков квадрат порядка 6 строится не из арифметических прогрессий, а из последовательностей определённого вида (метод описан в книге Ю. В. Чебракова: он применяет его для построения квадрата 6-го порядка из простых чисел). Я нашла свой набор последовательностей:

a1, a1 + 4b, a1 + 14b, a1 + 15b, a1 + 21b, a1 + 30b
a2, a2 + 4b, a2 + 5b, a2 + 17b, a2 + 24b, a2 + 25b
a3, a3 + 10b, a3 + 16b, a3 + 22b, a3 + 24b, a3 + 30b
a4, a4 + b, a4 + 2b, a4 + 12b, a4 + 13b, a4 + 23b
a5, a5 + 8b, a5 + 14b, a5 + 20b, a5 + 21b, a5 + 24b
a6, a6 + 2b, a6 + 9b, a6 + 10b, a6 + 15b, a6 + 21b

Здесь все $ai$ – числа cмита, параметр $b$ – произвольное натуральное число, все члены последовательностей тоже должны быть смитами.
Три из этих последовательностей – для а1, а2 и а6 я нашла сама, три оставшиеся нашёл Mathusic. Это найденные мной последовательности:

1822 1966 2326 2362 2578 2902
20362 20506 20542 20974 21226 21262
22 94 346 382 562 778

Параметр $b = 36$.
Это последовательности, которые нашёл Mathusic (для а3, а4 и а5 соответственно):

681817 682177 682393 682609 682681 682897
1446106 1446142 1446178 1446538 1446574 1446934
3003898 3004186 3004402 3004618 3004654 3004762

Магический квадрат, построенный из этих последовательностей:

1822 21226 682897 1446538 3003898 382
3004762 681817 778 2326 1446574 20506
1446142 2902 3004654 20542 346 682177
21262 1446178 1966 562 682393 3004402
94 3004618 1446106 682609 20974 2362
682681 22 20362 3004186 2578 1446934

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

В книге Чебракова используется такой набор последовательностей:

a1, a1 + 7b, a1 + 9b, a1 + 12b, a1 + 24b, a1 + 26b
a2, a2 + 7b, a2 + 13b, a2 + 21b, a2 + 24b, a2 + 28b
a3, a3 + 2b, a3 + 6b, a3 + 8b, a3 + 16b, a3 + 28b
a4, a4 + 12b, a4 + 15b, a4 + 17b, a4 + 20b, a4 + 23b
a5, a5 + b, a5 + 3b, a5 + 11b, a5 + 13b, a5 + 17b
a6, a6 + 10b, a6 + 17b, a6 + 20b, a6 + 23b, a6 + 29b

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

Ещё просьба: если кому-то известны другие магические квадраты 6-го порядка из смитов, сообщите, пожалуйста. Нам нужен ориентир для минимальной магической константы такого квадрата – её верхняя граница. Теоретическая нижняя граница известна – $2460$.

[Mathusic]

Вот ссылка на эти последовательности. Не проверял минимальность Вашего квадрата, Nataly.

[Nataly-Mak]

Судя по ссылке, вы предложили файл, выложенный на форуме Портала ЕН. Удивительно, что этот Портал "отдал" мне файл
Но я думала, что вы уже предлагаете новые последовательности, а это старые. Они у меня уже есть. Сейчас я их все просмотрела, похоже, что представленный квадрат наименьший из всех, какие можно построить из найденных вами последовательностей.
Новая задача была найти последовательности другого вида (из книги Ю. В. Чебракова). Эти последовательности отличаются от моих последоваетельностей по своей структуре. Не следует искать так много последовательностей (как вы сделали это в прошлый раз), достаточно найти один набор с минимальными значениями всех членов последовательностей.

[Mathusic]

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

Судя по ссылке, вы предложили файл, выложенный на форуме Портала ЕН. Удивительно, что этот Портал "отдал" мне файл
Но я думала, что вы уже предлагаете новые последовательности, а это старые. Они у меня уже есть. Сейчас я их все просмотрела, похоже, что представленный квадрат наименьший из всех, какие можно построить из найденных вами последовательностей.
Новая задача была найти последовательности другого вида (из книги Ю. В. Чебракова). Эти последовательности отличаются от моих последоваетельностей по своей структуре. Не следует искать так много последовательностей (как вы сделали это в прошлый раз), достаточно найти один набор с минимальными значениями всех членов последовательностей.

А у Вам даже чтение сайта запрещено? Попробуйте просматривать через прокси-сервер. Может получиться (только никому ладно? )

-- Чт окт 22, 2009 14:44:05 --

Кстати, кажется для $b=90$ есть набор меньше

611005,611365,612265,612355,612895,613705,
5935,6295,6385,7465,8095,8185,
59415,60315,60855,61395,61575,62115,
762115,762205,762295,763195,763285,764185,
611095,611815,612355,612895,612985,613255,
521905,522085,522715,522805,523255,523795,

Только жаль, есть повторы (а я то думал, почему Вы его не выбрали)

[Nataly-Mak]

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

А у Вам даже чтение сайта запрещено? Попробуйте просматривать через прокси-сервер. Может получиться (только никому ладно? )

Да, был закрыт даже просмотр. Мне давно говорили о прокси, но конкретно не давали ссылку. Спасибо вам! Всё получилось, форум просмотрела.
А вы меня умилили Даёте ссылку на форуме и при этом по секрету. По секрету - всему свету. Я знаю, что многие с того форума этот форум просматривают.
Мне сначала друзья присылали копии страниц, но потом я не стала их больше загружать этой работой, тем более что в интересующих меня темах нового ничего не появляется.
Конечно, мне больше всего интересны две темы: "Латинские и магические квадраты" и "Числа Смита", но там после моего ухода ничего не появилось. Некому эти темы развивать Впрочем, это отступление от темы, то есть оффтоп.
Сегодня опять работала с квадратами 9-го порядка. Результатов нет! Решила выложить файл, в котором 913 полумагических квадратов (это квадраты с магической константой 8737). Подумать только: почти тысяча полумагических квадратов и ни один не превратился в магический. Все желающие могут попробовать прогнать эти квадраты по программе ice00. Вдруг у кого-то получится Я вроде даже все методы попробовала, точнее: с3, d3, a3 и b2.
Файл здесь.
Далее, кто-нибудь из интересующихся может попробовать сделать свою программу превращения полумагических квадратов в магические. Мне не совсем понятно, каким методом делает это ice00, хотя он мне и ответил на этот вопрос, но как-то неопределённо. Я знаю, например, такой метод: сделать полную перестановку всех строк и столбцов. В квадрате 9-го порядка это вполне реально (но не на Бейсике, конечно). У ice00 явно другие методы, потому что у него, к примеру, нарушаются суммы чисел в строках после того, как он сделает диагонали. При перестановке строк и столбцов такого не произойдёт. Можно придумать и другие методы, если хорошо подумать. Как-то же надо построить этот квадрат, если, конечно, он существует
Ещё поработала с квадратами 6-го порядка. И здесь смиты не хотят складываться в последовательности. Для последовательностей из книги Ю. В. Чебракова (см. предыдущий пост) нашла только одну последовательность из шести - для а3:

58 94 166 202 346 562

Значение параметра $b = 18$. Поэтому теперь просьба к тем, кто захочет найти оставшиеся пять последовательностей, искать их для того же значения параметра $b$.
Составила аналогичные последовательности на основе сотового магического квадрата 6-го порядка. Никакой особой гармонии не полчилось. Вот эти последовательности:

a1, a1+10b, a1+20b, a1+22b, a1+24b, a1+27b
a2, a2+7b, a2+14b, a2+18b, a2+26b, a2+28b
a3, a3+3b, a3+5b, a3+8b, a3+14b, a3+26b
a4, a4+10b, a4+14b, a4+18b, a4+23b, a4+25b
a5, a5+4b, a5+7b, a5+13b, a5+14b, a5+21b
a6, a6+11b, a6+12b, a6+18b, a6+20b, a6+24b

Для смитов не нашла с ходу ни одной последовательности. А для простых чисел таких последовательностей море. Вот, например, при значении параметра $b = 30$:

13 313 613 673 733 823
47 257 467 587 827 887
41 131 191 281 461 821
37 337 457 577 727 787
29 149 239 419 449 659
1069 1399 1429 1609 1669 1789

И вот магический квадрат, построенный из этих последовательностей:

13 47 821 457 659 1669
149 191 1789 613 337 587
727 823 449 467 1069 131
887 787 313 1609 41 29
1429 41937 281 827 673
461 1399 257 239 733 577

И магическая константа квадрата довольно маленькая получается - $3666$ (красивая к тому же). Но для простых чисел наименьший квдарат 6-го порядка давно построен. А вот для смитов ничего не получается!
Теперь уже есть задача для двух наборов последовательностей. Но вряд ли удастся этим методом получить квадрат с маленькой магической константой.

[ice00]

Squares for consecutive primes now completed up to this order:

*** ORDER: 51   - SEQ(119)       FROM: 653        MAGIC=613837
*** ORDER: 52   - SEQ(195)       FROM: 1187       MAGIC=688404
*** ORDER: 53   - SEQ(15)        FROM: 47         MAGIC=640571
*** ORDER: 54   - SEQ(13)        FROM: 41         MAGIC=679584
*** ORDER: 55   - SEQ(12)        FROM: 37         MAGIC=720739
*** ORDER: 56   - SEQ(7)         FROM: 17         MAGIC=761542
*** ORDER: 57   - SEQ(114)       FROM: 619        MAGIC=863609

Here the windows program:

http://www.4shared.com/file/142768990/59a9c6b1/pms51-57.html

[Nataly-Mak]

ice00
Поздравляю! У вас хорошие результаты.
А у меня ничего не получается
Если у вас есть немного времени, пожалуйста, проверьте мои полумагические квадраты 9-го порядка (ссылка в предыдущем посте). Может быть, у вас найдётся хоть один магический квадрат. У меня не нашёлся. Даже не верится, что из 913 полумагических квадратов ни один не может превратиться в магический. Хотя теоеретически это вполне возможно.
Приглашаю вас также подумать над другими методами построения наименьших магических квадратов порядков 6 - 9 из смитов. Как же их всё-таки построить?

[ice00]

I checked yesterday the >900 order 9 squares you put on file, but without positive result.
I have in mind some ideas that with a relative small order like 6 could be try to see if they can give some result. This kind of idea I had implemented (but not used) to see if a order 4 square of prime numbers can be constructed. Maybe extending it I can look if it possible to have some result from it, but now it is a little more early for being happy about this idea.

[Nataly-Mak]

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

4, ... , 576  S = 1516
454, ..., 861 S = 3269
535, ... , 922 S = 3602
861, ... , 1776  S = 6522
915, ... , 1842  S = 7080
1086, ..., 1894  S = 7825

Если верить Бодигриму, первый кандидат исключается автоматически, так как наименьший квадрат 5-го порядка из смитов имеет константу $1831$. Я раньше пробовала построить квадрат из первого варианта массива по своей программе, у меня тоже такой квадрат не построился.
Для остальных пяти кандидатов программа pms5 вела себя так, как я сказала выше: она запускается и долго-долго ничего не выдаёт. Что в ней происходит, одному Богу известно. Приходилось просто прерывать программу. Я не получила ни одного результата для этих вариантов. Вполне возможно, что все эти квадраты просто не существуют, но никакой уверенности в этом нет.
Проделала такой эксперимент ради интереса: ввела в качестве исходного массива первые 25 натуральных чисел, программа в этом случае мгновенно построила традиционный магический квадрат.
Вот такие у меня плохие успехи