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

[Nataly-Mak]

И опять только квадрат 12х12
И ещё одна матрица построена 135х83, и тоже только квадрат 12х12.

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

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

И ещё одна матрица построена только что - 45х83. Ещё не проверена, "служба" автоматической проверки пока спит

Эта матрица сделана из одной предыдущей матрицы добавлением трёх порций простых чисел. А из той предыдущей матрицы (30х60) мне удалось вручную выделить квадрат 13х13, в котором только 4 нуля.

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

[Nataly-Mak]

Для всех, кто решает задачу или ещё захочет вдруг порешать, предлагаю 5 матриц из нулей и единиц.

[Nataly-Mak]

EtCetera сообщил о выделенном квадрате 13х13 утром. Этот квадрат выделен из матрицы №10, которая есть в выложенном архиве с матрицами.

EtCetera
ещё раз благодарю вас за оказанную помощь.

Перевела единички в простые числа. Как я и опасалась, в примитивном квадрате два числа повторились: 25903 и 32533. Процес построения матрицы у меня очень трудоёмкий, поэтому я не вставила в программу проверку на повторяемость чисел. К тому же, львиная доля чисел из матрицы удаляется. Так из матрицы 45х83 выделен только квадратик 13х13. Ну, вот получился примитивный квадрат с небольшим изъяном. Но принцип работы алгоритма проверен и отлажен на двух примерах - для примитивных квадратов 11х11 и 13х13.
Если писать программу на языке с хорошей памятью и быстродействием, то процесс построения матрицы будет выполняться очень быстро. Я же выполняю программу 6 раз для 6 различных массивов простых чисел, и каждый проход выполняется минут 10-15. Потом ещё преобразовываю полученную матрицу в матрицу из нулей и единиц, это тоже выполняю в 6 проходов соответственно для тех же 6 массивов простых чисел. Да ещё некоторые матрицы приходится разбивать на две, потому что полностью программа не берёт матрицу по причине недостаточной памяти. На нормальном языке всё это можно выполнить минут за 5-10. У меня на построение одной матрицы уходит примерно 1,5 часа. Было построено более десяти матриц, только из одной удалось выделить квадрат 13х13 из единиц.

Это полученный примитивный квадрат 13х13 из простых чисел:

277  719  1019  1237  1567  2503  3163   3463  10093  16363   37307  1012213  1115533
487  929  1229  1447  1777  2713  3373   3673  10303  16573  37517  1012423  1115743
2221  2663  2963  3181  3511  4447  5107   5407  12037  18307  39251  1014157  1117477
7681  8123  8423  8641  8971  9907  10567  10867  17497  23767  44711  1019617  1122937
16087  16529  16829  17047  17377  18313  18973  19273  25903  32173  53117  1028023  1131343
22717  23159  23459  23677  24007  24943  25603  25903  32533  38803  59747  1034653  1137973
26251  26693  26993  27211  27541  28477  29137  29437  36067  42337  63281  1038187  1141507
29347  29789  30089  30307  30637  31573  32233  32533  39163  45433  66377  1041283  1144603
46447  46889  47189  47407  47737  48673  49333  49633  56263  62533  83477  1058383  1161703
76471  76913  77213  77431  77761  78697  79357  79657  86287  92557  113501  1088407  1191727
225241  225683  225983  226201  226531  227467  228127   228427  235057  241327  262271  1237177  1340497
747427  747869  748169  748387  748717  749653  750313  750613  757243  763513  784457  1759363  1862683
775987  776429  776729  776947  777277  778213  778873  779173  785803  792073  813017  1787923  1891243

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

1012213 12037 18313 26993 1161703 241327 778873 1447 7681 59747 32533 77761 747869
775987 37517 10867 24007 29789 1088407 757243 2503 2963 1131343 42337 49333 226201
748169 1115533 18307 18973 27211 46447 262271 779173 1777 8123 1034653 39163 78697
226531 776429 1012423 17497 24943 30089 1191727 763513 3163 3181 16087 63281 49633
79357 748387 277 39251 19273 27541 46889 1237177 785803 2713 8423 1137973 45433
56263 227467 776729 1115743 23767 25603 30307 76471 784457 3463 3511 16529 1038187
66377 79657 748717 719 1014157 25903 28477 47189 1340497 792073 3373 8641 22717
1141507 62533 228127 776947 487 44711 25903 30637 76913 1759363 10093 4447 16829
23159 1041283 86287 749653 1019 1117477 32173 29137 47407 225241 813017 3673 8971
17047 26251 83477 228427 777277 929 1019617 32533 31573 77213 1862683 16363 5107
9907 23459 1144603 92557 750313 1237 2221 53117 29437 47737 225683 1787923 10303
5407 17377 26693 1058383 235057 778213 1229 1122937 38803 32233 77431 747427 37307
16573 10567 23677 29347 113501 750613 1567 2663 1028023 36067 48673 225983 1891243

Магическая константа квадрата равна 4178497.

Теперь предлагается построить пандиагональный квадрат 13-го порядка из простых чисел, во-первых, без повторяющихся чисел, во-вторых, с меньшей магической константой.

Есть ли у кого другие алгоритмы построения пандиагональных квадратов, порядок которых является простым числом?
Предложенный алгоритм основан на использовании примитивного квадрата.
Можно подумать над другими способами построения примитивного квадрата порядка 13 и не только, далее у нас следует пандиагональный квадрат простого порядка 17.

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

[Nataly-Mak]

(Оффтоп)

Ах, мои бедные магические квадраты! Все учёные мужи вас покинули. Ну, ничего, я по-прежнему с вами :-)

-- Пт окт 29, 2010 08:36:09 --

Обновлённые таблички для констант магических квадратов из простых чисел:

[Nataly-Mak]

По этому же алгоритму построила пандиагональный квадрат 7-го порядка из смитов. Построена матрица 29х42 при 4 готовых строках и 4 готовых столбцах; квадрат 7х7 из единичек выделила вручную. Далее заменяю в выделенном квадрате единички на числа и применяю к полученному примитивному квадрату преобразование Россера.

Это готовый пандиагональный квадрат 7-го порядка из смитов:

77782 2182 542362 396346 454 38326 180085
395842 34978 3865 257746 382 383998 160726
180346 382198 2362 160222 430366 517 81526
194746 395905 78178 4126 562162 562 1858
385942 180526 58 36382 160285 473566 778
1921 237946 396166 382594 4306 180022 34582
958 3802 214546 121 79582 160546 777982

Магическая константа равна 1237537. Но раньше я пыталась построить примитивный квадрат 7х7 путём "чистого" достраивания примитивного квадрата 5х5, у меня ничего не получилось, квадрат 6х6 получался быстро, а дальше никак. По новому алгоритму всё получилось сразу.

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

Pavlovsky
задача для вас

[Nataly-Mak]

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

158638 24214 250438 142258 382 70582 124627
141682 18742 52366 283063 454 202234 72598
124879 178474 24394 72022 160042 526 210802
90382 141826 158962 52618 302899 634 23818
230638 125059 58 42178 72166 300262 778
23962 230602 142078 178798 52798 124483 18418
958 52222 142843 202 182398 72418 320098

Построен по тому же алгоритму.

Кто меньше?

Эти смиты такие непредсказуемые. Например, магическая константа наименьшего пандиагонального квадрата 4-го порядка из смитов равна 14560 (если верить maxal'у), а для пандиагонального квадрата порядка 5 она равна 8318. Для порядка 6 наименьшая константа пока не установлена, однако уже построен квадрат с магической константой 5964. Интересная картина получается: порядок увеличивается, а наименьшая константа уменьшается.

Так какой же будет наименьшая константа пандиагонального квадрата 7-го порядка из смитов? Хороший вопрос!

[Nataly-Mak]

Ещё чуть-чуть уменьшила константу, теперь она равна 749062:

39478 2218 234418 223222 526 30298 218902
221422 29902 2038 257098 1822 74434 162346
219442 74038 2362 160546 250798 1642 40234
189922 222538 39838 2578 291658 1966 562
74794 219586 166 29938 161662 260734 2182
1678 199858 223078 74398 2722 217786 29542
2326 922 247162 1282 39874 162202 295294

[Nataly-Mak]

Сейчас хочу вернуться к поиску идеального квадрата 7-го порядка из смитов.
Готовый набор комплементарных пар программа проверяет за несколько секунд. У меня проблемы с формированием наборов комплементарных пар.

Потенциальный набор комплементарных пар должен содержать не менее 24 пар. При этом сумма чисел в паре, делённая на 2, даёт число расположенное в центральной ячейке квадрата, это число тоже должно быть смитом.

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

Идеальный квадрат 7-го порядка из простых чисел я искала очень долго, были проверены сотни наборов комплементарных пар. Квадрат найден с центральным числом 25903, константа ассоциативности равна 51806 (сумма чисел в паре комплементарных чисел), магическая константа равна 181321.



Для смитов пока найдены только наименьшие идеальные квадраты порядков 5 - 6 (автор maxal).

[Nataly-Mak]

Начала снова проверку наборов комплементарных пар для идеального квадрата 7-го порядка из смитов. Стартовала с центрального числа 29902, дошла до центрального числа 76425 (что соответствует потенциальным магическим константам от 209314 до 534975). Программа бежит очень шустро, квадратов не найдено. Отложу эту проверку, может быть, буду проверять между делом.

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

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

[Nataly-Mak]

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

Взяла готовый примитивный прямоугольник 6х7, полученный другим способом (он уже был показан выше и метод его получения описан):

58 382 23818 52222 124483 229198 275998
202 526 23962 52366 124627 229342 276142
454 778 24214 52618 124879 229594 276394
1858 2182 25618 54022 126283 230998 277798
3802 4126 27562 55966 128227 232942 279742
178474 178798 202234 230638 302899 407614 454414

Требуется достроить всего одну строку. Теоретически всё очень просто. Но с первым массивом смитов, содержащим 16000 чисел, достраивание не выполняется. Тогда я беру второй массив смитов с большими числами. Теперь достраивание выполнилось:

58 382 23818 52222 124483 229198 275998
202 526 23962 52366 124627 229342 276142
454 778 24214 52618 124879 229594 276394
1858 2182 25618 54022 126283 230998 277798
3802 4126 27562 55966 128227 232942 279742
178474 178798 202234 230638 302899 407614 454414
580054 580378 603814 632218 704479 809194 855994

Если превратить этот примитивный квдарат 7х7 в пандиагональный квадрат 7-го порядка с помощью преобразования Россера, его магическая константа будет равна 1470655. Вот в чём минус "чистого" достраивания: очень большие числа получаются в примитивном квадрате.

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

[Nataly-Mak]

Возвращаюсь к примитивному прямоугольнику 13х10:

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

Что же тут с достраиванием?
Мне хочется получить примитивный квадрат 13х13 из различных простых чисел, первый полученный квадрат имеет повторяющиеся числа, значит, всё-таки неполноценный квадрат

Итак, достраивание...
Завсегдатаям этой темы не надо объяснять, что значит достроить примитивный прямоугольник до примитивного квадрата. Требуется получить всего три новых столбца из простых чисел по закону примитивного квадрата, но чтобы все числа в новых столбцах были различные и не повторяли числа в исходном примитивном прямоугольнике.

Все мои попытки достраивания с маленькими массивами простых чисел (по 16000 чисел в каждом) дали только один столбец из 11 чисел:

683699, 684113, 688733, 690629, 691589, 695117, 696503, 700079, 713807, 719189, 742457

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

[Nataly-Mak]

Была матрица 66х83, в которой выделен прямоугольник 13х12 из единиц. Не поленилась превратить его в числа и проверить. Хороший примитивный прямоугольник! Все числа в нём различные.

823  1109  3203  5003  5623  6793  9209  26479  50789  63443  852689  1154819
991  1277  3371  5171  5791  6961  9377  26647  50957  63611  852857  1154987
1237  1523  3617  5417  6037  7207  9623  26893  51203  63857  853103  1155233
5857  6143  8237  10037  10657  11827  14243  31513  55823  68477  857723  1159853
7753  8039  10133  11933  12553  13723  16139  33409  57719  70373  859619  1161749
8713  8999  11093  12893  13513  14683  17099  34369  58679  71333  860579  1162709
12241  12527  14621  16421  17041  18211  20627  37897  62207  74861  864107  1166237
17203  17489  19583  21383  22003  23173  25589  42859  67169  79823  869069  1171199
34381  34667  36761  38561  39181  40351  42767  60037  84347  97001  886247  1188377
160591  160877  162971  164771  165391  166561  168977  186247  210557  223211  1012457  1314587
493693  493979  496073  497873  498493  499663  502079  519349  543659  556313  1345559  1647689
623431  623717  625811  627611  628231  629401  631817  649087  673397  686051  1475297  1777427
843757  844043  846137  847937  848557  849727  852143  869413  893723  906377  1695623  1997753

Тут задача совсем простая: достроить всего один столбец. Но числа здесь уже почти до 2 миллионов присутствуют, а при достраивании будут ещё больше.
У меня и нет таких больших простых чисел.

У кого есть простые числа, дайте миллиончик Генератор простых чисел есть, но он работает тем медленнее, чем больше числа.
Нужны простые числа в интервале от 1.200.000 до 2.500.000.

[Someone]

Вот здесь (http://www.fpx.de/fp/Software/Sieve.html) есть очень быстрая программа (на C), реализующая решето Эратосфена. На моём компьютере она находит все простые числа, меньшие $10^9$, за 40 секунд. К сожалению, в теперешнем виде она неудобна, так как список простых чисел она выдаёт на экран, а при попытке перенаправления ввода-вывода получается плохо. Её нужно модифицировать, чтобы она при запуске запрашивала диапазон, находила простые числа (от 1 до верхней границы диапазона или чуть больше, если это удобно для программирования) и выводила простые числа из заданного диапазона в файл.

[Nataly-Mak]

Вот выкладываю свой генератор простых чисел, это исполняемая программа:
http://www.natalimak1.narod.ru/PROST.rar

В программе реализовано решето Сундарама.
Этим генератором я сгенерировала простые числа до 1.200.000.
На запрос программы надо ввести M - нижняя граница интервала (обязательно чётное значение!), L - верхняя граница интервала (любое значение больше M).

Простые числа выводятся на экран и записываются в файл MK8.txt.
Попробуйте кто-нибудь, пожалуйста, как быстро будет программа работать. У меня после миллиона работает медленно.

Хотела новым компилятором воспользоваться, но увы Он меня не понимает. По-моему, причина в том, что я неверно задаю одну переменную, которая не является целой. А как её задать правильно, я не знаю.

svb
не подскажете?

[Nataly-Mak]

Нашла в Интернете немного простых чисел, последнее 1318699.
Там видела и очень много, до 10^{12}. Мне так много не надо.

При моих ограниченных возможностях уже получился столбец достраивания к прямоугольнику 13х12, в котором только два числа не простые:

1306069  1306237  1306483  1311103  1312999  1313959  1317487  1322449  1339627  1465837  1798939  1928677  2149003