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

[svb]

Summa=9402
Time: 1234.75 sec

-- Вс апр 29, 2012 22:31:23 --

Summa=9486
Time: 4078.71 sec

[Nataly-Mak]

Нет? Ожидаемый результат

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

[Nataly-Mak]

Сомнений не осталось.
Сейчас запустила программу alexBlack для проверки константы 3774 (повторно), никакие другие программы не работают. Прошло 1,5 ч., программа прошла половину (судя по нарисованным точкам).
Я могу предположить только одно: у меня старая версия его программы. Потом он её оптимизировал и писал на форуме ПЕН, что массив из 36 смитов программа проверяет 10 сек.
А где взять новую версию программы? Как я уже писала, его страница не открывается (ошибка 404).

alexBlack
отзовитесь

[Nataly-Mak]

Вот результат работы программы проверки константы 3774 по программе alexBlack



То, что не работали другие программы, дало очень незначительное убыстрение; раньше было 2,85 ч., сейчас 2,81 ч., это всего около 2,5 мин.

Попробовала наш тестовый пример - для константы 5964 из смитов (задан массив из 36 чисел), программа работала 110 сек., найдено 4 квадрата:

6:[p]:5964: 94,1795,922,913,1678,562,2902,517,166,526,1219,634,22,895,2785,355,1642,265,1111,382,274,1858,121,2218,202,1921,1282,346,319,1894,1633,454,535,1966,985,391
6:[p]:5964: 202,1921,1282,346,319,1894,1111,382,274,1858,121,2218,22,895,2785,355,1642,265,2902,517,166,526,1219,634,94,1795,922,913,1678,562,1633,454,535,1966,985,391
6:[p]:5964: 1678,913,922,1795,94,562,1219,526,166,517,2902,634,1642,355,2785,895,22,265,121,1858,274,382,1111,2218,319,346,1282,1921,202,1894,985,1966,535,454,1633,391
6:[p]:5964: 319,346,1282,1921,202,1894,121,1858,274,382,1111,2218,1642,355,2785,895,22,265,1219,526,166,517,2902,634,1678,913,922,1795,94,562,985,1966,535,454,1633,391

А вот что дала программа svb для этой же тестовой константы 5964 (с тем же самым массивом смитов):

Summa=5964
1:
  985 1966  535  454 1633  391
 1678  913  922 1795   94  562
 1219  526  166  517 2902  634
 1642  355 2785  895   22  265
  121 1858  274  382 1111 2218
  319  346 1282 1921  202 1894
Time: 2.85 sec
Time: 22.37 sec

Тут время уже фанстастическое квадрат найден за 2,85 сек.

Но почему только один квадрат? Найденные по программе alexBlack 4 квадрата эквивалентны (изоморфны) друг другу? Надо посмотреть на эти квадраты внимательно.

[Nataly-Mak]

Кстати, задача о пандиагональных квадратах 6-го порядка из последовательных простых чисел предлагалась во втором конкурсе "Нетрадиционные пандиагональные квадраты"

Цитата:

Задача № 2

О пандиагональном квадрате 6-го порядка из последовательных простых чисел сказано в задаче №1.
Его магическая константа равна 930.
Найти следующий пандиагональный квадрат 6-го порядка из последовательных простых чисел (то есть магическая константа этого квадрата должна быть наименьшей из всех потенциальных магических констант для таких квадратов) или доказать, что таких квадратов больше не существует.
Несколько потенциальных магических констант для квадратов указанного вида: 1494, 3774, 8118, 9318, 9402, 9486.

(этот конкурс проводился здесь, на этом форуме)

Никто задачу не решил (скорее всего, никто не решал).

-- Пн апр 30, 2012 13:32:46 --

Рассмотрела квадраты, найденные по программе alexBlack (см. выше). Да, они действительно эквивалентные (параллельный перенос на торе).
Теперь понятно, почему программа svb выдала только один квадрат.

[Nataly-Mak]

Да, многое забыто, пиходится вспоминать; хорошо, что есть сообщения на форумах, в них кое-что сохранено, хотя далеко не всё.
Например, не могу точно вспомнить, как у нас определился диапазон магических констант для пандиагональных квадратов 6-го порядка из смитов: 3912 - 5964. Нет, о верхней границе помню, конечно, это я сама нашла квадрат с такой константой по программе svb (ещё по старой программе, с комплектами отклонений). А вот как определилась нижняя граница, убей - не помню.

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

Вот схема такого пандиагонального квадрата 7-го порядка:

p1 p1 p1 p2 p1 p2 p1
p2 p1 p1 p1 p1 p2 p1
p2 p1 p2 p1 p1 p1 p1
p1 p1 p2 p1 p2 p1 p1
p1 p1 p1 p1 p2 p1 p2
p1 p2 p1 p1 p1 p1 p2
p1 p2 p1 p2 p1 p1 p1

Подробности здесь:
http://e-science.ru/forum/index.php?sho ... 507&st=200

В отличие от алгоритма Россера, предлагаемый алгоритм даёт нерегулярные пандиагональные квадраты.

В сообщении описан эксперимент с квадратом из смитов, найден такой полуфабрикат (то есть программа не отработала до конца, долго; остались не найдены несколько чисел):

0 10966 0 355 10669 6439 85 
526 274 6835 18337 0 0 14386 
7402 14998 7339 3973 2614 2155 15853 
0 346 0 9346 0 18346 0 
2839 16537 16078 14719 265 3694 202 
4306 0 0 355 11857 18418 7078 
18607 1165 8023 7249 0 7726 0

Помню, что у меня есть пандиагональный квадрат 7-го порядка из смитов с магической константой 696745. Очень большая константа! Этот квадрат построен по алгоритму Россера (с использованием примитивного квадрата).

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

[Nataly-Mak]

Хотела писать программку достраивания приведённого полуфабриката. Оказалось, что квадрат элементарно достраивается вручную:

16456 10966 9364 355 10669 6439 85
526 274 6835 18337 16420 -2444 14386
7402 14998 7339 3973 2614 2155 15853
4198 346 4423 9346 3181 18346 14494
2839 16537 16078 14719 265 3694 202
4306 10048 2272 355 11857 18418 7078
18607 1165 8023 7249 9328 7726 2236

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

Вот только желающих у меня, как всегда, нуль

[Nataly-Mak]

Выше приведены 4 пандиагональных квадрата 6-го порядка из смитов с магической константой 5964, найденных по программе alexBlack, и одни квадрат из того же массива чисел, найденный по программе svb. Как я уже сказала, все эти квадраты эквивалентны.

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

[svb]

Summa=5964
1:
 3595    4  355   94 1858   58
  265 1111 2902  634  517  535
  985  382  202 1894 1282 1219
  166 1795  778  121  319 2785
  562 2326   85 2515   22  454
  391  346 1642  706 1966  913
Time: 18674.01 sec

Это для $N=71$ (начало $N=76$) Diab_v5. Очень долго! Далее еще хуже будет.

[svb]

2:
 3505  391  526  202  985  355
  562   85 2515 1642  706  454
  319  958   22 1165  274 3226
  265 1678 2461    4  922  634
 1255 1219   94  517 1966  913
   58 1633  346 2434 1111  382
Time: 27766.11 sec

[Nataly-Mak]

Домучила константу 5046. Квадрат не найден.

[Nataly-Mak]

svb
вы добываете пандиагональные квадраты с магической константой 5964, как жемчужины со дна моря. Красиво, восхищаюсь

А это квадраты, найденные мной по вашей старой программе, с комплектами отклонений:

(Оффтоп)

S = 5964
121 1858 274 382 1111 2218
1642 355 2785 895 22 265
1219 526 166 517 2902 634
1678 913 922 1795 94 562
985 1966 535 454 1633 391
319 346 1282 1921 202 1894
1: S=5964 p2,4,6,8=-36 108 1188 -1260
121 319 985 1678 1219 1642
2218 1894 391 562 634 265
1111 202 1633 94 2902 22
382 1921 454 1795 517 895
274 1282 535 922 166 2785
1858 346 1966 913 526 355
1: S=5964 p2,4,6,8=-1152 1152 1188 -1260
22 2902 94 1633 202 1111
265 634 562 391 1894 2218
1642 1219 1678 985 319 121
355 526 913 1966 346 1858
2785 166 922 535 1282 274
895 517 1795 454 1921 382
1: S=5964 p2,4,6,8=1260 -1188 -1152 1152
355 2785 895 22 265 1642
526 166 517 2902 634 1219
913 922 1795 94 562 1678
1966 535 454 1633 391 985
346 1282 1921 202 1894 319
1858 274 382 1111 2218 121
1: S=5964 p2,4,6,8=1188 -1260 -1152 1152
22 895 2785 355 1642 265
1111 382 274 1858 121 2218
202 1921 1282 346 319 1894
1633 454 535 1966 985 391
94 1795 922 913 1678 562
2902 517 166 526 1219 634
1: S=5964 p2,4,6,8=-108 36 -1152 1152
355 1858 346 1966 913 526
1642 121 319 985 1678 1219
265 2218 1894 391 562 634
22 1111 202 1633 94 2902
895 382 1921 454 1795 517
2785 274 1282 535 922 166
1: S=5964 p2,4,6,8=-36 108 -1152 1152
895 517 1795 454 1921 382
2785 166 922 535 1282 274
355 526 913 1966 346 1858
1642 1219 1678 985 319 121
265 634 562 391 1894 2218
22 2902 94 1633 202 1111
1: S=5964 p2,4,6,8=-1152 1188 1152 -1260
895 22 265 1642 355 2785
382 1111 2218 121 1858 274
1921 202 1894 319 346 1282
454 1633 391 985 1966 535
1795 94 562 1678 913 922
517 2902 634 1219 526 166
1: S=5964 p2,4,6,8=0 72 1152 -1260
355 526 913 1966 346 1858
2785 166 922 535 1282 274
895 517 1795 454 1921 382
22 2902 94 1633 202 1111
265 634 562 391 1894 2218
1642 1219 1678 985 319 121
1: S=5964 p2,4,6,8=-1260 1188 1152 -1152
22 265 1642 355 2785 895
2902 634 1219 526 166 517
94 562 1678 913 922 1795
1633 391 985 1966 535 454
202 1894 319 346 1282 1921
1111 2218 121 1858 274 382
1: S=5964 p2,4,6,8=-1188 1260 1152 -1152
355 1642 265 22 895 2785
1858 121 2218 1111 382 274
346 319 1894 202 1921 1282
1966 985 391 1633 454 535
913 1678 562 94 1795 922
526 1219 634 2902 517 166

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

Как я понимаю, вы проверяете эту константу с включённым фильтром, то есть только из чисел вида 4(mod 9). Правильно? Если отключить фильтр, то проверка будет идти уже не часами, а сутками.

Да, мы построили уже десятки пандиагональных квадратов 6-го порядка из смитов, и ни в одном из них (!) нет чисел не равных 4(mod 9). Однако строгого доказательства этого факта мы не имеем
Проэтому прав Pavlovsky, говоря, что недостаточно рассматривать только шаблоны из вычета 4. Пока этот факт, полученный эмпирически, строго не доказан, мы должны предполагать, что существуют квадраты из смитов, дающих другие вычеты по модулю 9, а не только 4.

[Nataly-Mak]

Анализирую пандиагональные квадраты из простых чисел.

Здесь магические константы пандиагональных квадратов 4-го порядка из простых чисел:
https://oeis.org/A191533
Вот последовательность магических констант:

240, 252, 288, 372, 408, 420, 480, 492, 504, 528, 540, 552, 560, 564, 576, 588, 600

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

Пандиагональные квадраты 5-го порядка из простых чисел дают интересную последовательность магических констант (эта последовательность есть в теме, см. стр. 111; автор Pavlovsky). Автор последовательности высказал гипотезу, что начиная с магической константы 581, константы будут образовывать арифметическую прогрессию с разностью 2, то есть для любой нечётной константы, начиная с 581, пандиагональный квадрат 5-го порядка из простых чисел существует. Хотя, конечно, гипотеза требует доказательства.

Пандиагональные квадраты 6-го порядка из простых чисел тоже ведут себя замечательно Магические константы этих квадратов образуют арифметическую прогрессию с разностью 12. Как я уже говорила, мне удалось построить квадраты со всеми константами от 486 до 990 включительно (с шагом 12), нет ни одного пропуска, с каждой константой квадрат построился. Весьма любопытно, как будут вести себя квадраты дальше.

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

[Nataly-Mak]

Рассмотрела все квадраты с константой 5964.
Квадратов много, но почти все они построены вот из этого массива смитов:

22  94  121  166  202  265  274  319  346  355  382  391  454  517  526  535  562  634  895  913  922  985  1111  1219  1282  1633  1642  1678  1795  1858  1894  1921  1966  2218  2785  2902

и следовательно, все эквивалентны.
Есть только один другой квадрат в моей статье, вот он:

85 1507 1822 22 1894 634 
94 346 706 2578 202 2038 
895 2614 4 355 454 1642 
1966 58 1255 1903 517 265 
319 913 958 985 2515 274 
2605 526 1219 121 382 1111

Итак, пока имеем 4 оригинальных квадрата с константой 5964.

[svb]

3:
 3226  346  319  274 1633  166
    4 1219 2461  913  985  382
 1255  562   58 1966  958 1165
  391 1795  706   85  202 2785
  454 1507  778 2605  265  355
  634  535 1642  121 1921 1111
Time: 2268.39 sec+1сутки
4:
 3226 1678  202  121  346  391
   94  382 1507 2362  706  913
 1858   85  535 1633  895  958
  355 1894 1165  274   58 2218
  265 1903  634 1255  985  922
  166   22 1921  319 2974  562
Time: 10830.25 sec+1сутки
5:
 3226  319  454  265  778  922
  634  517 1903 2326  202  382
 1507  985  526 1678  355  913
  391  958  166   94 1921 2434
  121 2911 1633  895  346   58
   85  274 1282  706 2362 1255
Time: 14479.82 sec+1сутки
6:
 3091  517  202  265 1507  382
  706  535 2434   22 2182   85
  958   58 1894 1678   94 1282
  454 1633  346  166  319 3046
  634 1255  562 2614    4  895
  121 1966  526 1219 1858  274
Time: 25686.72 sec+1сутки
7:
 3091  913  391   85 1219  265
 1282  319 2173 1966   58  166
  526  634  121 2155  346 2182
   94 1642  535  706  202 2785
  454 2434 1633  274 1165    4
  517   22 1111  778 2974  562
Time: 32959.81 sec+1сутки