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

[Nataly-Mak]

Программку проверки, наконец-то, написала, приведённый выше примитивный квадрат 11х11 проверила.
И вот полученный из него пандиагональный квадрат 11-го порядка с магической константой 198341:

24077 463 179 251 7369 94309 47 59443 1597 4337 6269
93967 1979 409 211 63617 7673 107 43 24203 683 5449
6287 59387 1447 233 263 29473 94399 59 67 2143 4583
5503 93979 24083 499 223 4241 8219 353 61 59513 1667
4673 6299 11 1993 479 281 64783 95383 113 79 24247
2213 5749 93997 59393 1483 277 4253 30323 443 73 137
59557 5657 6353 23 24097 569 293 5407 95929 359 97
149 24317 5839 94009 17 2029 523 4271 65633 1427 127
109 181 6203 6599 41 59407 1553 347 5419 118033 449
373 167 59627 6823 94063 29 24133 613 4283 6257 1973
1433 163 193 28307 6689 53 31 2099 593 5437 153343

Можно пытаться уменьшать магическую константу.
Но мне интересно попробовать получить таким методом примитивный квадрат 13х13.

[Nataly-Mak]

Уф!
Утомилась очень в поисках примитивного квадрата 13х13. Примитивные квадраты 11х11 уже легко получаются.
Но я ничего не могу сообразить с программной реализацией алгоритма, а вручную можно год ковыряться и ничего не найти.
Так как же реализовать алгоритм?

Частично автоматизировала, но полностью никак не могу.
Вот, например, получаю такой прямоугольник 17х38:

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  0  1  1  1  1  1  1  0  1  1  0  0  0  0  0 
 1  0  0  1  1  1  1  1  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  0  0  1  1  1  1  1  1  0  0  0  0  0  0  1  0 
 1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  1  1 
 1  0  1  1  1  1  1  1  1  1  0  1  1  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  1 
 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  0  1  1  1  1  1  1  0  1  1  1  0  1  1  0 
 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  0  1  1  1  1  1  1  1  0  0  1  1  0  0  0  0 
 1  0  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  0  1  1  1  1  1  1  0  1  0  1  0  1  0  0 
 1  0  0  1  1  1  1  1  1  0  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  0  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  0  1  1  1  1  1  1  0  1  0  0  0  1  1  0 
 1  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  0  0  0  1  1 
 1  0  1  1  1  1  1  1  1  1  0  1  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0 
 1  0  0  1  1  1  1  1  1  1  1  0  0  1  0  0  0 
 1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  0 
 1  0  0  1  1  1  1  1  1  1  0  0  1  0  0  0  1 
 1  0  0  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  1  0  0  0  0  1  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  0  0  1  0  0 
 1  1  0  1  1  1  1  1  1  1  0  1  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  1  0  0  0  0  0

В прямоугольнике 8 строк полностью состоят из простых чисел по построению.
Это автоматизировано, единички означают простые числа, о нули - не простые числа. Всё просто и ясно. Но вот дальше как программу сделать, чтобы она определила, можно ли из этого прямоугольника выкроить квадрат 13х13, чтобы в нём все числа были простые? Тоже должно быть просто, но у меня уже соображалка не работает: перетрудилась с этими прямоугольниками.

Pavlovsky
ау! Вы достраиванием занимаетесь или нет? Что там у вас получается?

Ну, все молчат и всё тут. Прямо заговор молчания
Я уже устала вручную играть с нулями и единичками.

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

[Nataly-Mak]

Да, непростая задача - построить примитивный квадрат 13х13 из простых чисел.
Вот пока максимальный примитивный прямоугольник 9х14 из простых чисел:

823  859  1237  5857  6793  7717  7753  7789  8713  9649  12241  17203  30931  36013 
 5003  5039  5417  10037  10973  11897  11933  11969  12893  13829  16421   21383  35111  40193 
 5623  5659  6037  10657  11593  12517  12553  12589  13513  14449  17041   22003  35731  40813 
 6793  6829  7207  11827  12763  13687  13723  13759  14683  15619  18211   23173  36901  41983 
 12343  12379  12757  17377  18313  19237  19273  19309  20233  21169  23761   28723  42451  47533 
 18973  19009  19387  24007  24943  25867  25903  25939  26863  27799  30391   35353  49081  54163 
 25603  25639  26017  30637  31573  32497  32533  32569  33493  34429  37021   41983  55711  60793 
 31153  31189  31567  36187  37123  38047  38083  38119  39043  39979  42571   47533  61261  66343 
 37123  37159  37537  42157  43093  44017  44053  44089  45013  45949  48541   53503  67231  72313

Дальше пока не продвинулась

Срочно требуются помощники

[svb]

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

[Nataly-Mak]

А где аннотация? Как-то не хочется скачивать кота в мешке

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

[svb]

А я бы скачал, хотя бы из любопытства Не так уж и много я пишу. Но, извольте:
1. название - "Разностные преобразования магических квадратов"
2. что может дать? Напрямую ничего не даст, но подумать есть над чем.

[Pavlovsky]

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

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

Монументальный труд. Буду неспешно изучать.

[Nataly-Mak]

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

А я бы скачал, хотя бы из любопытства Не так уж и много я пишу. Но, извольте:
1. название - "Разностные преобразования магических квадратов"
2. что может дать? Напрямую ничего не даст, но подумать есть над чем.

Я не любопытная И скачиваю только то, что мне интересно и нужно для работы.
Однако, спасибо за информацию.
А думать мне и так есть над чем, аж голова трещит

-- Чт окт 21, 2010 14:41:11 --

Вот, например, сейчас никак не соображу, как мне автоматизировать выборку столбцов и строк из примитивного прямоугольника.
Надо определить, можно ли из следующего прямоугольника 23х50 (23 строки, 50 столбцов) выделить 6 столбцов длиной 13, содержащих единички в одинаковых строках.

0  1  0  0  0  1  1  1  1  0  0  1  1  0  0  1  1  1  1  1  0  0  0   0  0  1  0  1  1  0  1  0  0  1  0  1  0  0  1  1  1  0  1  0  0  0  0  0  1  0 
 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  0  0  1  0  1  0  1  0   0  1  1  0  0  0  0  0  1  0  0  0  1  0  0  0  1  0  0  0  0  0  1  0  0  0  0 
 0  0  0  0  0  0  0  1  0  1  0  0  1  0  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  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  1  1  1  1  1  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  0  0  0  1  0  1  1  0  1  0  0  0  0  1  0 
 1  0  0  1  1  0  1  1  1  1  1  1  0  1  1  1  1  0  0  1  1  0  0   1  0  0  0  1  0  0  1  1  1  1  1  1  1  0  0  0  1  0  1  1  0  1  0  0  1  1 
 1  1  0  0  0  1  0  0  1  0  1  1  0  0  0  1  1  1  0  0  1  0  0   1  0  0  0  1  1  0  0  0  1  1  1  0  1  0  0  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 
 0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  1  0  1  1  1  1  1  1   0  0  1  1  0  1  0  0  1  1  0  0  1  0  1  0  1  1  0  0  0  0  1  1  0  0  0 
 0  1  0  0  0  0  0  0  0  1  1  1  1  0  1  0  0  1  1  0  0  1  0   1  0  0  0  0  0  1  1  0  1  1  0  0  1  0  0  1  1  0  1  0  1  1  0  0  0  1 
 0  0  1  0  0  1  1  1  1  0  0  0  0  0  1  1  1  0  0  1  0  1  0   1  1  0  0  0  0  0  1  1  0  0  1  0  0  1  0  0  1  0  0  0  1  0  0  1  0  1 
 0  0  0  1  1  0  0  1  0  1  1  0  0  1  0  0  1  1  1  1  1  1  0   1  1  0  0  0  0  1  1  1  0  0  1  0  0  0  0  1  1  1  1  0  1  0  1  1  0  0 
 0  1  1  0  1  1  1  0  0  1  1  0  0  0  0  1  1  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  0  1  0  1  0  0  0  0  1  1  0  1  0  0  1  1  0  0  0  1  0  0 
 1  1  0  1  1  0  1  0  1  0  1  0  1  1  0  0  0  0  1  1  1  1  1   1  1  1  0  0  1  1  0  1  0  0  0  1  1  1  1  1  0  1  1  0  1  1  0  1  0  0 
 1  1  1  0  1  0  1  1  1  0  0  0  0  0  0  1  0  0  1  0  1  1  1   0  0  0  0  0  1  1  0  0  1  0  0  0  0  0  0  0  0  0  0  1  0  1  0  0  1  1 
 1  0  1  1  1  0  1  0  0  1  1  0  0  1  1  1  0  0  0  1  1  0  1   0  0  1  1  0  0  0  0  0  1  0  1  1  1  1  1  0  0  0  0  0  0  0  1  1  0  0 
 1  1  1  1  1  0  0  1  1  0  0  0  1  0  1  0  0  0  0  0  0  1  0   1  1  0  1  1  0  1  0  1  0  0  0  0  0  0  0  1  0  1  1  1  0  0  0  0  0  0 
 0  0  0  0  0  1  0  0  1  0  0  0  0  1  0  1  1  0  1  1  0  0  1   1  1  1  1  1  1  1  0  0  1  1  1  1  0  1  0  1  1  1  0  0  0  1  1  1  0  0 
 0  0  0  0  0  0  0  0  1  0  1  0  0  0  0  0  1  1  0  0  0  1  0   1  1  1  0  0  1  0  0  1  1  0  0  0  1  0  1  0  1  0  1  1  0  1  0  0  1  1 
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  0  1  0  1  1  0  0   1  0  1  1  1  0  1  0  0  1  1  0  0  0  1  1  0  1  0  1  0  0  0  1  1  1  1 
 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  1   1  1  0  0  1  0  1  1  0  1  0  0  1  0  1  1  0  1  1  0  1  0  1  0  0  0  0

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

[Nataly-Mak]

Да, здесь помощь мне, похоже, не светит Пришлось новую тему открыть, может быть, там помогут.

Из приведённого прямоугольника сделала выборку ручками. Получила примитивный квадрат 13х13, в котором только 8 чисел не являются простыми. Досадно, где-то совсем близко уже. Вот выборка, 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 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
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1

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

[caxap]

(Оффтоп)

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

Надо определить, можно ли из следующего прямоугольника 23х50...

Если программа не врёт, максимальный квадрат в этой матрице -- 7x7.

[Nataly-Mak]

Похоже, что не врёт

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

А выделение прямоугольника можете по программе проверить?
У меня получилась выборка, показанная выше, это уже всё вместе объединено. Не хватает 8 единичек до полного квадрата.

Ну, а если полную матрицу проверять на выделение максимального квадрата, то надо к приведённой матрице добавить матрицу 7х23 (7 столбцов на 23 строки) из одних единиц.

[caxap]

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

А выделение прямоугольника можете по программе проверить?

Это немного сложнее, неохота переписывать. Может скините в личку весь массив, в котором нужно искать квадрат?

[Nataly-Mak]

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

[Nataly-Mak]

В процессе поиска примитивного квадрата 13х13 из простых чисел у меня получился примитивный прямоугольник 7х23, полностью составленный из простых чисел:

199  239  1879  2069  2789  3529  4349 
 823  863  2503  2693  3413  4153  4973 
 1321  1361  3001  3191  3911  4651  5471 
 5857  5897  7537  7727  8447  9187  10007 
 7753  7793  9433  9623  10343  11083  11903 
 8389  8429  10069  10259  10979  11719  12539 
 9187  9227  10867  11057  11777  12517  13337 
 9649  9689  11329  11519  12239  12979  13799 
 11617  11657  13297  13487  14207  14947  15767 
 20599  20639  22279  22469  23189  23929  24749 
 25057  25097  26737  26927  27647  28387  29207 
 29383  29423  31063  31253  31973  32713  33533 
 30931  30971  32611  32801  33521  34261  35081 
 31729  31769  33409  33599  34319  35059  35879 
 51679  51719  53359  53549  54269  55009  55829 
 53239  53279  54919  55109  55829  56569  57389 
 63241  63281  64921  65111  65831  66571  67391 
 73141  73181  74821  75011  75731  76471  77291 
 78307  78347  79987  80177  80897  81637  82457 
 80167  80207  81847  82037  82757  83497  84317 
 106291  106331  107971  108161  108881  109621  110441 
 116539  116579  118219  118409  119129  119869  120689 
 130267  130307  131947  132137  132857  133597  134417

Выбирая любые 7 строк из 23, мы будем получать различные примитивные квадраты 7х7. Их будет очень много (число сочетаний из 23 по 7). Идея возникла: проверить, не найдутся ли среди них 4 примитивных квадрата 7х7 с одинаковой магической константой будущего пандиагонального квадрата. Тогда из этих 4-х примитивных квадратов можно построить 4 пандиагональных квадрата 7-го порядка, а из них составить пандиагональный квадрат 14-го порядка по решётке Россера.

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

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

[Nataly-Mak]

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

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