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

[Nataly-Mak]

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

Я только что пробовал для квадрата 6-го порядка, массив 346...958, ни одним способом программа не построила магического квадрата.
Очень жаль, значит массив скорее всего должен быть не последовательным.
Напишите программку, которая будет подбирать пары чисел, дающие одинаковые заданные суммы из также заданного массива. Может так мы сможем составить для четных вариантов определенный массив?

Уважаемый dezdlisa!
Было бы хорошо, есди бы вы хоть немного ознакомились с темой, прежде чем приступать к решению нерешённых задач. Я уже неоднократно писала здесь, что для порядков 6 - 10 программы ice00 не дают результатов. Вы снова открываете Америку.
Последний наименьший квадрат из смитов, который мне удалось построить по программе ice00, имеет порядок 11. Этот квадрат здесь приведён. ice00 построил по своей программе наименьший квадрат 11-го порядка из последовательных смитов.
Теперь я пытаюсь построить наименьший квадрат 10-го порядка из произвольных смитов (из последовательных смитов квадрат данного порядка мной построен по своей программе; об этом тоже здесь сообщалось). Пока это у меня не получается, ни моя программа, ни программа ice00 не дают результата.
Квадрат 6-го порядка из последовательных смитов может существовать, но с другим массивом. Вы проверили только один массив. Кроме того: то, что магический квадрат не получен по программе, ещё не означает, что такой квадрат не существует. Насколько я понимаю, однозначный ответ можно дать только для порядков 3 и 4, так как в программах для этих порядков выполняется полный перебор всех вариантов.
Ещё раз советую вам посмотреть всё, что сделано в данной теме, чтобы не повторять то, что здесь уже было не раз сказано.
И кому это вы даёте задание "напишите программку..."?

[dezdlisa]

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

[Nataly-Mak]

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

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

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

[dezdlisa]

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

[Nataly-Mak]

Никак не получается наименьший магический квадрат 10-го порядка из смитов И с константой 12206 попробовала, и с константой 12209 - ничего!
Тогда решила продолжить в сторону больших порядков, здесь всё отлично получается. Построила до порядка 28 включительно:

n = 21  S = 126404  (126400)
n = 22  S = 147816  (147815)
n = 23  S = 171556  (171552)
n = 24  S = 197041  (197031)
n = 25  S = 224506  (224500)
n = 26  S = 253587  (253584)
n = 27  S = 285314  (285305)
n = 28  S = 320620  (320617)

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

[ice00]

Program created and many squares pop out from the list of 202 input squares:

ORDER=10  MAGIC=12202

648  166  355  2362 27   1284 627  2038 2409 2286
1736 588  2218 1255 922  1626 1111 1908 636  202
861  1903 517  1086 1935 2366 382  762  438  1952
1449 1921 1822 1642 483  4    2326 666  94   1795
778  562  2461 576  1966 1872 391  958  2373 265
2484 913  706  2173 645  654  852  1881 1165 729
2155 535  2079 1962 1678 319  1894 663  22   895
1219 2265 85   454  121  915  1776 2227 1507 1633
526  1282 378  58   2583 2434 985  825  1376 1755
346  2067 1581 634  1842 728  1858 274  2182 690

YUPPY!!!!!!!!!!!!!!!!!


ORDER=10  MAGIC=12202

861  1903 517  1086 1935 2366 382  762  438  1952
1736 588  2218 1255 922  1111 1626 1908 636  202
454  1633 121  1507 1219 1776 85   2227 915  2265
1449 1921 1822 1642 483  4    2326 666  94   1795
778  562  2461 576  1966 1872 958  391  2373 265
1881 2173 645  706  729  852  2484 1165 654  913
2182 1858 346  274  1842 690  634  728  2067 1581
2155 22   1962 535  319  2079 895  1894 1678 663
648  166  355  2038 2409 627  2286 27   2362 1284
58   1376 1755 2583 378  825  526  2434 985  1282

YUPPY!!!!!!!!!!!!!!!!!

I just report two of them here

[Nataly-Mak]

Ура-а-а-а!
ice00
Неужели все мои 202 полумагических квадрата превратились в магические?! Это фантастика! Ваша программа просто супер. Празднуем победу Очень вас благодарю. Вы блестяще завершили мой труд над этим квадратом.
Переходим к квадрату 9-го порядка

[dezdlisa]

ice00, если я правильно понял, то вы эти полумагические квадраты прогоняли на pms10?
(вижу что массив немного изменен)
Или есть еще какие-то сторонние ресурсы о которых нам (мне) неизвестно?

[ice00]

Цитата:

Неужели все мои 202 полумагических квадрата превратились в магические?!

No, not all. In the 202 squares, 9 are turned full magic, that is less of 5%

Цитата:

ice00, если я правильно понял, то вы эти полумагические квадраты прогоняли на pms10?
(вижу что массив немного изменен)
Или есть еще какие-то сторонние ресурсы о которых нам (мне) неизвестно?

It is done with the new program:

http://www.4shared.com/file/141983331/ba05d9f6/pmsd2_6-10.html

Now the input sequence in file must be a sequence of squares (at least 1 must be present). It tests all the squares and prints only the one that are magic.

Use method $C3$ and if not working, try at least $A3$, $B3$, $D3$

[Nataly-Mak]

ice00
Программы получила, большое спасибо. Программу для квадрата порядка 10 уже попробовала, проверила свои 202 полумагических квадрата. Да, получилось 9 магических квадратов. Но нам и одного было бы достаточно Вот покажу последний магический квадрат:

ORDER=10  MAGIC=12202

2182 627  274  1921 2484 1755 391  895  1111 562  
2461 654  634  1678 1872 663  588  636  2155 861  
2079 2326 94   483  265  913  2583 1822 355  1282 
690  1736 1966 728  922  1858 778  1284 202  2038 
2218 1507 2067 454  22   378  1935 2362 1255 4    
27   762  2286 2265 2373 1962 1165 58   958  346  
852  1633 121  1903 166  1642 576  1908 1449 1952 
438  645  985  1626 706  535  2434 1776 648  2409 
526  517  1894 825  2173 1581 1086 1376 1842 382  
729  1795 1881 319  1219 915  666  85   2227 2366 

Здорово! Завтра проверю первого кандидата в наименьший магический квадрат 10-го порядка из последовательных смитов (думаю, что он тоже даст магический квадрат), а потом примусь за квадрат 9-го порядка.
Однако, почему же всё-таки ваша программа в первоначальном варианте для порядка 10 (и меньших порядков) не даёт результата?

[ice00]

Цитата:

Однако, почему же всё-таки ваша программа в первоначальном варианте для порядка 10 (и меньших порядков) не даёт результата?

With low number of solution (maybe for Smith there are no so many square for low order) and starting with a random square, the probability to have a square that can be made magic with the rearrange that I made in row/column is very very little (instead the space of solution for a 6x6 order is extreme big). The type or rearrange was choose for be efficient (as this was enought for primes number).

If I modify the rows/columns rearrange maybe I could find another method of solution that can work even with this kind of square. But this require to test some idea that I did not have jet full analyzed..

[maxal]

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

n = 7 S = 3720 ?
Минимальность магических констант, начиная с порядка 6, надо проверить.

Для n=7 теоретически минимальная константа равна 3719. Набор смитов для нее такой:
4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 915, 922, 958, 985, 1086

-- Mon Oct 19, 2009 21:14:48 --

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

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

Я расширил поиск до $10^{10}$ - квадрата $3\times 3$ из последовательных смитов не нашлось.

[Nataly-Mak]

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

Для n=7 теоретически минимальная константа равна 3719. Набор смитов для нее такой:
4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 915, 922, 958, 985, 1086

Спасибо, что проверили, но для порядка 7 я уже обнаружила ошибку, вот была уточнённая и дополненная таблица вскоре после первого варианта таблицы (post252093.html#p252093)

n = 3   S = 822   существует (книга М. Гарднера)
n = 4   S = 1195   существует (tolstopuz)
n = 5   S = 1831   существует (Бодигрим)      
n = 6    S = 2460   ?
n = 7   S = 3719   ?
n = 8   S = 5856   ?
n = 9   S = 8737   ?
n = 10   S = 12202   существует (Nataly-Mak, ice00)
n = 11   S = 16335   существует (Nataly-Mak)   два варианта массива
n = 12   S = 21333   существует (Nataly-Mak)
n = 13   S = 27612   существует
n = 14   S = 35185   существует         два варианта массива
n = 15   S = 43968    существует
n = 16   S = 54013   существует         два варианта массива
n = 17 S = 65464   существует
n = 18 S = 78281   существует
n = 19 S = 92422   существует
n = 20 S = 107933   существует

Кстати, сейчас ввела ещё уточнение в таблицу: теперь известны и квадраты порядков 10 и 11. А чуть выше приведено продолжение таблицы для порядков 21 - 28.
Вопрос: можно ли создать последовательность в OEIS из магических констант наименьших магических квадратов из чисел Смита, если в ней будет такой пробел с четырьмя неизвестными константами? Я уже написала письмо главному редактору Энциклопедии, но пока ответ не получен. Всё осложняется тем, что я пишу по-русски.
Да, видимо, в магических квадратах порядков 3 и 4 из последовательных смитов будут очень большие числа.

-- Вт окт 20, 2009 07:48:36 --

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

With low number of solution (maybe for Smith there are no so many square for low order) and starting with a random square, the probability to have a square that can be made magic with the rearrange that I made in row/column is very very little (instead the space of solution for a 6x6 order is extreme big). The type or rearrange was choose for be efficient (as this was enought for primes number).

If I modify the rows/columns rearrange maybe I could find another method of solution that can work even with this kind of square. But this require to test some idea that I did not have jet full analyzed..

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

[maxal]

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

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

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

[4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111, 1165, 1219, 1255, 1282, 1284, 1376, 1449, 1507, 1581, 1626, 1633, 1642, 1678, 1736, 1755, 1776, 1795, 1822, 1842, 1858, 1872, 1881, 1894, 1903, 1908, 1921, 1935, 1952, 1962, 1966, 2038, 2067, 2079, 2155, 2173, 2182, 2218, 2227, 2265, 2286, 2326, 2362, 2366, 2373, 2409, 2434, 2461, 2475, 2484, 2515, 2556, 2576, 2578, 2583, 2605, 2614, 2679, 2688, 2722, 2745, 2751, 2785, 2839, 2888, 2902, 2911, 2934, 2944, 2958, 2964, 2965, 2970, 2974, 3046, 3091, 3138, 3168, 3174, 3226, 3246, 3258, 3294, 3345, 3366, 3390, 3442, 3505, 3564, 3595, 3615, 3622, 3649, 3663, 3690, 3694, 3802, 3852, 3864, 3865, 3930, 3946, 3973, 4054, 4126, 4162, 4173, 4185, 4189, 4191, 4198, 4209, 4279, 4306, 4369, 4414, 4428, 4464, 4472, 4557, 4592, 4594, 4702, 4743, 4765, 4788, 4794, 4832, 4855, 4880, 4918, 4954, 4959, 4960, 4974, 4981, 5062, 5071, 5088, 5098, 5172, 5242, 5248, 5253, 5269, 5298, 5305, 5386, 5388, 5397, 5422, 5458, 5485, 5526, 5539, 5602, 5638, 5642, 5674, 5772, 5818, 5854, 5874, 5915, 5926, 5935, 5936, 5946, 5998, 6036, 6054, 6084, 6096, 6115, 6171, 6178, 6187, 6188, 6252, 6259, 6295, 6315, 6344, 6385, 6439, 6457, 6502, 6531, 6567, 6583, 6585, 6603, 6684, 6693, 6702, 6718, 6760, 6816, 6835, 6855, 6880, 6934, 6981, 7026, 7051, 7062, 7068, 7078, 7089, 7119, 7136, 7186, 7195, 7227, 7249, 7287, 7339, 7402, 7438, 7447, 7465, 7503, 7627, 7674, 7683, 7695, 7712, 7726, 7762, 7764, 7782, 7784, 7809, 7824, 7834, 7915, 7952, 7978, 8005, 8014, 8023, 8073, 8077, 8095, 8149, 8154, 8158, 8185, 8196, 8253, 8257, 8277, 8307, 8347, 8372, 8412, 8421, 8466, 8518, 8545, 8568, 8628, 8653, 8680, 8736, 8754, 8766, 8790, 8792, 8851, 8864, 8874, 8883, 8901, 8914, 9015, 9031, 9036, 9094, 9166, 9184, 9193, 9229, 9274, 9276, 9285, 9294, 9296, 9301, 9330, 9346, 9355, 9382, 9386, 9387, 9396, 9414, 9427, 9483, 9522, 9535, 9571, 9598, 9633, 9634, 9639, 9648, 9657, 9684, 9708, 9717, 9735, 9742, 9760, 9778, 9840, 9843, 9849, 9861, 9880, 9895, 9924, 9942, 9968, 9975, 9985, 10086, 10201, 10291, 10296, 10419, 10462, 10489, 10494, 10579, 10592, 10606, 10664, 10669, 10689, 10698, 10705, 10736, 10786, 10791, 10797, 10806, 10845, 10966, 11065]

[dezdlisa]

Нашел самый меньший массив, пока что, для 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