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

[Nataly-Mak]

maxal
ещё раз о моих экспериментах с набором из 18 комплементарных пар из смитов с суммой в паре 4400:

94 4306 121 4279 202 4198 274 4126 346 4054 454 3946 535 3865 706 3694 778 3622 895 3505 958 3442 1678 2722 1795 2605 1822 2578 1966 2434 2038 2362 2173 2227 2182 2218

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

2. По своей старой программе сгенерировала все 3616 упорядоченных строк с суммой чисел в строке равной магической константе квадрата.
Программа 12d3 даёт такое же количество строк.

Далее у меня есть программа, которая из сгенерированных строк формирует наборы по 6 строк, состоящие из различных чисел. К сожалению, Бейсик не берёт такой большой массив строк, поэтому не могу выполнить программу. Можно было бы посмотреть на полученные наборы из 6 строк: имеются ли среди них такие, из которых может составиться ассоциативный квадрат. Это дало бы точный ответ на вопрос.

Может быть, эти идеи быстрее приведут к ответу на поставленный вопрос о возможности составления из заданного массива чисел ассоциативного квадрата 6-го порядка, чем вычисления по программе построения?

[Nataly-Mak]

Сделала хитрый финт и удалось сгенерировать 7 наборов по 6 строк из различных чисел так, что в каждой строке нет комплементарных чисел.
Не уверена, правда, что получила все наборы. Показываю три набора:

94  274  1966  2722  3865  4279 
 121  202  895  3622  4054  4306 
 346  454  2182  2578  3442  4198 
 535  778  1822  2434  3505  4126 
 706  1678  2038  2227  2605  3946 
 958  1795  2173  2218  2362  3694 

 94  706  1678  2578  3946  4198 
 121  202  895  3622  4054  4306 
 274  346  2173  2434  3694  4279 
 454  535  2038  2605  3442  4126 
 778  1795  1822  2218  2722  3865 
 958  1966  2182  2227  2362  3505 

 94  778  1966  2218  3865  4279 
 121  202  895  3622  4054  4306 
 274  535  2173  2578  3442  4198 
 346  706  1795  2722  3505  4126 
 454  2038  2182  2227  2605  3694 
 958  1678  1822  2362  2434  3946

Ни один из полученных наборов не годится для построения ассоциативного квадрата.

[svb]

Маленькое замечание.

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

maxal
ещё раз о моих экспериментах с набором из 18 комплементарных пар из смитов с суммой в паре 4400:

94 4306 121 4279 202 4198 274 4126 346 4054 454 3946 535 3865 706 3694 778 3622 895 3505 958 3442 1678 2722 1795 2605 1822 2578 1966 2434 2038 2362 2173 2227 2182 2218

Пусть мы рассматриваем набор из комплементарных пар, расположим все числа по возрастанию: $a[1],a[2],...,a[n^2 ] $, ясно, что все суммы $a[i] + a[n^2 + 1 - i] $ равны между собой и равны сумме комплементарной пары (4400 в приведенном наборе). Обозначим через $s1 $ сумму первых $n^2 /2 $ чисел (19017 в нашем случае). Теперь попробуем обменивать числа в коплементарных парах. Каждый такой обмен чисел $a[i]$ и $a[n^2 + 1 - i]$ приводит к увеличению суммы $s1$ на величину $a[n^2 + 1 - i]-a[i]$, выпишем эти числа:

4212 4158 3996 3852 3708 3492 3330 2988 2844 2610 2484 1044 810 756 468 324 54 36 

Для того, чтобы сработал алгоритм Наталии, необходимо добиться, чтобы сумма $s1$ стала равной 39600, т.е. начальную сумму 19017 мы должны увеличить на 20583. Задача сводится к знаменитой задаче о рюкзаке - из последнего приведенного набора чисел набрать сумму 20583. Для данного конкретного случая, к сожалению, это невозможно, т.к. нечетную сумму не составить из четных чисел.

[Nataly-Mak]

svb
изящное доказательство!

Применила ваши рассуждения к другому набору из 18 комплементарных пар:

22  58  121  265  526  958  1165  1282  1642  1822  1858  2038  2155  2218  2362  2605  3046  3595  
3865  4414  4855  5098  5242  5305  5422  5602  5638  5818  6178  6295  6502  6934  7195  7339  7402  7438

$S1 = 27738$, надо сделать сумму $67140$, то есть увеличить $S1$ на $39402$.

Разности в комплементарных парах:

270 1368 2250 2736 3024 3150 3384 3744 3816 4176 4896 5130 5544 6408 6930 7218 7344 7416

Нужная сумма $39402$ набирается, например, так:

270 + 1368 + 2250 + 3150 + 5130 + 5544 + 6930 + 7344 + 7416

Как я поняла, это необходимое условие. Правильно?
То есть из данного набора комплементарных пар ассоциативный квадрат 6-го порядка может построиться, но не обязательно построится.

[Nataly-Mak]

Пока с ассоциативным квадратом 6-го порядка из смитов ничего не получается, решила попробовать строить ассоциативные квадраты 5-го порядка из простых чисел, находя для этого комплементарные пары.
Первый потенциальный массив нашёлся из 12 комплементарных пар с суммой в паре 466:

3 5 17 23 47 83 107 113 149 173 197 227 239 269 293 317 353 359 383 419 443 449 461 463 233

(сначала идут комплементарные пары, а последним записано число, которое будет находиться в центральной ячейке квадрата; это число равно половине константы ассоциативности квадрата).

Из этого массива у меня не построился ассоциативный квадрат.
Следующий кандидат – набор из 14 комплементарных пар с суммой в паре 502:

3  11  23  41  53  59  71  83  101  113  149  191  233  239  263  269  311  353  389  401  419  431  443  449  461  479  491  499  251

Из этого массива ассоциативный квадрат построился сразу:

11 263 101 431 449
443 149 389 41 233
479 311 251 191 23
269 461 113 353 59
53 71 401 239 491

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

Итак, мы имеем наименьшие ассоциативные квадраты из простых чисел порядков 3 – 6.
Квадрат 4-го порядка я давно построила (он здесь был показан). Квадрат 6-го порядка совсем недавно построен; я его вообще-то строила для того, чтобы получить из него пандиагональный квадрат. Ну, а квадрат 3-го порядка – это и есть наименьший магический квадрат из простых чисел; он ассоциативный, ибо все МК 3-го порядка ассоциативны.
Четыре квадрата есть, можно создать в OEIS последовательность магических констант наименьших ассоциативных квадратов из простых чисел.

maxal
просьба: проверьте, пожалуйста, нет ли уже в OEIS такой последовательности.

Последовательность из магических констант пандиагональных квадратов из простых чисел я недавно создала (A179440).

Ассоциативный квадрат 7-го порядка из простых чисел можно строить таким же способом (из комплементарных пар), но это, конечно, будет сложнее, чем для порядка 5.

Что у нас с ассоциативными квадратами из смитов? Квадрат порядка 3 имеем.
Вот наименьший ассоциативный квадрат 4-го порядка:

1282 5458 2578 5242
5602 2218 5098 1642
5638 2182 5062 1678
2038 4702 1822 5998

(построен из 28 комплементарных пар, найденных maxal'ем; если применить к этому ассоциативному квадрату преобразование 3-х квадратов, получится пандиагональный квадрат).

Квадрата порядка 5 нет. Надо попробовать построить.
Квадрат порядка 6 есть (построил maxal), но вряд ли наименьший. С меньшей магической константой пока не удаётся найти, но кажется мне, что он существует.

[Nataly-Mak]

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

166 2902 1903 3226 3973
4414 706 4306 922 1822
3649 2974 2434 1894 1219
3046 3946 562 4162 454
895 1642 2965 1966 4702

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

Итак, дело за наименьшим ассоциативным квадратом 6-го порядка из смитов.
Из него будет получен и пандиагональный квадрат преобразованием 3-х квадратов, но, возможно, не наименьший.

[Nataly-Mak]

Сегодня утром, пока не очень жарко (всего +32 ), написала статью "Алгоритмы построения нетрадиционных ассоциативных квадратов”.
Хотелось бы увидеть отзывы, может, что-нибудь напортачила. Эта жара всех доконала Днём опять будет +40. Ужас!

Вчера в моей новой статье в OEIS (последовательность магических констант наименьших пандиагональных квадратов из простых чисел A179440) прошла правка, сделанная в связи с двумя найденными новыми квадратами: моим 6-го порядка и svb 7-го порядка. Правку вносил товарищ, который всегда помогает мне с отправкой статей в Энциклопедию. И вот первый раз за всю историю сотрудничества он допустил ошибку: вместо пандиагонального квадрата 6-го порядка поместил обычный магический квадрат. Я ему уже написала об этом, и он ответил, что уже исправил. Однако надо теперь ждать, когда пройдёт эта правка. А пока в статье обычный магический квадрат (не удивляйтесь!). Перед работниками Энциклопедии (может, кто-нибудь заглянет сюда) извиняюсь за этот ляпсус.
Товарищ пишет: “…сам не знаю, как такое вышло”.
Жара!

[Pavlovsky]

В Екатеринбурге наконец то жара спала...
Пандиагональный МК 10х10

 167    211    547   1061   1483    653    107    229     47    197
 461    347    571    911    929    431    139    313    251    349
1487    659    131    367    173    227    557   1093      3      5
 967    433    263    379    479    359    613    941     29    239
 563   1109     13     37      7     11   1511    797    257    397
 631    953     71    269     67    241   1091    499    491    389
  31    149   1637    827    647   1279     19     53     17     43
 191    307   1319    509    643    983     89    281    109    271
 103    223     23     59     41    181    157    179   2027   1709
 101    311    127    283    233    337    419    317   1471   1103

Магическая сумма = 4702

Пандиагональный МК 10х10

  61    311    719   1063   1277    487    193    263     37    163
 479    463    881    349    257    593    251    421    419    461
1279    523    211    317     67    337    727   1103      3      7
 269    641    569    601    509    467    911    499     29     79
 733   1129     11     47      5     43   1297    577    241    491
 941    503     59    229     41    127    587    821    659    607
  23     97   1327    751    907   1283     17     73     13     83
 359    307    677    827   1091    643     89    233     71    277
 191    227     19    109     31    137     53    271   1993   1543
 239    373    101    281    389    457    449    313   1109    863

Магическая сумма = 4574

[Nataly-Mak]

Интересно получается с пандиагональным квадратом 8-го порядка из простых чисел, построенным мной из четырёх пандиагональных квадратов 4-го порядка с одинаковой магической константой по решётке Россера:

61 137 103 229 503 311 653 643
47 73 193 251 449 379 631 617
509 313 647 641 67 139 97 227
461 389 619 607 59 83 181 241
157 349 7 17 599 523 557 431
211 281 29 43 613 587 467 409
593 521 563 433 151 347 13 19
601 577 479 419 199 271 41 53

Поскольку пандиагональные квадраты 4-го порядка составлены из комплементарных пар с одной и той же суммой в паре, то и весь квадрат 8-го порядка тоже составлен из таких комплементарных пар. Я подумала: а нельзя ли превратить пандиагональный квадрат в ассоциативный с помощью преобразования, обратного преобразованию 3-х квадратов? Кстати, преобразование 3-х квадратов интересно тем, что обратное ему преобразование совпадает с ним самим (но применимо обратное преобразование не к любому пандиагональному квадрату чётного порядка, в отличие от прямого преобразования, которое применимо к любому ассоциативному квадрату чётного порядка).

Так вот, попробовала применить преобразование к приведённому пандиагональному квадрату и… получила следующий ассоциативный квадрат 8-го порядка из простых чисел:

61 137 103 229 643 653 311 503
47 73 193 251 617 631 379 449
509 313 647 641 227 97 139 67
461 389 619 607 241 181 83 59
601 577 479 419 53 41 271 199
593 521 563 433 19 13 347 151
211 281 29 43 409 467 587 613
157 349 7 17 431 557 523 599

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

Теперь дело за наименьшим ассоциативным квадратом 7-го порядка из простых чисел. В своей статье "Алгоритмы построения нетрадиционных ассоциативных квадратов" я отметила, что построение такого квадрата по алгоритму, основанному на использовании комплементарных пар чисел, в принципе возможно, но тут как повезёт. Надо рассчитывать на удачу, как мне, например, повезло с ассоциативным квадратом 6-го порядка из простых чисел, который построился мгновенно, в то время как ни для одного набора комплементарных пар из смитов мне не удаётся выполнить программу до конца или прежде того получить ассоциативный квадрат.
Возможен поиск новых идей, способных преодолеть “экспоненциальный взрыв”. Хорошая задача!

Надо попробовать построение идеального квадрата 7-го порядка из простых чисел. У меня есть общая формула для пандиагонального квадрата 7-го порядка, полученная решением СЛУ. Надо определить в ней комплементарные элементы через один из них, это намного сократит количество независимых элементов в формуле. Может быть, удастся тогда реализовать полученную формулу. Пока же я её даже не пыталась реализовать, безнадёжно.

Кстати, и наименьшие идеальные квадраты порядков 5 - 6 из простых чисел у нас ещё не построены. Идеальный квадрат 5-го порядка вообще есть, но с очень большой магической константой (построен из чисел арифметической прогрессии длины 25).

maxal
вам, наверное, несложно по своей программе построить идеальные квадраты порядков 5 - 6 из простых чисел? Ждём

[Nataly-Mak]

Проделала с программой для построения пандиагонального квадрата 5-го порядка то, что предполагала проделать с программой для квадрата 7-го порядка.
В программе для пандиагонального квадрата 5-го порядка реализована общая формула типа 8 + 17 (8 независимых элементов и 17 зависимых).
Формула получена решением СЛУ.
Если учитывать ассоциативность квадрата, то у меня количество независимых элементов сократилось до 5, то есть формула стала типа 5 + 20.
Понятно, что такая программа выполняется намного быстрее, чем программа для пандиагонального квадрата без свойства ассоциативности.
Кроме того, сделала программу так, что она проверяет любой набор комплементарных пар, а не только набор точно из 12 пар.

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

113 1151 1229 911 101
839 521 41 1013 1091
941 953 701 449 461
311 389 1361 881 563
1301 491 173 251 1289

Магическая константа равна 3505.
По моим подсчётам это наименьший квадрат. Может быть, какой-нибудь и проскочила. Жара!

Сейчас посмотрела ещё раз все преобразования в формуле. Вроде можно сократить количество независимых элементов до 4, если учесть, что в идеальном квадрате заранее известен центральный элемент. Сейчас этот элемент в программе вычисляется и проверяется, равен ли он константе ассоциативности, делённой пополам.

[Pavlovsky]

Родилась такая задачка.

Можно ли построить пандиагональный МК 5х5 из различных простых чисел, с магической суммой 6k+3 (где k целое) и с использованием числа 3?

[maxal]

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

Магическая константа равна 3505.
По моим подсчётам это наименьший квадрат.

Да, это так.

А вот ассоциативный квадрат 5x5 из простых с наименьшей возможной магической суммой 1255:

11, 233, 461, 479, 71, 
263, 419, 59, 113, 401, 
449, 191, 251, 311, 53, 
101, 389, 443, 83, 239, 
431, 23, 41, 269, 491

-- Wed Aug 04, 2010 20:20:04 --

Pavlovsky в сообщении #342394 писал(а):

Можно ли построить пандиагональный МК 5х5 из различных простых чисел, с магической суммой 6k+3 (где k целое) и с использованием числа 3?

Сие невозможно. Достаточно рассмотреть в таком квадрате ряд, не содержащий 3, и заметить, что сумма элементов в нём не может быть кратна 3-м.

-- Wed Aug 04, 2010 20:31:04 --

Квадраты 6x6 из простых с минимальными константами:

идеальный - константа 990:

103, 59, 163, 233, 139, 293, 
229, 257, 307, 131, 13, 53, 
283, 17, 67, 173, 181, 269, 
61, 149, 157, 263, 313, 47, 
277, 317, 199, 23, 73, 101, 
37, 191, 97, 167, 271, 227

ассоциативный - константа 630:

131, 53, 47, 109, 151, 139, 
137, 103, 61, 29, 173, 127, 
191, 179, 43, 13, 11, 193, 
17, 199, 197, 167, 31, 19, 
83, 37, 181, 149, 107, 73, 
71, 59, 101, 163, 157, 79

[Nataly-Mak]

Ассоциативный квадрат 5-го порядка из простых чисел я уже построила и показала:

Цитата:

Из этого массива ассоциативный квадрат построился сразу:

11 263 101 431 449
443 149 389 41 233
479 311 251 191 23
269 461 113 353 59
53 71 401 239 491

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

Сейчас пытаюсь построить идеальный квадрат 5-го порядка из смитов (ассоциативный 5-го порядка из смитов тоже построила). Уже проверила до константы 31575. Пока идеальный квадрат не построился.

Для порядка 6 ассоциативный квадрат из простых тоже давно построен (с магической константой 630). Найденный вами идеальный квадрат новый.

Идеальный квадрат 6-го порядка из смитов вы построили давно.
Нет ассоциативного (наименьшего) и пандиагонального (наименьшего) из смитов.

Кроме того, остаётся открытым вопрос о минимальности пандиагонального квадрата 6-го порядка из простых чисел. Найденный мной пандиагональный квадрат получен из ассоциативного квадрата преобразованием 3-х квадратов и имеет магическую константу 630. Но вполне возможно, что существует пандиагональный квадрат из произвольных простых чисел, не составленный из комплементарных пар чисел, магическая константа которого меньше 630.

Сейчас составлю полную таблицу разных видов квадратов из простых и из смитов.

[maxal]

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

Идеальный квадрат 6-го порядка из смитов вы построили давно.
Нет ассоциативного (наименьшего) и пандиагонального (наименьшего) из смитов.

Вот наименьший ассоциативный квадрат 6x6 из смитов с константой 14280:

2722, 2326, 1255, 2965, 958, 4054, 
2182, 391, 2902, 3865, 4306, 634, 
4198, 2605, 2839, 166, 58, 4414, 
346, 4702, 4594, 1921, 2155, 562, 
4126, 454, 895, 1858, 4369, 2578, 
706, 3802, 1795, 3505, 2434, 2038

[Pavlovsky]

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

Сие невозможно. Достаточно рассмотреть в таком квадрате ряд, не содержащий 3, и заметить, что сумма элементов в нём не может быть кратна 3-м.

Возьмем одно число вида 6k-1 и четыре числа вида 6k+1. В сумме они дадут 6k+3.