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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Здорово!

А я поднимаюсь потихоньку вверх; начала с константы 3966, сейчас проверила константу 4452, это константа проверялась 12 часов.
Завтра начну проверять константу 4506; проверяю с шагом 54 и, конечно, с фильтром пока.

Вполне возможно, что alexBlack все эти константы уже проверил, но молчит :-(

На форуме ПЕН он сообщал, что проверил константы 4884 и 4992, на третьей константе - 5100 - квадрат у него построился. Получается, что он проверял с шагом 108.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Итак, пока у нас 9 различных пандиагональных квадратов 6-го порядка из смитов с магической константой 5964.
Проверила массивы во всех квадратах, все они различны. То есть ни один массив из 36 чисел не даёт хотя бы двух неизоморфных квадратов. Вот насколько мало таких пандиагональных квадратов! Поэтому и поиск их идёт очень долго.

Вчера решила попробовать продолжить построение пандиагональных квадратов 6-го порядка из простых чисел (по-прежнему работаю по программе svb, поскольку она работает намного быстрее имеющейся у меня версии программы alexBlack).

Из простых чисел квадраты строятся очень хорошо; правда, если это произвольный набор простых, а не последовательные простые. Как я сообщала, остановилась раньше на константе 990. Начала теперь с константы 1002, до константы 1050 (с шагом 12) уже построила квадраты. Конечно, все не строю, прерываю программу, как только найдётся несколько первых квадратов.
Удивительный факт - квадраты составляются для всех магических констант с шагом 12.

-- Чт май 03, 2012 07:14:21 --

Ещё о новом алгоритме построения пандиагональных квадратов 7-го порядка

Выше показана схема пандиагонального квадрата 7-го порядка с отклонениями от комплементарности, отклонений всего два - p1 и p2, но они жёстко связаны (формула приведена).

Старую программу не стала искать, может быть, она и не сохранена со старого винта; написала новую.
Проделала эксперимент, квадрат строила из произвольных натуральных чисел. Исходные данные:
K = 1590, S = 5565, p1 = -4, p2 = 10.

Группа с отклонением p1:

Код:

715 853 1369 643 577 583 271 709 1291 1501 907 949 649 787 667 1585 607 979 1 919 799 937 637 679 85 295 877 1315 1003 1009 943 217 733 871

17 пар, 34 числа

Группа с отклонением p2:

Код:

1001 407 233 977 1019 587 1163 437 1013 581 623 1367 1193 599

7 пар, 14 чисел

Здесь выбрано точно необходимое количество пар, в первой группе пар должно быть не меньше 17, во второй группе - не меньше 7.
С этими исходными данными квадрат строится очень быстро:

Код:

715  853  1369  1001  643  407  577 
 233  583  271  709  1291  977  1501 
 1019  907  587  949  649  787  667 
 1585  607  1163  793  437  979  1 
 919  799  937  637  1013  679  581 
 85  623  295  877  1315  1003  1367 
 1009  1193  943  599  217  733  871

Итак, тест программа прошла. Можно пробовать построение пандиагональных квадратов из смитов.
Такой эксперимент тоже провела; я его ещё и тогда провела, о чём сообщала на форуме ПЕН. Сейчас повторила эксперимент с этими же исходными данными и ещё один - с другими данными. Программа работает, 35 чисел ставит на место моментально, например (во втором эксперименте):
K = 17540, p1 = 1152, p2 = -2880, S = 61390,
в группе с отклонением p1 27 пар, в группе с отклонением p2 31 пара.

Код:

0  14386  8914  12442  9094  0  85 
 1678  274  1966  8023  0  0  0 
 9274  18346  4765  14566  7627  2614  4198 
 0  7726  0  9346  0  10966  0 
 14494  16078  11065  4126  9895  346  5386 
 0  0  0  10669  16726  18418  12982 
 18607  0  9598  2218  9778  4306  0

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

Программу можно использовать и для построения идеальных квадратов 7-го порядка. Ведь идеальный квадрат - это пандиагональный квадрат, в котором есть свойство ассоциативности. Это означает, что все отклонения от комплементарности в предложенном алгоритме будут равны нулю: p1 = p2 = 0.

Сейчас хочу протестировать программу на построении идеального квадрата.

svb · 20/01/10 766 Нижний Новгород

Цитата:

8:
3091 202 517 58 1642 454
265 391 1633 1111 2218 346
922 1255 2182 274 166 1165
706 913 778 121 1219 2227
22 1282 319 2578 85 1678
958 1921 535 1822 634 94
Time: 39822.34 sec+1сут.
9:
3091 391 346 265 913 958
4 922 1642 2911 166 319
1111 1921 58 454 562 1858
535 94 1507 85 2578 1165
706 2362 1633 355 526 382
517 274 778 1894 1219 1282
Time: 2сут.-30743.82 sec
10:
2965 526 535 85 958 895
319 346 1894 2218 202 985
1219 517 94 2434 22 1678
922 2038 913 4 454 1633
274 1255 706 1165 2173 391
265 1282 1822 58 2155 382
Time: 2сут.-14494.66 sec
11:
2965 346 958 94 1219 382
58 1894 1111 1921 895 85
391 535 517 121 1822 2578
913 1633 2362 4 778 274
355 922 454 1642 265 2326
1282 634 562 2182 985 319
Time: 2сут.-12104.60 sec

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

А вот как строятся пандиагональные квадраты 6-го порядка из простых чисел:

(Оффтоп)

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

svb · 20/01/10 766 Нижний Новгород

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

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

И зачем вы меня спровоцировали :-)

на построение этих квадратов?

Цитата:

Возникает вопрос: сколько существует различных квадратов с магической константой 5964?
Это наш тестовый пример. В моей статье, помнится, я привела несколько разных квадратов, но все ли?

А сейчас и бросить жалко

Код:

12:
 2965  895   85  166 1795   58
 1282  202 2902  706  778   94
  382 1219  265  958 2218  922
  526 1165 1255  319  121 2578
  355 2461  346 1633  535  634
  454   22 1111 2182  517 1678
Time: 2 сут.-9392.43 sec
13:
 2965  562  265  166  895 1111
  346   22 1894 2362  958  382
 1678 2155  634  922  121  454
  526   85  274  319 2434 2326
  355 2605 1642  913  391   58
   94  535 1255 1282 1165 1633
Time: 2 сут.-9012.80 sec

Всего несколько суток осталось :-)

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Эх, вы единственный коллега, поддающийся на мои провокации

Раньше были ещё, но... больше не желают поддаваться на провокации :wink:

Ведь пандиагональные квадраты с магической константой 5964 - это у нас своего рода эталон. Так что будет замечательно, если мы будем знать полный комплект различных квадратов с этой магической константой.

А я протестировала программу построения пандиагональных квадратов 7-го порядка по новому алгоритму (с отклонениями от комплементарности) на примере построения идеального квадрата. Всё прекрасно выполнилось.
Квадрат взяла из своей статьи "Нетрадиционные пандиагональные квадраты (часть II)", это идеальный квадрат из простых чисел (построен по другому алгоритму).

Исходные данные:
K=5554, S = 19439, p1 = p2 = 0.

Квадрат построился минут за 10:

Код:

4643  2141  1301  5501  5153  677  23 
4463  281  1427  5297  2543  167  5261 
3833  761  3491  4373  1217  383  5381 
503  821  5471  2777  83  4733  5051 
173  5171  4337  1181  2063  4793  1721 
293  5387  3011  257  4127  5273  1091 
5531  4877  401  53  4253  3413  911

***
Ещё построила несколько пандиагональных квадратов 6-го порядка из простых чисел, до константы 1230 включительно. Решила пока остановиться. Квадраты строятся и очень быстро. Но это всё же только экспериментальные данные.

Кто сможет доказать, что для любой следующей магической константы в этой арифметической прогрессии с разностью 12 пандиагональный квадрат 6-го порядка из простых чисел существует?

Хорошая задача!

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb
а помните, как лихо вы строили пандиагональные квадраты 7-го порядка методом Россера (с использованием примитивных квадратов)? :-)

Вот сейчас решила посмотреть, что мы имеем с пандиагональными квадратами 7-го порядка из простых чисел. Благо, файл с квадратами сохранился.

Это магические константы квадратов, которые у нас есть:

Код:

2477, 2435, 2363, 2279, 2047, 1895, 1649, 1597

Пока не вижу никакой закономерности в этой последовательности магических констант.

Квадрат с магической константой 1649 построил Pavlovsky; этот квадрат некоторое время был у нас наименьшим. Потом я улучшила этот результат, построив квадрат с магической константой 1597:

Код:

89 397 409 43 157 311
103 101 491 17 313 193
241 109 163 439 47 281
383 227 107 541 37 79
337 7 139 167 563 53
347 389 277 127 307 67
97 367 11 263 173 613

Я тоже строила квадрат методом Россера (это было в апреле 2011 г.).

Пока этот квадрат является наименьшим. Однако не доказано, что он действительно наименьший, и я сильно подозреваю, что это совсем не так.

Задачу, к сожалению, все забросили.
А в последовательности OEIS (A179440) так и стоят одиноко три наименьшие константы - для квадратов порядков 4 - 6; дальше указаны только верхние границы для констант.
Обидно, что не довели хотя бы квадраты 7-го порядка до логического конца :-(

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

svb · 20/01/10 766 Нижний Новгород

Summa=5964
Осталось совсем немного, но я выключаю комп. Справа число квадратов для соответствующего N. Можете продолжить :-)

Код:

N=76(3865) - 0
N=75(3802) - 0
N=74(3694) - 0
N=73(3649) - 0
N=72(3622) - 0
N=71(3595) - 1
N=70(3505) - 1
N=69(3442) - 0
N=68(3226) - 3
N=67(3091) - 4
N=66(2965) - 10
N=65(2839) - ?
N=64(3046) - ?
N=63(2911) - ?
N=62(2785) - 6
N=61(2902) - ?
N=60(2515) - ?
N=59(2227) - ?
N=58(2974) - ?
N=57(2461) - ?
N=56(2722) - ?
N=55(2605) - ?
N=54(2173) - ?
N=53(4) - ?
N=52(2326) - ?
N=51..36     - 0

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Насколько я понимаю, совсем не обязательно выполнять программу без перерыва?...

Я всегда на ночь прерываю, а утром продолжаю с прерванного места.
Сейчас проверяю константу 4938, вчера работала 14 часов; сейчас продолжу, осталось ещё 52 числа прверить.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb
вы...навсегда выключили комп?

Значит, и вы больше не поддаётесь на провокации, связанные с квадратами?

Вот, к примеру, примитивный квадрат 7х7 из простых чисел, соответствующий приведённому выше пандиагональному квадрату с магической константой 1597:

Код:

7   11   17   37   67   191   241
43   47   53   73   103   227   277
79   83   89   109   139   263   313
97   101   107   127   157   281   331
163   167   173   193   223   347   397
307   311   317   337   367   491   541
379   383   389   409   439   563   613

Вам-то не надо объяснять, что такое примитивный квадрат.
Для других форумчан поясню: в примитивном квадрате разность между соответствующими элементами любых двух строк (столбцов) постоянна. Например:

11 - 7 = 4
47 - 43 = 4
83 - 79 = 4
........

277 - 241 = 36
227 - 191 = 36
103 - 67 = 36
.......

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

Задачу до конца так и не решили. Pavlovsky решал, svb решал, я решала... А где наименьший квадрат? :-(

Нет, друзья мои, так задачи не решают :-)

Там начали, бросили, там начали, бросили... Понимаю: скучно гнать программу 10 суток. Мне, однако, совсем не скучно! Потому что программа у меня работает сама по себе, а я
тем временем работаю сама по себе. И никакой скуки и тоски!

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

У меня, к сожалению, программа построения примитивных квадратов 7х7 не сохранилась (сдохла вместе со старым компом). Сейчас буду писать новую программу.

-- Пт май 04, 2012 07:58:38 --

Просмотрела свой давнишний файл о построении пандиагональных квадратов 7-го порядка из простых чисел. Вот, например, такой ещё есть примитивный квадрат:

Код:

23 43 73 83 113 293
41 61 91 101 131 311
47 67 97 107 137 317
89 109 139 149 179 359
173 193 223 233 263 443
191 211 241 251 281 461
389 409 439 449 479 659

Хороший квадратик, он даёт пандиагональный квадрат с магической константой 1433.
Но! В нём есть одно не простое число - 91.

Это ещё образец примитивного квадрата для тех, кто вдруг (!) захочет попробовать поиск примитивных квадратов 7х7 из простых чисел.

Замечу, что наименьший обычный магический квадрат 7-го порядка из простых чисел имеет магическую константу 733 (см. A164843).

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Написала программу построения примитивных квадратов 7х7 из простых чисел, протестировала.
Повторюсь: мне известны пандиагональные квадраты 7-го порядка из простых чисел с такими магическими константами:

2477, 2435, 2363, 2279, 2125, 2047, 1895, 1649, 1597

Это то, что есть у меня в файле; может быть, не всё скопировала в этой теме, но было это очень давно, искать не хочется.

Сейчас задала в программе ограничение на магическую константу S - не больше 1895, мгновенно получила примитивный квадрат с константой 1739:

Код:

11  13  23  41  151  263  331 
17  19  29  47  157  269  337 
59  61  71  89  199  311  379 
101  103  113  131  241  353  421 
137  139  149  167  277  389  457 
227  229  239  257  367  479  547 
431  433  443  461  571  683  751

Превращаю этот примитивный квадрат в пандиагональный с помощью преобразования Россера:

Код:

71 457 461 17 241 229
157 103 479 23 379 167
331 89 137 571 19 353
433 269 113 547 41 59
257 11 199 139 683 29
389 443 337 131 227 151
101 367 13 311 149 751

Тест программа прошла замечательно. Однако полученная константа больше 1597, а надо искать с меньшей константой.

Далее запускаю программу с ограничением на константу не больше 1595, всё! программа уходит в глубокую задумчивость :-)

Вот и попробуйте найти примитивный квадрат с константой меньше 1597! Если он существует, то найти его очень сложно.
Я задействовала в программе массив из 150 простых чисел, это довольно большой массив.

В общем, задача остаётся открытой.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

В голове вертятся идеи оптимизации программы.

Например, первое: можно задавать в программе магическую константу, для которой делается проверка; это сократит количество перебираемых элементов на 1. Сейчас у меня в программе конкретная константа не задаётся, а задаётся только верхняя граница.
Второе: попробовать минимизировать массив чисел для конкретной магической константы. Массив из 150 чисел может оказаться избыточным. Можно ещё проверить каждое число массива на принадлежность не менее чем трём цепочкам из 7 чисел с суммой равной магической константе.

Берём, скажем, следующую константу для проверки - 1595. Вот всё надо сделать под эту константу. Возможно, оптимизация позволит проверить массив чисел полностью.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

svb в сообщении #567066 писал(а):

Summa=5964
Осталось совсем немного, но я выключаю комп. Справа число квадратов для соответствующего N. Можете продолжить :-)

Могу

Код:

Summa=5964
1:
 2839  265  319   22 2434   85
   94  922 3046  985  526  391
 1282  121  778  895  562 2326
  202 1219 1111  913   58 2461
  382 2182    4 2515  346  535
 1165 1255  706  634 2038  166
Time: 6142.49 sec

С утра запустила программу, до сих пор проверяется число 2839.
Но у меня работает ещё программа проверки магической константы 4830, плюс программа поиска примитивных квадратов 7х7, правда, последнюю сейчас прервала.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Ещё один квадратик появился :-)

Код:

2:
 2839  526 1219   94 1282    4
  895 1165 2461  274 1111   58
   85  391  166  922 2218 2182
  778 1822 1795  265  346  958
  913 1678  202 1894   22 1255
  454  382  121 2515  985 1507
Time: 34365.02 sec

svb · 20/01/10 766 Нижний Новгород

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

Ещё один квадратик появился :-)

Ох, сколько их еще будет! :-)

Научный форум dxdy

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

Кто сейчас на конференции