Антимагические квадраты

[Yadryara]

Альфа удобна для вычисления $\pi(x)$ для сравнительно небольших $x$ — примерно до триллиона ($10^{12}$). Дальше не справляется.

Как я уже намекал, немаленькую работу проделал Droog_Andrey — Andrey V. Kulsha.

На его страничке http://www.primefan.ru/stuff/primes/table.html имеются значения $\pi(x)$ для $x$ до $10^{20}$. А некоторые и для больших $x$.

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

Yadryara в сообщении #840846 писал(а):

Примерно

$$99\,515\,726\,000\,000\,000$$

Спасибо.
А как вы посчитали?

Провёл интерполяцию "на глазок" как раз по таблице Андрея.

[Nataly-Mak]

Yadryara
спасибо ещё раз.
Всё это весьма интересно, однако для моей задачи информация разовая и вспомогательная. Это тупиковый путь для решения данной задачи: такой огромный массив простых чисел невозможно проверить за реальное время.

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

[Yadryara]

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

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

Это понятно и без слов. В том числе и поэтому я пока в основном со стороны наблюдаю.

С этими квадратами-кубами можно так увлечься, что и на другие дела времени не останется. Одна задача решается, появляется другая.

Я, кстати, про кубы сравнительно недавно ставил задачу. Там тоже перебор будь здоров.

В некоторые задачах перебор удавалось существенно сократить и решить их, но писать подробней это здесь оффтоп.

[Nataly-Mak]

Yadryara в сообщении #842568 писал(а):

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

В том всё и дело, что задачи о квадратах-кубах невозможно решить одним тупым перебором. Поиск алгоритмов в обход нереального по времени перебора и представляет самую сложную суть этих задач.
То, что невозможно сделать перебором, возможно сделать другими очень красивыми алгоритмами. Не могу ещё раз не вспомнить блестящие решения Jarek на международном конкурсе "Пандиагональные магические квадраты из простых чисел".
Эти решения восхитили не только меня, восторг выразили многие, например:
post773369.html#p773369

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

[Nataly-Mak]

Между прочим, на форуме ПЕН один форумчанин написал программку для Mathematica и проверил довольно большой массив простых чисел, где-то до простого числа 467303901007 или больше.
Классно! Мне такой большой массив проверить не по силам на QBASIC.

Решение в этом массиве не найдено для предложенной мной конструкции.
Но ведь подходящая конструкция не единственная, их можно много найти. И все надо проверить.

[Nataly-Mak]

Итак...
задача решается пока только в моей голове

Я решила действовать с другой стороны: не искать сначала подходящую конструкцию, а потом под неё искать простые числа. Сделала программу, которая проверяет сразу и глобально, а именно: она проверяет возможность составить квадрат Стенли из каждого потенциального массива из 16 последовательных простых чисел.
Вот и все дела! И не надо искать подходящие конструкции и под них потом искать последовательности простых чисел.

Теперь
ВСЕМ, ВСЕМ, ВСЕМ!

Я выкладываю свою программу. В архиве вы найдёте исходник программы ST4consec.BAS на QBASIC, исполняемую программу ST4consec.exe, текстовый файл A73.txt, в котором записан массив простых чисел в интервале [3, 1000000].
Вот и всё, что нужно для выполнения программы.
В программе M - количество простых чисел в массиве.
В данном тесте M=78497.

Просто запускаете программу (как обычно запускают исполняемые программы exe); программа выполняется несколько секунд. В файл A15.txt запишется решение, если оно будет найдено. В файл A17.txt я для проверки записываю последний проверенный массив из 16 последовательных простых (это должны быть последние 16 чисел массива, находящегося в файле A73.txt).

В данном массиве простых чисел решения, конечно, нет.

Для проверки вставьте в файл A73.txt (в любом месте, но не в конце!) последовательность

0 4 6 10 12 16 30 34 40 46 52 54 60 66 70 84

и запустите программу. Решение будет найдено мгновенно, вы увидите его в файле A15.txt (это квадрат Стенли, составленный из добавленной последовательности из 16 чисел).

Всё описала?
Если есть вопросы, пожалуйста, задавайте, не стесняйтесь :)

Ну, а дальше (в порядке гуманитарной помощи ) нужна приличная программа, которая сможет "взять" для проверки очень большой массив простых чисел. На Бейсике это невозможно, по крайней мере, в моей версии (с очень большими числами вообще не работает).

Архив на Яндекс.Диске:
http://yadi.sk/d/Ed44WjKRLTuHu

Кстати, чертовски неудобно, что не могу прикреплять файлы здесь.
Уже в какой-то теме задавала этот вопрос, ответа никакого не получила (может быть, задать вопрос в разделе "Работа форума"?).

Вот сейчас в точно такой же параллельной теме на форуме ПЕН легко прикрепила этот архив прямо в сообщении. Здесь же надо было загружать архив на Яндекс.Диск.
Может быть, всё-таки можно разрешить это делать на этом форуме не только ЗУ, а, скажем, форумчанам с довольно большим стажем?

[Nataly-Mak]

По своей программе, которая здесь выложена, проверила простые числа в интервале [3, 2140000000].
Решение в этом интервале не найдено (если нигде не ошиблась при такой кустарной работе).
Дальше мой Бейсик отказывается генерировать простые числа.

Нашла, например, такое приближение к решению (готовый квадрат Стенли):

0  64  70  114 
90  154  160  204 
102  166  172  216 
36  100  106*  150*

Стартовое простое число: D=49951927.
В этом решении всего два неправильных числа (они помечены звёздочкой). Если бы вместо 106 и 150 было 126 и 130, решение было бы правильное.

Вот что даёт WolframAlpha для стартового числа 49951927:

Select[Range[0,216],PrimeQ[49951927+#]&]

{0, 36, 64, 70, 90, 100, 102, 114, 126, 130, 154, 160, 166, 172, 204, 216}

Хороший набор из 16 последовательных простых чисел, но, увы, из чисел этого набора квадрат Стенли не составляется; надо изменить всего два числа, чтобы квадрат составился.

[Nataly-Mak]

У-р-р-р-а-а-а!

Дня два назад написала Jens Kruse Andersen, пригласила его на форум рассказать, как он нашёл свои решения.

Только что получен ответ:

Цитата:

n=4, d=545468748354 (minimal)

136367186951 added to these:

0  30  56  86 
72 102 128 158
120 150 176 206
186 216 242 272

В-о-о-о-о-т! Я нутром чувствовала, что выложенные в головоломке #731 решения не наименьшие. Так оно и есть.
Jens продолжил поиск, и вот новый результат.

Браво, Jens!

-- Ср апр 02, 2014 09:23:07 --

Вот она --- последовательность

Select[Range[0,272],PrimeQ[136367186951+#]&]

{0, 30, 56, 72, 86, 102, 120, 128, 150, 158, 176, 186, 206, 216, 242, 272}

Класс!

[Nataly-Mak]

Наименьший квадрат Стенли 4-го порядка из последовательных простых чисел от J. K. Andersen

136367186951 136367186981 136367187007 136367187037
136367187023 136367187053 136367187079 136367187109
136367187071 136367187101 136367187127 136367187157
136367187137 136367187167 136367187193 136367187223

Индекс квадрата $d=545468748354$.

[Nataly-Mak]

Однако впереди ещё более сложная задача - для n=5.
Уже полностью переключилась на эту задачу
Как уже писала, Jarek дал очень пессимистический прогноз по поводу решения данной задачи - найти квадрат Стенли 5-го порядка из последовательных простых чисел.

Ну, а может быть, не так уж и сложно

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

5 7 17 31 131
11 13 23 37 137
41 43 53 67 167
71 73 83 97 197
101 103 113 127 227

Все простые числа в этом интервале:

Select[Range[0,222],PrimeQ[5+#]&]

{0, 2, 6, 8, 12, 14, 18, 24, 26, 32, 36, 38, 42, 48, 54, 56, 62, 66, 68, 74, 78, 84, 92, 96, 98, 102, 104, 108, 122, 126, 132, 134, 144, 146, 152, 158, 162, 168, 174, 176, 186, 188, 192, 194, 206, 218, 222}

Квадрат составлен из простых чисел, соответствующих следующим разностям:

0 2 12 26 126
6 8 18 32 132
36 38 48 62 162
66 68 78 92 192
96 98 108 122 222

Тут всё просто.
А теперь надо составить квадрат Стенли 5-го порядка из последовательных простых чисел.
Я уже давно и безрезультатно пыталась решить эту задачу.

Это квадратик Стенли ну очень нужен он даст нам пандиагональный магический квадрат 5-го порядка из последовательных простых чисел (с помощью хорошо известного алгоритма Россера). Задача решается очень давно и до сих пор не решена.
Совсем недавно Jarek нашёл пандиагональный магический квадрат 4-го порядка из последовательных простых чисел (он выложен в теме "Магические квадраты").

-- Ср апр 02, 2014 13:28:10 --

Первое приближение к решению:

0 30 56 86 174*
72 102 128 158 246*
120 150 176 206 294*
186 216 242  272 360
236* 266* 292* 322* 410

Не простые числа помечены звёздочкой. Семь "дырок" в решении

Это я просто достроила минимальное решение Andersen для n=4 до квадрата Стенли 5-го порядка (достраивается элементарно).

Select[Range[0,410],PrimeQ[136367186951+#]&]
{0, 30, 56, 72, 86, 102, 120, 128, 150, 158, 176, 186, 206, 216, 242, 272, 360, 410}

Для составления квадрата Стенли использован следующий массив (числа со звёздочкой добавлены):

0  30  56  72  86  102  120  128  150  158  174*  176  186  206  216  236*  242  246*  266*  272  292*  294*  322*  360  410

[Jens K Andersen]

Hi, I just joined the forum without knowing Russian. Google Translate helps me read.

If we want the first square with consecutive primes then it's hopeless to search for fixed patterns like those with width 82, because the number of admissible patterns grows quickly with the width. We don't know in advance how wide the first case will be so even if we found it we wouldn't know it was the first.

Below are the first squares with consecutive primes for n=4. Add the initial prime to each of the 16 numbers to get the 16 primes. All the squares have widths more than twice of the smallest possible 82. They were found by generating all primes with the sieve of Eratosthenes and testing whether any 16 consecutive primes can form a square.

   136367187311 +
    0  30  56  86
   72 102 128 158
  120 150 176 206
  186 216 242 272

   399926079359 +
    0  24  54 174
   66  90 120 240
  164 188 218 338
  234 258 288 408

   501929799467 +
    0  30  56  86
   36  66  92 122
   42  72  98 128
   96 126 152 182

   809511139961 +
    0   6  42  60
  110 116 152 170
  140 146 182 200
  174 180 216 234

  1038209011981 +
    0  12  42  60
   24  36  66  84
  102 114 144 162
  152 164 194 212

  1502332658903 +
    0  12  90 120
   34  46 124 154
  160 172 250 280
  180 192 270 300

  2351122716757 +
    0   4 126 144
   36  40 162 180
   60  64 186 204
  120 124 246 264

  2401736073731 +
    0  30  60 144
   40  70 100 184
   64  94 124 208
   66  96 126 210

n=5 with consecutive primes looks infeasible.

[Nataly-Mak]

Jens K Andersen
Я очень рада видеть вас на нашем форуме.

Цитата:

All the squares have widths more than twice of the smallest possible 82. They were found by generating all primes with the sieve of Eratosthenes and testing whether any 16 consecutive primes can form a square.

Да, я тоже искала решения таким способом.
Ваши решения очень хороши!

Цитата:

n=5 with consecutive primes looks infeasible.

Почему?
Jarek говорит так же.

У Carlos Rivera есть вторая часть головоломки #731 - ассоциативные квадраты Стенли из последовательных простых чисел. Он обещал опубликовать это отдельной головоломкой. Я жду.
Вы можете начать решать эту головоломку уже сейчас
Для n=2, 3, 4 решения известны, но для n=4 не доказана минимальность.

Цитата:

n=4, d=1282288088665523520 (not minimal?)

320572022166380833 320572022166380839 320572022166380843 320572022166380849
320572022166380893 320572022166380899 320572022166380903 320572022166380909
320572022166380851 320572022166380857 320572022166380861 320572022166380867
320572022166380911 320572022166380917 320572022166380921 320572022166380927

This solution was obtained from the magic pandiagonal square of order 4 of consecutive primes.
See
http://www.primepuzzles.net/puzzles/puzz_723.htm

Это решение принадлежит Jarek.

Может быть, этот случай возможен для n=5

[Nataly-Mak]

Это наименьший ассоциативный квадрат Стенли 5-го порядка из произвольных простых чисел:

n=5, d=3505, k=1402

41 101 491 881 941
113 173 563 953 1013
251 311 701 1091 1151
389 449 839 1229 1289
461 521 911 1301 1361

http://www.primepuzzles.net/puzzles/puzz_717.htm

k - константа ассоциативности, d - индекс квадрата.

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

Select[Range[0,1320],PrimeQ[41+#]&]
{0, 2, 6, 12, 18, 20, 26, 30, 32, 38, 42, 48, 56, 60, 62, 66, 68, 72, 86, 90, 96, 98, 108, 110, 116, 122, 126, 132, 138, 140, 150, 152, 156, 158, 170, 182, 186, 188, 192, 198, 200, 210, 216, 222, 228, 230, 236, 240, 242, 252, 266, 270, 272, 276, 290, 296, 306, 308, 312, 318, 326, 332, 338, 342, 348, 356, 360, 368, 378, 380, 390, 392, 398, 402, 408, 416, 420, 422, 426, 438, 446, 450, 458, 462, 468, 480, 482, 500, 506, 516, 522, 528, 530, 536, 546, 552, 558, 560, 566, 572, 576, 578, 590, 600, 602, 606, 612, 618, 620, 632, 636, 642, 650, 660, 668, 678, 686, 692, 698, 702, 710, 716, 720, 728, 732, 746, 756, 768, 770, 780, 782, 786, 788, 798, 812, 816, 818, 822, 836, 840, 842, 846, 866, 870, 878, 888, 896, 900, 906, 912, 926, 930, 936, 942, 950, 956, 968, 972, 978, 980, 990, 992, 998, 1008, 1010, 1020, 1022, 1028, 1046, 1050, 1052, 1056, 1062, 1068, 1076, 1082, 1088, 1110, 1112, 1122, 1130, 1140, 1146, 1152, 1160, 1172, 1176, 1182, 1188, 1190, 1196, 1208, 1218, 1236, 1238, 1242, 1248, 1250, 1256, 1260, 1262, 1266, 1278, 1280, 1286, 1320}

Из массива выбрано 12 пар комплементарных чисел (комплементарные числа - это числа, дающие одинаковую сумму).

Насколько сложно найти 12 пар комплементарных простых чисел, чтобы они были последовательные и при этом составили ассоциативный квадрат Стенли

Замечу: известен уникальный результат - наименьший пандиагональный квадрат 6-го порядка из последовательных простых чисел - A073523.
Но в этом квадрате пары чисел псевдокомплементарные (термин принадлежит svb).

Итак, пандиагональные магические квадраты порядков 4 и 6 из последовательных простых чисел найдены. Порядок 5 пока сопротивляется и очень сильно
Удастся ли сломить это сопротивление?

[Nataly-Mak]

О возможности минимизации этого решения

320572022166380833 320572022166380839 320572022166380843 320572022166380849
320572022166380893 320572022166380899 320572022166380903 320572022166380909
320572022166380851 320572022166380857 320572022166380861 320572022166380867
320572022166380911 320572022166380917 320572022166380921 320572022166380927

приглашаю всех высказать свои мнения, а в особенности автора решения Jarek.

Напомню, что между ассоциативными квадратами Стенли 4-го порядка и пандиагональными магическими квадратами того же порядка существует взаимно-однозначное соответствие, устанавливаемое преобразованием Россера (и обратным ему преобразованием).
Поэтому поиск ассоциативного квадрата Стенли 4-го порядка равносилен поиску пандиагонального магического квадрата 4-го порядка.

Напомню также, что задача поиска пандиагонального магического квадрата 4-го порядка из последовательных простых чисел решалась очень давно maxal в теме "Магические квадраты". Решение найдено не было.
maxal сообщал в теме, что проверил все простые числа до 7,5 триллионов.
Задача была поставлена во втором конкурсе "Нетрадиционные пандиагональные квадраты", где тоже не была решена.

-- Чт апр 03, 2014 12:14:00 --

Насколько изящное это решение:

n=4, d=240, k=120

7 13 31 37
17 23 41 47
73 79 97 103
83 89 107 113

наименьший ассоциативный квадрат Стенли 4-го порядка из произвольных простых чисел.
Задействовано 8 пар комплементарных простых чисел из диапазона:

Select[Range[0,106],PrimeQ[7+#]&]
{0, 4, 6, 10, 12, 16, 22, 24, 30, 34, 36, 40, 46, 52, 54, 60, 64, 66, 72, 76, 82, 90, 94, 96, 100, 102, 106}

Неужели решение из последовательных простых чисел нисколько невозможно минимизировать

[Nataly-Mak]

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

Первое приближение к решению:

0 30 56 86 174*
72 102 128 158 246*
120 150 176 206 294*
186 216 242  272 360
236* 266* 292* 322* 410

Не простые числа помечены звёздочкой. Семь "дырок" в решении

Плохое приближение

Сейчас нашла свою программу, которая проверяла все потенциальные массивы из 25 последовательных простых чисел на предмет составления из них квадрата Стенли 5-го порядка.
Я проверила, кажется, все массивы простых чисел в интервале [3, 2000000000]. В этом интервале решений не найдено, если я нигде не ошиблась.

Сейчас запустила программу на поиск приближений к решению.
С ходу получила лучшее приближение с 5 "дырками", то есть 5 элементов квадрата Стенли не являются простыми числами.
Исходный массив из 25 последовательных простых чисел:

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 

Квадрат Стенли составился из такого массива:

13  17  19  23  29   35*  37  41  43  47  51*  53  55*  59   67   73  79  83  89  97   103  107   111*  113  121*

Это квадрат:

 13  17  29  73  83 
19  23  35*  79  89 
37  41  53  97  107 
43  47  59  103  113 
51*  55*  67  111*  121*

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