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

[Nataly-Mak]

Примитивный квадрат 13х13 пока не даётся

Вот какой удалось получить примитивный квадрат 17х17:

1  1  1  1  1  1  1  0  0  1  0  1  0  0  1  0  0 
 1  1  1  1  1  1  1  0  1  1  1  0  1  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  0  1  1  0  0  0  1  0  1  0 
 1  1  1  1  1  1  1  1  1  1  0  1  0  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  0  0  0  0  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  1  0  0  0  1  1  1  0  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  0  1  1  0  1  1  1  0  0  0 
 1  1  1  1  1  1  1  0  0  1  0  1  0  1  1  0  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  0  0  1  1  0  1  0  0  1  0

Это в процессе поиска квадрата 13х13. Единички - это простые числа, а нули - составные. Уже совсем мало нулей, почти все числа простые. Но почти не считается
Ну, за примитивный квадрат 17х17 даже и браться не буду, для него нужны очень большие прямоугольники. Мне бы хоть 13х13 найти.

[Nataly-Mak]

Да, получила ещё один примтивный прямоугольник 7х28, предыдущий был 7х23, добавилось 5 строк. Это совсем другой примитивный прямоугольник, в том смысле, что объединить эти два прямоугольника в один прямоугольник 7х51 нельзя, в них разности между числами не совпадают.
Но для решения сформулированной выше задачи о поиске 4-х примитивных квадратов 7х7 с одинаковой константой оба прямоугольника годятся.

(Оффтоп)

487 1777 2713 3373 3637 3673 3709
1187 2477 3413 4073 4337 4373 4409
3167 4457 5393 6053 6317 6353 6389
3677 4967 5903 6563 6827 6863 6899
7681 8971 9907 10567 10831 10867 10903
8747 10037 10973 11633 11897 11933 11969
10427 11717 12653 13313 13577 13613 13649
10691 11981 12917 13577 13841 13877 13913
16087 17377 18313 18973 19237 19273 19309
18097 19387 20323 20983 21247 21283 21319
21221 22511 23447 24107 24371 24407 24443
22717 24007 24943 25603 25867 25903 25939
24551 25841 26777 27437 27701 27737 27773
26251 27541 28477 29137 29401 29437 29473
29347 30637 31573 32233 32497 32533 32569
33091 34381 35317 35977 36241 36277 36313
33377 34667 35603 36263 36527 36563 36599
34897 36187 37123 37783 38047 38083 38119
39551 40841 41777 42437 42701 42737 42773
40867 42157 43093 43753 44017 44053 44089
46447 47737 48673 49333 49597 49633 49669
47237 48527 49463 50123 50387 50423 50459
48497 49787 50723 51383 51647 51683 51719
49927 51217 52153 52813 53077 53113 53149
61441 62731 63667 64327 64591 64627 64663
76471 77761 78697 79357 79621 79657 79693
101161 102451 103387 104047 104311 104347 104383
142537 143827 144763 145423 145687 145723 145759

[Nataly-Mak]

Задача выборки из матрицы nxm, состоящей из нулей и единиц, максимального квадрата из единиц оказалась не такой простой.
Прграмма, сделанная сахар'ом, работает только для очень маленьких матриц (не больше 50 строк и столбцов). А для матриц большего размера начинает выдавать неверные результаты.

Приглашаю коллег в тему, посвящённую этой задаче:
topic37468-15.html

Может быть, кто-нибудь заинтересуется задачей

[Nataly-Mak]

Та-а-а-к, коллеги отдыхают

Думала, как же мне обойти ограниченность моего массива простых чисел. Придумала простое решение: программу достраивания выполняю 4 раза, выбирая числа из 4-х разных массивов прсостых чисел. В результате задействовала простые числа до 600000. Уже неплохо. Получила такую матрицу 35х60:

(Оффтоп)

1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 0 1
1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1
1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1
1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0
1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1
1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0
1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0
1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0
1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0
1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1
1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 2 2 2
1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 2 2 2 2
1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 2 2 2 2
1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 2 2 2 2 2
1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

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

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

Ну, вот, теперь простая задача - найти в этой матрице квадрат 13х13 из единичек, если, конечно, он в ней есть
Смотрю, смотрю на эту матрицу, любуюсь... Однако, любоваться хорошо, а надо "включать" глазки и ручки и искать квадрат, ибо программы поиска пока нет.

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

[Nataly-Mak]

Поигралась с матрицей
Удалось выделить из неё примитивный прямоугольник 11х13 из единиц, а в оставшихся двух строках только 4 нулика. Уже совсем близко.

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

Кто знает и, главное, умеет?

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

[EtCetera]

Nataly-Mak

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

Удалось выделить из неё примитивный прямоугольник 11х13 из единиц

У меня программа смогла выделить квадрат $12\times 12$ и, по-видимому, считает, что более крупных нет:

(Матрица с выделенным квадратом 12x12)

1* 1* 1* 1* 1* 1* 1* 0  1  1* 1* 1  1  1  1  0  0  1  0  1  1* 0  1* 0  1* 0  0  0  1  0  0  0  0  1  0  1  0  0  0  1  1  0  0  0  1  1  0  0  1  1  0  1  0  0  1  1  0  0  0  1  
1  1  1  1  1  1  1  1  0  0  1  0  0  0  0  1  1  1  0  0  0  1  1  1  0  0  0  1  1  0  0  0  0  0  1  0  1  0  0  1  0  0  1  1  1  0  0  1  0  0  0  0  1  0  1  1  0  0  0  1  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1  1  1  1  1  1  1  0  1  0  0  1  0  0  0  1  1  1  1  1  1  0  0  0  1  1  1  0  0  0  1  1  0  1  1  0  0  0  0  0  1  0  0  1  1  1  1  0  1  1  0  0  0  1  0  1  1  1  0  1  
1  1  1  1  1  1  1  0  1  0  1  0  1  1  0  0  1  1  1  0  0  0  1  1  0  1  0  1  0  1  0  0  0  0  1  1  0  0  0  0  0  0  0  0  1  1  1  1  1  0  0  1  0  1  0  0  1  0  0  1  
1  1  1  1  1  1  1  0  1  1  1  0  0  1  1  0  1  1  0  0  0  0  0  0  1  1  1  0  1  0  1  0  0  0  1  1  0  1  1  1  0  1  0  0  1  0  1  0  1  0  1  0  1  0  1  0  0  1  0  1  
1* 1* 1* 1* 1* 1* 1* 0  1  1* 1* 0  0  1  1  0  1  0  0  0  1* 0  1* 0  1* 0  1  0  0  1  1  0  0  0  0  0  1  1  1  0  1  0  0  0  1  0  1  1  0  0  0  0  1  0  0  0  0  1  0  0  
1* 1* 1* 1* 1* 1* 1* 0  0  1* 1* 1  1  0  0  1  0  1  0  1  1* 0  1* 0  1* 1  0  0  0  0  1  0  1  1  1  0  0  1  0  0  1  0  1  0  1  0  0  1  0  0  0  0  0  0  1  0  1  0  0  1  
1  1  1  1  1  1  1  0  1  1  0  0  0  0  0  1  0  0  0  1  1  0  1  0  0  0  0  0  0  0  0  0  0  1  0  0  1  1  0  0  1  1  1  0  1  0  0  1  1  1  0  0  1  0  0  0  1  0  0  0  
1  1  1  1  1  1  1  0  1  1  1  1  0  0  1  0  1  1  0  0  0  1  1  1  0  1  0  0  0  1  0  0  0  1  0  1  0  0  1  0  1  0  0  1  1  0  0  1  0  1  1  0  0  0  1  0  0  1  1  0  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1  1  1  1  1  1  1  0  0  1  0  0  1  0  1  1  0  0  0  0  1  1  1  0  0  0  0  0  1  0  0  0  0  1  0  0  1  1  0  1  1  0  0  0  0  1  0  0  0  0  1  0  1  0  0  1  0  0  0  1  
1  1  1  1  1  1  1  1  0  0  0  0  0  1  1  1  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  1  0  1  1  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  1  0  1  0  
1  1  1  1  1  1  1  0  1  0  1  0  0  1  0  1  0  1  1  0  0  1  1  0  0  0  0  0  0  1  0  1  0  1  1  0  0  1  1  1  0  0  0  0  1  0  1  1  0  0  1  0  0  1  0  0  0  0  1  1  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1  1  1  1  1  1  1  1  1  1  0  0  0  1  1  1  0  1  1  0  0  0  1  0  0  1  1  0  1  0  0  0  0  0  1  1  0  1  0  0  1  0  0  0  1  1  0  0  0  0  1  0  1  0  1  0  0  0  0  0  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1  1  1  1  1  1  1  0  0  0  1  1  0  0  0  0  1  0  1  0  1  0  1  0  0  0  0  1  0  1  1  1  0  1  0  1  0  0  0  0  1  1  1  0  0  1  0  0  1  0  1  0  1  0  0  1  0  0  0  0  
1  1  1  1  1  1  1  0  1  0  1  0  1  1  0  1  0  0  1  1  0  1  1  1  1  1  0  0  1  0  1  0  0  0  1  1  1  0  1  0  0  1  0  1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  1  1  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1* 1* 1* 1* 1* 1* 1* 0  0  1* 1* 0  1  1  0  1  0  0  1  1  1* 0  1* 1  1* 0  0  0  1  0  0  0  0  1  1  1  0  0  0  0  0  0  1  0  0  1  0  0  0  1  0  0  1  0  1  1  0  0  0  0  
1  1  1  1  1  1  1  0  1  0  1  1  0  0  1  0  0  0  1  0  0  0  1  1  1  0  1  1  1  1  0  0  0  1  1  1  1  1  0  0  0  0  0  1  1  0  1  0  0  1  1  1  0  0  0  0  0  1  1  1  
1* 1* 1* 1* 1* 1* 1* 0  0  1* 1* 0  0  0  1  0  0  0  0  0  1* 1  1* 1  1* 0  0  0  1  1  1  0  1  1  0  0  0  0  1  1  0  0  1  1  0  1  1  0  1  0  0  0  0  1  0  1  1  0  0  1  
1* 1* 1* 1* 1* 1* 1* 1  1  1* 1* 1  1  1  1  1  1  1  1  1  1* 1  1* 1  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
1  1  1  1  1  1  1  0  0  1  1  1  0  0  0  0  0  0  0  0  1  1  1  0  0  0  0  0  0  1  1  1  0  0  1  0  0  0  0  1  0  0  0  1  0  1  0  0  0  1  0  1  0  1  1  1  1  2  2  2  
1  1  1  1  1  1  1  0  0  0  0  0  0  0  1  0  1  1  0  1  0  0  0  0  0  0  0  0  0  0  0  1  0  1  1  1  0  1  0  0  0  0  1  0  0  0  0  1  1  1  1  0  0  0  0  0  2  2  2  2  
1  1  1  1  1  1  1  1  0  1  1  1  1  0  1  1  0  1  1  1  1  1  0  1  1  0  0  0  0  1  1  0  1  0  1  1  0  0  0  1  0  0  0  1  1  1  0  0  1  0  0  0  0  0  1  0  2  2  2  2  
1  1  1  1  1  1  1  1  0  0  1  0  0  0  0  0  0  1  0  1  1  0  0  0  0  0  1  0  1  1  0  0  0  1  1  0  1  1  1  1  0  0  0  1  0  0  0  0  0  0  1  0  1  0  0  2  2  2  2  2  
1  1  1  1  1  1  1  0  1  0  1  0  0  0  1  0  1  1  1  1  1  1  0  1  0  1  1  0  1  1  0  1  0  1  0  1  1  0  0  1  0  1  0  1  1  0  0  1  0  2  2  2  2  2  2  2  2  2  2  2  
1  1  1  1  1  1  1  0  0  0  1  1  0  1  1  1  0  1  0  1  0  0  0  0  0  0  1  0  1  1  0  1  1  0  0  0  1  1  0  0  0  0  0  1  0  0  0  1  0  2  2  2  2  2  2  2  2  2  2  2  
1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  1  0  0  1  0  1  0  1  0  0  1  0  0  0  1  0  1  1  0  1  1  0  0  0  1  0  1  0  1  0  0  2  2  2  2  2  2  2  2  2  2  2  
1  1  1  1  1  1  1  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  
1  1  1  1  1  1  1  0  0  1  0  1  0  0  0  0  0  1  1  0  0  0  1  1  0  1  0  1  1  1  1  1  0  0  1  0  0  1  0  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  
1  1  1  1  1  1  1  0  0  0  0  0  0  0  1  0  0  1  1  0  0  0  1  1  0  1  1  1  0  0  0  0  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2

[Nataly-Mak]

О!
Это очень интересно, что у вас уже есть программа.
Да, в этой матрице у меня тоже квадрат 13х13 вроде не выделяется (но я вручную выделяла).
Пожалуйста, расскажите, по какому алгоритму делали программу.

А я всё строила матрицы и проверяла их вручную. Вконец обалдела от этого занятия. Но кажется я его нашла! Если это не мираж, то завтра перейду от единиц к числам и покажу построенный примитивный квадрат 13х13. Хотя ещё на повторяемость чисел не проверяла. Но пусть хотя бы с одинаковыми числами будет квадрат, для первого приближения годится.

[EtCetera]

Nataly-Mak

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

расскажите, по какому алгоритму делали программу

Боюсь, что это были как раз ветви и границы с небольшой начальной подготовкой.
Если у Вас есть еще крупные матрицы (длина строки которых не превышает 64, а количество строк $\text{---}$ нескольких сотен), их можно попытаться скормить моей программе для проверки правильности ее работы и задействования по прямому назначению.

[Nataly-Mak]

EtCetera в сообщении #365829 писал(а):

Боюсь, что это были как раз ветви и границы с небольшой начальной подготовкой.

Почему боитесь?

Цитата:

Если у Вас есть еще крупные матрицы (длина строки которых не превышает 64, а количество строк $\text{---}$ нескольких сотен), их можно попытаться скормить моей программе для проверки правильности ее работы и задействования по прямому назначению.

Матрицы есть и ещё будут. Если хотите, я скину вам в личку последнюю матрицу, из которой я выделила квадрат 13х13 из единиц. Проверите работу своей программы на этой матрице. Буду очень признательна, если вы поможете мне автоматизировать проверку матриц.
_______

Увы! Примитивного квадрата 13х13 пока нет. Была ошибка, и она не в выделении квадрата из матрицы, а в построении самой матрицы. Видимо, при 4-х достраиваниях в каком-то из них я забыла сменить массив простых чисел. В результате в матрице продублировались 4 столбца.
Примитивный квадрат, конечно, получился, но в нём куча одинаковых чисел, потому что 4 одинаковых столбца. Вот он:

823 3203 5003 5623 6793 9209 11399 37123 192979 192979 192979 192979 305849
1237 3617 5417 6037 7207 9623 11813 37537 193393 193393 193393 193393 306263
5857 8237 10037 10657 11827 14243 16433 42157 198013 198013 198013 198013 310883
7753 10133 11933 12553 13723 16139 18329 44053 199909 199909 199909 199909 312779
8713 11093 12893 13513 14683 17099 19289 45013 200869 200869 200869 200869 313739
12241 14621 16421 17041 18211 20627 22817 48541 204397 204397 204397 204397 317267
13627 16007 17807 18427 19597 22013 24203 49927 205783 205783 205783 205783 318653
17203 19583 21383 22003 23173 25589 27779 53503 209359 209359 209359 209359 322229
30931 33311 35111 35731 36901 39317 41507 67231 223087 223087 223087 223087 335957
36313 38693 40493 41113 42283 44699 46889 72613 228469 228469 228469 228469 341339
59581 61961 63761 64381 65551 67967 70157 95881 251737 251737 251737 251737 364607
67273 69653 71453 72073 73243 75659 77849 103573 259429 259429 259429 259429 372299
207877 210257 212057 212677 213847 216263 218453 244177 400033 400033 400033 400033 512903

И надо начинать всё сначала

[Nataly-Mak]

Ошибку нашла - причину появления в матрице одинаковых столбцов, она была в массиве простых чисел: один фрагмент был повторен дважды.

Что делать дальше?

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

"Служба" автоматической проверки матриц пока молчит
Там тоже проблема возникла: в моих матрицах больше 64 столбцов, программа не берёт такие матрицы. Но зато в матрице мало строк, можно просто повернуть матрицу на 90 градусов.

Сегодня с утра построила ещё одну матрицу - самую большую, 64 строки и 74 столбца.
Начала превращать числа этой матрицы в нули и единички, и уже проблема: Бейсик выдаёт сообщение, что не хватает памяти. А в программе всего массив простых чисел P(15700) и два двумерных массива A(64,74), B(64,74). И вот это уже для Бейсика очень много.

Так что превратить числа матрицы в нули и единички не могу уже
Поэтому привожу матрицу с числами:

(Оффтоп)

277 563 2657 4457 5077 6247 8663 10853 11797 15983 16903 18427 19373 22093 23287 25057 25933 30217 30607 33923 36577 37343 42157 46573 47393 50243 50837 55963 62897 81527 89017 90913 95933 97753 103457 129497 133723 137533 172513 176467 182107 185137 191627 192433 224677 254117 270743 294227 305303 319183 342353 365723 374273 414977 417463 428537 467927 478663 482137 519877 543967 564377 579023 614227 654077 683153 708347 774083 782177 843887 852143 859307 866773 880703
823 1109 3203 5003 5623 6793 9209 11399 12343 16529 17449 18973 19919 22639 23833 25603 26479 30763 31153 34469 37123 37889 42703 47119 47939 50789 51383 56509 63443 82073 89563 91459 96479 98299 104003 130043 134269 138079 173059 177013 182653 185683 192173 192979 225223 254663 271289 294773 305849 319729 342899 366269 374819 415523 418009 429083 468473 479209 482683 520423 544513 564923 579569 614773 654623 683699 708893 774629 782723 844433 852689 859853 867319 881249
991 1277 3371 5171 5791 6961 9377 11567 12511 16697 17617 19141 20087 22807 24001 25771 26647 30931 31321 34637 37291 38057 42871 47287 48107 50957 51551 56677 63611 82241 89731 91627 96647 98467 104171 130211 134437 138247 173227 177181 182821 185851 192341 193147 225391 254831 271457 294941 306017 319897 343067 366437 374987 415691 418177 429251 468641 479377 482851 520591 544681 565091 579737 614941 654791 683867 709061 774797 782891 844601 852857 860021 867487 881417
1237 1523 3617 5417 6037 7207 9623 11813 12757 16943 17863 19387 20333 23053 24247 26017 26893 31177 31567 34883 37537 38303 43117 47533 48353 51203 51797 56923 63857 82487 89977 91873 96893 98713 104417 130457 134683 138493 173473 177427 183067 186097 192587 193393 225637 255077 271703 295187 306263 320143 343313 366683 375233 415937 418423 429497 468887 479623 483097 520837 544927 565337 579983 615187 655037 684113 709307 775043 783137 844847 853103 860267 867733 881663
1621 1907 4001 5801 6421 7591 10007 12197 13141 17327 18247 19771 20717 23437 24631 26401 27277 31561 31951 35267 37921 38687 43501 47917 48737 51587 52181 57307 64241 82871 90361 92257 97277 99097 104801 130841 135067 138877 173857 177811 183451 186481 192971 193777 226021 255461 272087 295571 306647 320527 343697 367067 375617 416321 418807 429881 469271 480007 483481 521221 545311 565721 580367 615571 655421 684497 709691 775427 783521 845231 853487 860651 868117 882047
5101 5387 7481 9281 9901 11071 13487 15677 16621 20807 21727 23251 24197 26917 28111 29881 30757 35041 35431 38747 41401 42167 46981 51397 52217 55067 55661 60787 67721 86351 93841 95737 100757 102577 108281 134321 138547 142357 177337 181291 186931 189961 196451 197257 229501 258941 275567 299051 310127 324007 347177 370547 379097 419801 422287 433361 472751 483487 486961 524701 548791 569201 583847 619051 658901 687977 713171 778907 787001 848711 856967 864131 871597 885527
5857 6143 8237 10037 10657 11827 14243 16433 17377 21563 22483 24007 24953 27673 28867 30637 31513 35797 36187 39503 42157 42923 47737 52153 52973 55823 56417 61543 68477 87107 94597 96493 101513 103333 109037 135077 139303 143113 178093 182047 187687 190717 197207 198013 230257 259697 276323 299807 310883 324763 347933 371303 379853 420557 423043 434117 473507 484243 487717 525457 549547 569957 584603 619807 659657 688733 713927 779663 787757 849467 857723 864887 872353 886283
7753 8039 10133 11933 12553 13723 16139 18329 19273 23459 24379 25903 26849 29569 30763 32533 33409 37693 38083 41399 44053 44819 49633 54049 54869 57719 58313 63439 70373 89003 96493 98389 103409 105229 110933 136973 141199 145009 179989 183943 189583 192613 199103 199909 232153 261593 278219 301703 312779 326659 349829 373199 381749 422453 424939 436013 475403 486139 489613 527353 551443 571853 586499 621703 661553 690629 715823 781559 789653 851363 859619 866783 874249 888179
8713 8999 11093 12893 13513 14683 17099 19289 20233 24419 25339 26863 27809 30529 31723 33493 34369 38653 39043 42359 45013 45779 50593 55009 55829 58679 59273 64399 71333 89963 97453 99349 104369 106189 111893 137933 142159 145969 180949 184903 190543 193573 200063 200869 233113 262553 279179 302663 313739 327619 350789 374159 382709 423413 425899 436973 476363 487099 490573 528313 552403 572813 587459 622663 662513 691589 716783 782519 790613 852323 860579 867743 875209 889139
12241 12527 14621 16421 17041 18211 20627 22817 23761 27947 28867 30391 31337 34057 35251 37021 37897 42181 42571 45887 48541 49307 54121 58537 59357 62207 62801 67927 74861 93491 100981 102877 107897 109717 115421 141461 145687 149497 184477 188431 194071 197101 203591 204397 236641 266081 282707 306191 317267 331147 354317 377687 386237 426941 429427 440501 479891 490627 494101 531841 555931 576341 590987 626191 666041 695117 720311 786047 794141 855851 864107 871271 878737 892667
12253 12539 14633 16433 17053 18223 20639 22829 23773 27959 28879 30403 31349 34069 35263 37033 37909 42193 42583 45899 48553 49319 54133 58549 59369 62219 62813 67939 74873 93503 100993 102889 107909 109729 115433 141473 145699 149509 184489 188443 194083 197113 203603 204409 236653 266093 282719 306203 317279 331159 354329 377699 386249 426953 429439 440513 479903 490639 494113 531853 555943 576353 590999 626203 666053 695129 720323 786059 794153 855863 864119 871283 878749 892679
13171 13457 15551 17351 17971 19141 21557 23747 24691 28877 29797 31321 32267 34987 36181 37951 38827 43111 43501 46817 49471 50237 55051 59467 60287 63137 63731 68857 75791 94421 101911 103807 108827 110647 116351 142391 146617 150427 185407 189361 195001 198031 204521 205327 237571 267011 283637 307121 318197 332077 355247 378617 387167 427871 430357 441431 480821 491557 495031 532771 556861 577271 591917 627121 666971 696047 721241 786977 795071 856781 865037 872201 879667 893597
13627 13913 16007 17807 18427 19597 22013 24203 25147 29333 30253 31777 32723 35443 36637 38407 39283 43567 43957 47273 49927 50693 55507 59923 60743 63593 64187 69313 76247 94877 102367 104263 109283 111103 116807 142847 147073 150883 185863 189817 195457 198487 204977 205783 238027 267467 284093 307577 318653 332533 355703 379073 387623 428327 430813 441887 481277 492013 495487 533227 557317 577727 592373 627577 667427 696503 721697 787433 795527 857237 865493 872657 880123 894053
767441 782087 817291 857141 886217 911411 977147 985241 1046951 1055207 1062371 1069837 1083767
204517 204803 206897 208697 209317 210487 212903 215093 216037 220223 221143 222667 223613 226333 227527 229297 230173 234457 234847 238163 240817 241583 246397 250813 251633 254483 255077 260203 267137 285767 293257 295153 300173 301993 307697 333737 337963 341773 376753 380707 386347 389377 395867 396673 428917 458357 474983 498467 509543 523423 546593 569963 578513 619217 621703 632777 672167 682903 686377 724117 748207 768617 783263 818467 858317 887393 912587 978323 986417 1048127 1056383 1063547 1071013 1084943
252157 252443 254537 256337 256957 258127 260543 262733 263677 267863 268783 270307 271253 273973 275167 276937 277813 282097 282487 285803 288457 289223 294037 298453 299273 302123 302717 307843 314777 333407 340897 342793 347813 349633 355337 381377 385603 389413 424393 428347 433987 437017 443507 444313 476557 505997 522623 546107 557183 571063 594233 617603 626153 666857 669343 680417 719807 730543 734017 771757 795847 816257 830903 866107 905957 935033 960227 1025963 1034057 1095767 1104023 1111187 1118653 1132583
259411 259697 261791 263591 264211 265381 267797 269987 270931 275117 276037 277561 278507 281227 282421 284191 285067 289351 289741 293057 295711 296477 301291 305707 306527 309377 309971 315097 322031 340661 348151 350047 355067 356887 362591 388631 392857 396667 431647 435601 441241 444271 450761 451567 483811 513251 529877 553361 564437 578317 601487 624857 633407 674111 676597 687671 727061 737797 741271 779011 803101 823511 838157 873361 913211 942287 967481 1033217 1041311 1103021 1111277 1118441 1125907 1139837
292183 292469 294563 296363 296983 298153 300569 302759 303703 307889 308809 310333 311279 313999 315193 316963 317839 322123 322513 325829 328483 329249 334063 338479 339299 342149 342743 347869 354803 373433 380923 382819 387839 389659 395363 421403 425629 429439 464419 468373 474013 477043 483533 484339 516583 546023 562649 586133 597209 611089 634259 657629 666179 706883 709369 720443 759833 770569 774043 811783 835873 856283 870929 906133 945983 975059 1000253 1065989 1074083 1135793 1144049 1151213 1158679 1172609
310747 311033 313127 314927 315547 316717 319133 321323 322267 326453 327373 328897 329843 332563 333757 335527 336403 340687 341077 344393 347047 347813 352627 357043 357863 360713 361307 366433 373367 391997 399487 401383 406403 408223 413927 439967 444193 448003 482983 486937 492577 495607 502097 502903 535147 564587 581213 604697 615773 629653 652823 676193 684743 725447 727933 739007 778397 789133 792607 830347 854437 874847 889493 924697 964547 993623 1018817 1084553 1092647 1154357 1162613 1169777 1177243 1191173
324301 324587 326681 328481 329101 330271 332687 334877 335821 340007 340927 342451 343397 346117 347311 349081 349957 354241 354631 357947 360601 361367 366181 370597 371417 374267 374861 379987 386921 405551 413041 414937 419957 421777 427481 453521 457747 461557 496537 500491 506131 509161 515651 516457 548701 578141 594767 618251 629327 643207 666377 689747 698297 739001 741487 752561 791951 802687 806161 843901 867991 888401 903047 938251 978101 1007177 1032371 1098107 1106201 1167911 1176167 1183331 1190797 1204727
335857 336143 338237 340037 340657 341827 344243 346433 347377 351563 352483 354007 354953 357673 358867 360637 361513 365797 366187 369503 372157 372923 377737 382153 382973 385823 386417 391543 398477 417107 424597 426493 431513 433333 439037 465077 469303 473113 508093 512047 517687 520717 527207 528013 560257 589697 606323 629807 640883 654763 677933 701303 709853 750557 753043 764117 803507 814243 817717 855457 879547 899957 914603 949807 989657 1018733 1043927 1109663 1117757 1179467 1187723 1194887 1202353 1216283
373363 373649 375743 377543 378163 379333 381749 383939 384883 389069 389989 391513 392459 395179 396373 398143 399019 403303 403693 407009 409663 410429 415243 419659 420479 423329 423923 429049 435983 454613 462103 463999 469019 470839 476543 502583 506809 510619 545599 549553 555193 558223 564713 565519 597763 627203 643829 667313 678389 692269 715439 738809 747359 788063 790549 801623 841013 851749 855223 892963 917053 937463 952109 987313 1027163 1056239 1081433 1147169 1155263 1216973 1225229 1232393 1239859 1253789
421621 421907 424001 425801 426421 427591 430007 432197 433141 437327 438247 439771 440717 443437 444631 446401 447277 451561 451951 455267 457921 458687 463501 467917 468737 471587 472181 477307 484241 502871 510361 512257 517277 519097 524801 550841 555067 558877 593857 597811 603451 606481 612971 613777 646021 675461 692087 715571 726647 740527 763697 787067 795617 836321 838807 849881 889271 900007 903481 941221 965311 985721 1000367 1035571 1075421 1104497 1129691 1195427 1203521 1265231 1273487 1280651 1288117 1302047
427711 427997 430091 431891 432511 433681 436097 438287 439231 443417 444337 445861 446807 449527 450721 452491 453367 457651 458041 461357 464011 464777 469591 474007 474827 477677 478271 483397 490331 508961 516451 518347 523367 525187 530891 556931 561157 564967 599947 603901 609541 612571 619061 619867 652111 681551 698177 721661 732737 746617 769787 793157 801707 842411 844897 855971 895361 906097 909571 947311 971401 991811 1006457 1041661 1081511 1110587 1135781 1201517 1209611 1271321 1279577 1286741 1294207 1308137
430057 430343 432437 434237 434857 436027 438443 440633 441577 445763 446683 448207 449153 451873 453067 454837 455713 459997 460387 463703 466357 467123 471937 476353 477173 480023 480617 485743 492677 511307 518797 520693 525713 527533 533237 559277 563503 567313 602293 606247 611887 614917 621407 622213 654457 683897 700523 724007 735083 748963 772133 795503 804053 844757 847243 858317 897707 908443 911917 949657 973747 994157 1008803 1044007 1083857 1112933 1138127 1203863 1211957 1273667 1281923 1289087 1296553 1310483
433501 433787 435881 437681 438301 439471 441887 444077 445021 449207 450127 451651 452597 455317 456511 458281 459157 463441 463831 467147 469801 470567 475381 479797 480617 483467 484061 489187 496121 514751 522241 524137 529157 530977 536681 562721 566947 570757 605737 609691 615331 618361 624851 625657 657901 687341 703967 727451 738527 752407 775577 798947 807497 848201 850687 861761 901151 911887 915361 953101 977191 997601 1012247 1047451 1087301 1116377 1141571 1207307 1215401 1277111 1285367 1292531 1299997 1313927
. . . . . . . . . . .
1026833 1052873 1057099 1060909 1095889 1099843 1105483 1108513 1115003 1115809 1148053 1177493 1194119 1217603 1228679 1242559 1265729 1289099 1297649 1338353 1340839 1351913 1391303 1402039 1405513 1443253 1467343 1487753 1502399 1537603 1577453 1606529 1631723 1697459 1705553 1767263 1775519 1782683 1790149 1804079

Во-первых, надо превратить эти числа в нули и единички, нули должны соответствовать составным числам, а единички - простым числам.
А потом уже выделять из полученной матрицы квадрат 13х13 из единиц.

Если повернуть эту матрицу на 90 градусов, в ней будет 74 строки и 64 столбца.
Далее подчеркну, что в матрице есть 7 готовых строк и 7 готовых столбцов (так задано при построении матрицы), то есть они полностью состоят из простых чисел. Можно удалить из исходной матрицы эти готовые столбцы и строки, тогда останется матрица из 57 строк и 67 столбцов. В этой матрице надо выделять уже квадрат не 13х13, а 6х6, что намного проще. Кстати, при ручном выделении я так всегда и поступала.

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

Что же дальше? Наверное, придётся пока отложить задачу построения пандиагонального квадрата 13-го порядка.
Коллеги упорно молчат. Pavlovsky писал, что задача построения примитивного квадрата 11х11 очень непростая. Я решила эту задачу. Задача построения примитивного квадрата 13х13 ещё более непростая. Да что-то не вижу энтузиастов

Возникшая при построении примитивного квадрата задача о выделении из матрицы, состоящей из нулей и единиц, квадрата nxn - сама по себе сложная задача. Алгоритм ручной выборки совершенно понятный, но реализовать его не так-то просто. Тоже, видимо, никого не заинтересовала задача.

У меня идей много, но очень ограничены возможности.
Вот, например, одна из идей. Вчера я показала примитивный квадрат 13х13, в котором 4 одинаковых столбца. Удалим 3 одинаковых столбца и получим примитивный прямоугольник 10х13:

823 3203 5003 5623 6793 9209 11399 37123 192979 305849
1237 3617 5417 6037 7207 9623 11813 37537 193393 306263
5857 8237 10037 10657 11827 14243 16433 42157 198013 310883
7753 10133 11933 12553 13723 16139 18329 44053 199909 312779
8713 11093 12893 13513 14683 17099 19289 45013 200869 313739
12241 14621 16421 17041 18211 20627 22817 48541 204397 317267
13627 16007 17807 18427 19597 22013 24203 49927 205783 318653
17203 19583 21383 22003 23173 25589 27779 53503 209359 322229
30931 33311 35111 35731 36901 39317 41507 67231 223087 335957
36313 38693 40493 41113 42283 44699 46889 72613 228469 341339
59581 61961 63761 64381 65551 67967 70157 95881 251737 364607
67273 69653 71453 72073 73243 75659 77849 103573 259429 372299
207877 210257 212057 212677 213847 216263 218453 244177 400033 512903

Проверила его на повторяемость чисел, в нём все числа простые и различные.

Теперь можно попробовать процедуру "чистого" достраивания. При этом надо достроить всего 3 столбца!

Однако реализовать эту идею не могу по той же причине очень ограниченной памяти в Бейсике. Максимальный массив из простых чисел я могу взять на 16000 чисел. Этого для данной задачи очень мало, здесь нужен массив примерно на 50000 простых чисел. Причём начинать его надо не сначала, а, например, с числа 305849.
Вполне может получиться достраивание

Но, увы, проблем у меня гораздо больше, чем идей. Хотя идей тоже много.

P.S. Пришлось вырезать часть матрицы: не проходит сообщение.
Сейчас выложу её на сайте.

-- Вт окт 26, 2010 07:27:50 --

Матрица здесь

[Nataly-Mak]

Попробовала процедуру "чистого" достраивания приведённого выше примитивного прямоугольника 10х13.
Взяла начальный массив, в нём первые 16000 простых чисел. Достраивание происходит, столбцов выдаётся очень много, но беда в том, что большинство чисел выходят за пределы массива и потому они не проверяются на простоту.
Вот, например, три достроенных столбца:

157109  157523  162143  164039  164999  168527  169913  1  1  1  1  1  1 
 164623  165037  169657  171553  1  1  1  1  1  1  1  1  1 
 164789  165203  169823  171719  1  1  1  1  1  1  1  1  1

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

Но ведь столбцов очень много получается, есть надежда, что достраивание выполнится - получатся три столбца, состоящие из простых чисел.

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

-- Вт окт 26, 2010 09:31:54 --

Проверила числа, заменённые единичками, 8 чисел оказались простыми.

Так возможно ли достроить? Всего три столбца!
Попробуйте же кто-нибудь Ну, никак никого не расшевелю.

[Nataly-Mak]

А между тем... Пока завтракала, компьютер искал совершенный квадрат 8-го порядка из простых чисел. Нашёл

19 5923 1019 4423 4793 1277 3793 2777
4877 1193 3877 2693 103 5839 1103 4339
499 5443 1499 3943 5273 797 4273 2297
5297 773 4297 2273 523 5419 1523 3919
1213 4729 2213 3229 5987 83 4987 1583
5903 167 4903 1667 1129 4813 2129 3313
733 5209 1733 3709 5507 563 4507 2063
5483 587 4483 2087 709 5233 1709 3733

В минимальности не уверена, так как проверяла не все потенциальные магические константы, а только с константой комплементарности кратной 6 (для такой константы больше комплементарных пар чисел).
Магическая константа квадрата равна 24024, констнта комплементарности равна 6006. Сумма чисел во всех квадратах 2х2 равна 12012.

Симпатичный квадратик. Главное - он совершенный Красивый

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

[Nataly-Mak]

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

37 97 73 863 1019 197 1423 1217 2083 2297 2287 2267
739 149 271 761 421 587 877 1847 1609 2243 2203 2153
293 613 523 487 647 827 1709 1249 1201 2131 2111 2069
1427 1223 2099 2293 2281 2251 41 103 89 859 1013 181
881 1871 1619 2239 2179 2143 743 173 281 757 397 577
1753 1279 1319 2087 2081 1951 337 643 641 443 617 709
887 1093 227 13 23 43 2273 2213 2237 1447 1291 2113
1433 463 701 67 107 157 1571 2161 2039 1549 1889 1723
601 1061 1109 179 199 241 2017 1697 1787 1823 1663 1483
2269 2207 2221 1451 1297 2129 883 1087 211 17 29 59
1567 2137 2029 1553 1913 1733 1429 439 691 71 131 167
1973 1667 1669 1867 1693 1601 557 1031 991 223 229 359

Квадрат построен из девяти пандиагональных квадратов 4-го порядка с одинаковой магической константой 4620 по решётке Россера. Магическая константа квадрата равна 13860. Может быть, это не наименьший пандиагональный квадрат 12-го порядка из простых чисел. Ну, хотя бы какой-нибудь есть.

Теперь у нас имеются пандиагональные квадраты из простых чисел порядков 4 - 12, кроме порядка 9. Для многих порядков остаётся открытым вопрос минимальности квадратов. Она установалена только для порядков 4 - 6.
Пандиагональный квадрат 13-го порядка построить пока не удалось.
Для 14-го порядка тоже можно воспользоваться решёткой Россера. Для этого надо построить 4 примитивных квадрата 7х7 с одинаковой константой, превратить их в пандиагональные квадраты и воспользоваться решёткой Россера для построения пандиагонального квадрата 14-го порядка из этих четырёх пандиагональных квадратов.
Я предлагала одну идею для такого построения: использовать примитивные прямоугольники 7х23 или 7х28. У меня есть ещё примитивный прямоугольник 7х55.
______
Сейчас хорошо рассмотрела построенный пандиагональный квадрат 11-го порядка. Полная аналогия с методом качелей! Примитивный квадрат не что иное как образующая таблица в методе качелей. Впрочем, вряд ли кто-нибудь знаком с моим методом качелей. Подробнее напишу об этом в статье, посвящённой нетрадиционным пандиагональным квадратам 11-го порядка, когда доберусь до них. Сейчас надо продолжить статью для пандиагональных квадратов порядка 8, для них уже все квадраты построены, все алгоритмы разработаны.

[Nataly-Mak]

Пришли вести от "службы" автоматической проверки матриц на предмет выделения квадратов из единиц.

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

Возлагаю большие надежды на последнюю матрицу 64х74, это самая большая матрица. Но она пока не переведена в матрицу из нулей и единиц.
Написала вчера просьбу ice00, он сразу отозвался и уже начал преобразовывать матрицу, прислал сегодня результат для чисел до миллиона. Подождём, когда он преобразует матрицу полностью, в ней не будет двоек, только нули и единицы.
Если из этой матрицы не получится выделить квадрат 13х13 из единиц, начну строить новые матрицы.

[Nataly-Mak]

Поиск продолжается, коллеги упорно молчат.
Они, может быть, уже нашли то, что я ищу

Обошла все свои проблемы, матрицы строю и полностью преобразовываю числа в нули и единицы. Добавила ещё одну порцию простых чисел, благо, генератор простых чисел у меня свой имеется. Теперь уже задействованы простые числа до 1200000.
Последняя построенная матрица 66х83 отправлена на проверку.
В предпоследних трёх или четырёх матрицах выделены квадраты 12х12. А квадрата 13х13 пока нет Это ведь тринадцать!