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

[Nataly-Mak]

Всё, тестирование завершено. Программа поиска четвёртого покрытия выдала кучу покрытий, но все они эквивалентны.
Фактически найдено всего одно четвёртое точное покрытие:

#4
11  911  2621  23  1613  2003  509  1949  2609 
131  191  1151  1913  2153  2633  179  1559  2339 
281  311  2291  743  2063  2333  59  1709  2459 
821  653  683  1703  2243  1229  1289  1499  2129
29  173  449  1283  1361  1439  2273  2549  2693 
1901  2069  2039  1019  479  1493  1433  1223  593
2441  2411  431  1979  659  389  2663  1013  263
2591  2531  1571  809  569  89  2543  1163  383
2711  1811  101  2699  1109  719  2213  773  113

whitefox
при обсуждении построения пандиагональных квадратов 7-го порядка методом точных ортогональных покрытий массива вы сначала высказали гипотезу:
любой комплект из 4-х точных попарно ортогональных покрытий массива из 49 различных чисел даёт пандиагональный квадрат 7-го порядка.
Мне удалось получить такой комплект, из которого мы не смогли построить пандиагональный квадрат.
Таким образом, данная гипотеза была опровергнута.
[Надеюсь, что мы там не ошиблись.]

Сейчас у меня напрашивается аналогичная гипотеза:
любой комплект из 4-х точных попарно ортогональных покрытий массива из 81 различного числа (40 пар комплементарных чисел + центральный элемент) даёт идеальный квадрат 9-го порядка.

Пока мне не удалось получить ни одного комплекта для опровержения данной гипотезы. Доказать её тоже не получается.
Что скажете?

[whitefox]

Скажу, что в той теме Pavlovsky предложил переформулировку той гипотезы в терминах конечной геометрии. Представляется, что на данном пути можно также найти доказательство либо опровержение и Вашей гипотезы.

[Nataly-Mak]

Осталось найти Pavlovsky

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

-- Чт июл 09, 2015 18:07:53 --

Вы писали в ответ на вопрос Pavlovsky "...проверить возможность построения пандиагонального квадрата из 4-х ортоганольных разбиений мы можем?"

whitefox в сообщении #760140 писал(а):

Конечно можем.
Эта аксиома как раз и обеспечивает успешное завершение, приведённого выше, алгоритма построения пандиагонального квадрата из четырёх попарно ортогональных точных покрытий.

Если я правильно понимаю, здесь вы утверждаете, что некая аксиома (вы её сформулировали выше) и гарантирует нам построение пандиагонального квадрата из комплекта 4-х точных попарно ортогональных покрытий массива.
Правильно понимаю?
Так чего не хватило, аксиомы?

Проверить-то комплект мы, конечно, можем. Отчего же не проверить. Но вот дело в том, что проверка эта не всегда завершается построением пандиагонального квадрата (повторюсь: если мы не ошиблись с примером моего комплекта).

[whitefox]

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

[Nataly-Mak]

whitefox в сообщении #1035195 писал(а):

Скажу, что в той теме Pavlovsky предложил переформулировку той гипотезы в терминах конечной геометрии. Представляется, что на данном пути можно также найти доказательство либо опровержение и Вашей гипотезы.

Здесь вы написали, что "...на данном пути можно также найти доказательство либо опровержение..." моей гипотезы.
Тогда получается, что "также" здесь лишнее, потому что ваша гипотеза не была доказана (опровергнута) "на данном пути".
И ещё неизвестно, можно ли её вообще доказать либо опровергнуть "на данном пути"

[whitefox]

А ещё я написал "представляется" Что не отвергает никакую другую возможность, а лишь указывает на наиболее вероятный исход, по моему скромному мнению.

[Nataly-Mak]

Эксперимент
цель эксперимента - найти комплект из 4-х точных попарно ортогональных покрытий массива отличный от известного.

Снова беру первое точное покрытие массива (по решению с дырками):

2699 281 809 1499 479 2633 389 911 2549 
59 1571 2129 1493 2339 659 1613 2273 113 
2591 1289 1901 191 1013 11 2693 101 2459 
683 2069 1559 2411 2003 1439 773 743 569 
1019 179 431 509 1361 2213 2291 2543 1703 
2153 1979 1949 1283 719 311 1163 653 2039 
263 2621 29 2711 1709 2531 821 1433 131 
2609 449 1109 2063 383 1229 593 1151 2663 
173 1811 2333 89 2243 1223 1913 2441 23

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

(Оффтоп)

POKRYTIE # 1 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  1811  2291  809  1229  1559  1979  2339 
 311  2531  2243  179  389  1109  1289  2069  2129 
 281  821  1571  2063  2213  2693  89  569  1949 
 1499  2273  2459  2003  1361  719  263  449  1223 
 2441  1901  1151  659  509  29  2633  2153  773 
 2411  191  479  2543  2333  1613  1433  653  593 
 2621  2591  911  431  1913  1493  1163  743  383 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  809  389  281  1499  2633  479  911  2699 
 113  2339  2129  1571  2273  659  1613  1493  59 
 11  101  1289  2693  2459  1901  191  2591  1013 
 1439  1559  2069  569  2003  773  2411  743  683 
 1703  2291  179  2213  1361  509  2543  431  1019 
 2039  1979  311  1949  719  2153  653  1163  1283 
 1709  131  2531  821  263  29  1433  2621  2711 
 2663  1229  1109  2063  449  1151  593  383  2609 
 23  1811  2243  89  1223  2441  2333  1913  173 

POKRYTIE # 2 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  1811  2291  809  1229  1559  1979  2339 
 311  2531  2243  179  389  1109  1289  2069  2129 
 1151  1901  2441  773  2153  2633  29  509  659 
 1499  2273  2459  2003  1361  719  263  449  1223 
 1571  821  281  1949  569  89  2693  2213  2063 
 2411  191  479  2543  2333  1613  1433  653  593 
 2621  2591  911  431  1913  1493  1163  743  383 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  809  389  2633  1499  281  479  911  2699 
 113  2339  2129  659  2273  1571  1613  1493  59 
 11  101  1289  1901  2459  2693  191  2591  1013 
 1439  1559  2069  773  2003  569  2411  743  683 
 1703  2291  179  509  1361  2213  2543  431  1019 
 2039  1979  311  2153  719  1949  653  1163  1283 
 1709  131  2531  29  263  821  1433  2621  2711 
 2663  1229  1109  1151  449  2063  593  383  2609 
 23  1811  2243  2441  1223  89  2333  1913  173 

POKRYTIE # 3 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  1811  2291  809  1229  1559  1979  2339 
 821  2411  2333  179  659  1109  1289  1499  1949 
 191  1151  2441  263  2273  2633  509  719  2069 
 479  2129  2693  569  1361  2153  29  593  2243 
 2531  1571  281  2459  449  89  2213  2003  653 
 1901  311  389  2543  2063  1613  1433  1223  773 
 2621  2591  911  431  1913  1493  1163  743  383 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  809  1499  2633  479  281  389  911  2699 
 113  2339  659  2273  2129  1571  1613  1493  59 
 11  101  1289  191  2693  2459  1901  2591  1013 
 1439  1559  2411  2069  569  2003  773  743  683 
 1703  2291  179  509  1361  2213  2543  431  1019 
 2039  1979  1949  719  2153  653  311  1163  1283 
 1709  131  821  263  29  2531  1433  2621  2711 
 2663  1229  1109  1151  593  449  2063  383  2609 
 23  1811  2333  2441  2243  89  1223  1913  173 

POKRYTIE # 4 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  1811  2291  809  1229  1559  1979  2339 
 821  2411  2333  179  659  1109  1289  1499  1949 
 281  1571  2531  653  2003  2213  89  449  2459 
 479  2129  2693  569  1361  2153  29  593  2243 
 2441  1151  191  2069  719  509  2633  2273  263 
 1901  311  389  2543  2063  1613  1433  1223  773 
 2621  2591  911  431  1913  1493  1163  743  383 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  809  1499  281  479  2633  389  911  2699 
 113  2339  659  1571  2129  2273  1613  1493  59 
 11  101  1289  2459  2693  191  1901  2591  1013 
 1439  1559  2411  2003  569  2069  773  743  683 
 1703  2291  179  2213  1361  509  2543  431  1019 
 2039  1979  1949  653  2153  719  311  1163  1283 
 1709  131  821  2531  29  263  1433  2621  2711 
 2663  1229  1109  449  593  1151  2063  383  2609 
 23  1811  2333  89  2243  2441  1223  1913  173 

POKRYTIE # 5 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  1811  2291  809  1229  1559  1979  2339 
 821  2441  1613  179  449  719  1499  2069  2459 
 191  1151  2411  1433  2153  2213  89  479  2129 
 389  659  2693  773  1361  1949  29  2063  2333 
 2531  1571  311  1289  569  509  2633  2243  593 
 1901  281  1109  2543  2273  2003  1223  653  263 
 2621  2591  911  431  1913  1493  1163  743  383 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  809  1499  479  389  2633  281  911  2699 
 113  2339  1613  2129  659  1571  2273  1493  59 
 11  101  2459  191  2693  1289  1901  2591  1013 
 1439  1559  2069  2411  773  569  2003  743  683 
 1703  2291  179  2213  1361  509  2543  431  1019 
 2039  1979  719  2153  1949  311  653  1163  1283 
 1709  131  821  1433  29  2531  263  2621  2711 
 2663  1229  449  1151  2063  593  1109  383  2609 
 23  1811  2441  89  2333  2243  1223  1913  173 

. . . . . . . . .

POKRYTIE # 225 
 11  23  113  1703  2663  1439  1709  2039  2549 
 101  131  2291  2441  659  1109  1499  1949  2069 
 821  2411  2333  509  719  809  1229  1289  2129 
 191  1151  1811  263  2273  2543  479  1559  1979 
 2633  2339  2693  569  1361  2153  29  383  89 
 2531  1571  911  2459  449  179  2243  1163  743 
 1901  311  389  2213  2003  1913  1493  1433  593 
 2621  2591  431  281  2063  1613  1223  773  653 
 2711  2699  2609  1019  59  1283  1013  683  173 

ASSOCIATIVNYJ KVADRAT
 2549  1499  809  479  2633  911  389  281  2699 
 113  659  2129  2273  2339  1571  1493  1613  59 
 11  101  1289  191  2693  2459  1901  2591  1013 
 1439  2069  2411  1559  569  743  2003  773  683 
 1703  2291  509  2543  1361  179  2213  431  1019 
 2039  1949  719  1979  2153  1163  311  653  1283 
 1709  131  821  263  29  2531  1433  2621  2711 
 2663  1109  1229  1151  383  449  593  2063  2609 
 23  2441  2333  1811  89  2243  1913  1223  173

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

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

[Nataly-Mak]

Раз с идеальными квадратами 9-го порядка всё плохо, решила попробовать метод точных ортогональных покрытий для построения минимального пандиагонального квадрата 7-го порядка из последовательных простых чисел.
Я много занималась поиском этого квадрата, но не методом точных ортогональных покрытий.
Лучшее найденное мной решение с 4 дырками:

151 139 227 181 13 79 7
43 11 73 157 49* 253* 211
167 137 97 193 23 31 149
107 109 131 113 199 97* 41
173 101 59 17 197 71 179
53 239 127 89 233 37 19
103 61 83* 47 83 229 191

$S=797$

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

7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 
163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 

Нашла замечательный анализ типов цепочек и типов точных покрытий для пандиагональных квадратов 7-го порядка с магической константой $S=733$, который годится и для искомого квадрата из последовательных простых чисел:

whitefox в сообщении #759141 писал(а):

Рассмотрим числа Массива №1 по модулю 4.

Получим следующий комплект вычетов:

1 -- 22 шт
3 -- 27 шт

$733\equiv1\pmod4$

Поэтому сумма вычетов одного ряда равна одному из чисел: 9, 13, 17, 21.

Каждое из этих чисел имеет единственное представление в виде суммы семи слагаемых принадлежащих множеству {1, 3}. А именно:

9=1+1+1+1+1+1+3
13=1+1+1+1+3+3+3
17=1+1+3+3+3+3+3
21=3+3+3+3+3+3+3

Сумма вычетов всего квадрата равна 103.

Пусть x -- число строк с суммой 9
y -- число строк с суммой 13
z -- число строк с суммой 17
u -- число строк с суммой 21

Составим следующую систему уравнений:

$\begin{cases} 9x+13y+17z+21u=103\\ x+y+z+u=7\\ 6x+4y+2z=22\\ x+3y+5z+7u=27 \end{cases}$

После приведения получим:

$\begin{cases} x=z+2u-3\\ y=10-2z-3u \end{cases}$

Эта система имеет десять решений:

1,4,0,2
3,1,0,3
0,5,1,1
2,2,1,2
1,3,2,1
3,0,2,2
0,4,3,0
2,1,3,1
1,2,4,0
2,0,5,0

Массив чисел в нашем примере имеет такое же разложение в соответствии с вычетами по модулю 4:

вычет 1 (22 шт)
13  17  29  37  41  53  61  73  89  97  101  109  113  137  149  157  173  181  193  197  229  233 
вычет 3 (27 шт) 
7  11  19  23  31  43  47  59  67  71  79  83  103  107  127  131  139  151  163  167  179  191  199  211  223  227  239 

Кроме того, $797\equiv1\pmod4$.

Замечательно! Анализ уже сделан. Осталось поработать ещё немного

-- Сб июл 11, 2015 12:31:22 --

Один из возможных шаблонов искомого квадрата:

3  1  3  1  3  3  3 
3  1  1  1  1  1  1 
3  3  3  3  1  1  3 
1  1  1  3  1  1  1 
3  3  3  3  3  1  1 
1  3  3  3  1  3  3 
3  1  3  3  3  3  1

Шаблон получен из следующего приближения к решению с 5 дырками (дырки помечены звёздочкой):

131 137 223 149 11 139 7
67 13 97 173 57* 233 157
163 167 83 179 17 37 151
73 109 117* 127 181* 101 89
191 71 43 31 227 53 181
41 239 199 79 197 23 19
131* 61 35* 59 107 211 193

$S=797$

Из этого шаблона можно получить одну из моделей комплекта 4-х точных попарно ортогональных покрытий массива.
По этой модели можно попытаться найти реальный комплект.
Всё-таки для порядка 7 поиск должен быть легче, чем для порядка 9, хотя не настолько легче, чтобы сразу всё нашлось.
В той теме комплект из 4-х точных попарно ортогональных покрытий массива для магической константы $S=733$ так и не удалось найти.

[Nataly-Mak]

Цитата:

В той теме комплект из 4-х точных попарно ортогональных покрытий массива для магической константы $S=733$ так и не удалось найти.

(та тема - topic73817.html)

А он ведь существует!
Jarek нашёл минимальный пандиагональный квадрат 7-го порядка из различных простых чисел, но он искал его не методом точных ортогональных покрытий.
Этому решению, конечно же, соответствует комплект из 4-х точных попарно ортогональных покрытий массива.

whitefox
у вас была программа поиска комплекта из 4-х точных попарно ортогональных покрытий массива для магической константы $S=733$.
Вы не могли бы модифицировать её, чтобы она стала искать комплект для магической константы $S=797$?

[Nataly-Mak]

Вот и модель комплекта готова:

#1
1 1 3 3 3 3 3
1 1 1 1 1 1 3
1 1 3 3 3 3 3
1 1 1 1 1 1 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3

#2
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 1 1 3 3 3
1 1 1 1 3 3 3

#3
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 1 1 1 1 3
1 1 1 1 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3
1 1 3 3 3 3 3

#4
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 3 3 3 3 3
1 1 1 1 3 3 3
1 1 1 1 3 3 3
1 1 3 3 3 3 3
1 1 1 1 3 3 3

Интересный вопрос: много ли будет моделей комплектов

Ну, осталась самая малость: найти по данной модели реальный(е) комплект(ы) из 4-х точных попарно ортогональных покрытий вот этого массива чисел:

7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239

Правда, ещё никто не знает, существует ли хотя бы один такой реальный комплект.

[whitefox]

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

whitefox
у вас была программа поиска комплекта из 4-х точных попарно ортогональных покрытий массива для магической константы $S=733$.
Вы не могли бы модифицировать её, чтобы она стала искать комплект для магической константы $S=797$?

Не смог найти, похоже, она канула в Лету.

[Nataly-Mak]

Э-э-э... вы же её несколько раз выкладывали в теме "Дьявольские магические квадраты из простых чисел" ссылками на Яндекс-диск. Неужели вы и там всё удалили? Правда, я эту программу не скачивала и не крутила. Но о ней писали svb и Pavlovsky, значит, они скачали и опробовали.

[whitefox]

Удалил.
Видимо, осерчал на неё сильно, а из-за чего — уже не помню.

[Nataly-Mak]

Ну и ладно.
А программа генерации полумагов и их проверки на пандиагональный квадрат тоже канула в Лету?
Эту программу я скачивала и даже крутила, но никак не могу найти её у себя.

-- Сб июл 11, 2015 21:56:23 --

Вот эта программа в работе

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

А я ищу решение $S=741$ по программе whitefox.



Почти 10 часов работает программа, проверено около 17 млн. полумагических квадратов, около 5 млн. магических квадратов.
Д-а-а-а, пандиагональные квадраты из различных простых чисел - редкие жемчужины среди полумагических и магических квадратов

-- Сб июл 11, 2015 22:00:20 --

Папку с исполняемой программой нашла! (надо было глянуть на окно программы, там же написан путь к программе).
Но в папке нет исходника

[Nataly-Mak]

Сейчас запустила эту программу для магической константы $S=797$. Программа работает!



Но! она ищет пандиагональный квадрат 7-го порядка из любых (различных) простых чисел, а нам надо из последовательных простых чисел. В этом случае набор (массив) простых чисел будет всего один вместо "не менее 30000".
Кстати, пандиагональный квадрат 7-го порядка из произвольных (различных) простых чисел с магической константой $S=797$ существует, его нашёл Jarek в рамках конкурса по пандиагональным квадратам из простых чисел.