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

[Nataly-Mak]

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

Зря, стало быть, я сменила начальную точку в проверке?

Вернулась к той точке, на которой прервала. Проверяю опять всё подряд. На данный момент проверено до 10 510 999 343 406 (то есть от начала проверки чуть больше 3 триллионов). Программа whitefox работает. Ловлю удачу

[Nataly-Mak]

Решила изменить тактику.
Уже проверены интервалы:

7499999900000 - 11612999098199 (от начальной точки maxal, немножко с откатом назад)

19787844669502 - 20841844431437 (от начальной точки Jens K Andersen)

А сегодня решила начать с 120 триллионов, то есть резко увеличила начальную точку.
Напомню, финиш - 320572022166380833.

"Мой финиш - горизонт..." (c)

Эх, вот как нужен тут проект распределённых вычислений

[Nataly-Mak]

Производительность моего компьютера такая: за 1 час 14 минут проверены все простые в интервале длиной в 100 миллиардов натуральных чисел.
Программа whitefox сделана так, что проверяет интервалы по 2 миллиарда натуральных чисел (с небольшим наложением на стыке интервалов).

[Nataly-Mak]

Квадраты Стенли у меня несколько отодвинуты в связи с конкурсом.

А между тем, Carlos Rivera опубликовал вторую часть головоломки - ассоциативные квадраты Стенли из последовательных простых чисел
http://www.primepuzzles.net/puzzles/puzz_736.htm

Теперь решаем задачу официально
Отправляем решения на сайт http://www.primepuzzles.net

[Droog_Andrey]

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

Итого в интервале [2, 200 000 000] 11078937 простых чисел.

Кстати, простые числа в указанном интервале программой svb генерируются за несколько секунд. Проверяется одна такая порция по моей программе 3-5 секунд.

Намного быстрее программа primesieve: http://primesieve.org/

На моём 4-летнем компе её старая версия 3.8 находит простые примерно вот с такой скоростью:
http://www.primefan.ru/stuff/pict/benchmark.gif

Она умеет также печатать список найденных простых.

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

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

Если стоит задача не найти все простые вплоть до заданной нетривиальной границы, а лишь посчитать их число $\pi(x)$, то неплохим вариантом является программа fastpix, написанная в 2001 году математиком по имени Xavier Gourdon. Вот инструкция к её использованию:
https://groups.yahoo.com/neo/groups/pri ... ages/23387

Для очень больших значений $x$ функция $\pi(x)$ быстрее рассчитывается аналитическими методами:
http://www.math.uni-bonn.de/people/jbue ... icPiX.html
Однако программ, реализующих эти методы, в открытом доступе пока не наблюдалось.

[maxal]

Для полноты картины вот антимагический квадрат Стенли 4x4 составленный из минимальных последовательных простых чисел, полученный из этого пандиагонального магического квадрата:

[170693941183817 170693941183859 170693941183907 170693941183949]
[170693941183847 170693941183889 170693941183937 170693941183979]
[170693941183861 170693941183903 170693941183951 170693941183993]
[170693941183891 170693941183933 170693941183981 170693941184023]

Этот квадрат составлен из 16 последовательных простых чисел, начиная с 170693941183817 (см. A245721). Если его вычесть из остальных, то квадрат приобретает вид:

[ 0  42  90 132]
[30  72 120 162]
[44  86 134 176]
[74 116 164 206]

[whitefox]

maxal в сообщении #892112 писал(а):

[ 0 42 90 132]
[30 72 120 162]
[44 86 134 176]
[74 116 164 206]

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

0 30 44 74 
42 72 86 116 
90 120 134 164 
132 162 176 206

Два варианта одного и того же квадрата.
Его "каноническая форма" следующая:

[ 0 30 42 72]
[44 74 86 116]
[90 120 132 162]
[134 164 176 206]

Условие "каноничности" : $a_{12}<a_{13}<a_{21}<a_{31}$

[Droog_Andrey]

Droog_Andrey в сообщении #875189 писал(а):

Если стоит задача не найти все простые вплоть до заданной нетривиальной границы, а лишь посчитать их число $\pi(x)$, то неплохим вариантом является программа fastpix, написанная в 2001 году математиком по имени Xavier Gourdon. Вот инструкция к её использованию:
https://groups.yahoo.com/neo/groups/pri ... ages/23387

Недавно появилась более быстрая реализация от автора пакета primesieve:
https://github.com/kimwalisch/primecount

[Nataly-Mak]

О поиске ассоциативного квадрата Стенли 9-го порядка из различных простых чисел
(по просьбе rockclimber)

rockclimber
Ср авг 20, 2014 писал:

Цитата:

Моя новая версия программы наконец-то заработала, и даже нашла второй квадрат 7-го порядка. А пока программа работала, я сделал кое-какие расчеты, результаты которых повергли меня в некоторое уныние. Я взял числа 3, 5 и 7 (порядки квадратов), выписал в экселе в столбик. В соседний столбик выписал минимальные центральные числа соответствующих квадратов (59, 701 и 25903). В следующем столбце посчитал логарифим центрального числа, в следующем - логарифм логарифма. Посчитал коэффициент корреляции - для столбца "логарифм логарифма" он оказался равен 0,9997. То есть получается, что минимальное центральное число квадрата пропорционально е в степени е в степени порядка квадрата, для квадрата девятого порядка тогда надо искать минимальный вариант где-то в районе 4 000 000, а для одиннадцатого - 7 700 000 000. Для одного простого числа около 200 000 перебор вариантов у меня занимает сейчас 12 минут, и это время тоже будет расти наверняка экспоненциально. Вы знаете еще какие-нибудь способы кардинально сократить время? Я применил все перечисленные вами и придуманные мной самим хитрости для уменьшения времени обработки, но объем работы по-прежнему огромный. Может, есть, например, способы проверять не все простые числа в качестве центральных, а некоторые пропускать?

А вот и отличное приближение к решению, в котором всего одно не простое число (оно помечено звёздочкой):

111053 114203 158747 181253 250703 320153 342659 387203 390353
336113 339263 383807 406313 475763 545213 567719 612263 615413
432413 435563 480107 502613 572063 641513 664019 708563 711713
797063 800213 844757 867263 936713 1006163 1028669 1073213 1076363*
1119473 1122623 1167167 1189673 1259123 1328573 1351079 1395623 1398773
1441883 1445033 1489577 1512083 1581533 1650983 1673489 1718033 1721183
1806533 1809683 1854227 1876733 1946183 2015633 2038139 2082683 2085833
1902833 1905983 1950527 1973033 2042483 2111933 2134439 2178983 2182133
2127893 2131043 2175587 2198093 2267543 2336993 2359499 2404043 2407193

Автор этого решения Progger. Решение было выложено автором на форуме ПЕН.

Progger
Вс мар 08, 2015 писал:

Цитата:

Пока продолжаю поиск квадрата Стенли 9-го порядка из различных простых чисел. Проверил до $3.66 \cdot 10^6$ ...

Progger
прошу прощения за маленькую цитату с важной информацией из вашего ЛС.
Вы продолжаете поиск?

[rockclimber]

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

О поиске ассоциативного квадрата Стенли 9-го порядка из различных простых чисел

Однако! Я и забыл уже про эти расчеты
А Progger, тем временем, вплотную приблизился к расчетной точке! Интригующий момент!

[Progger]

Последнее проверенное число на данный момент - 4024357, полного квадрата пока не найдено. Есть 2 квадрата в которых только 1 элемент не является простым числом:

111053 114203 158747 181253 250703 320153 342659 387203 390353
336113 339263 383807 406313 475763 545213 567719 612263 615413
432413 435563 480107 502613 572063 641513 664019 708563 711713
797063 800213 844757 867263 936713 1006163 1028669 1073213 1076363*
1119473 1122623 1167167 1189673 1259123 1328573 1351079 1395623 1398773
1441883 1445033 1489577 1512083 1581533 1650983 1673489 1718033 1721183
1806533 1809683 1854227 1876733 1946183 2015633 2038139 2082683 2085833
1902833 1905983 1950527 1973033 2042483 2111933 2134439 2178983 2182133
2127893 2131043 2175587 2198093 2267543 2336993 2359499 2404043 2407193

1022849 1168169 1366829 1743569 2540339 3337109 3713849 3912509 4057829
1318781 1464101 1662761 2039501 2836271 3633041 4009781 4208441 4353761
1497719 1643039 1841699 2218439 3015209 3811979 4188719 4387379 4532699
1626239 1771559 1970219 2346959 3143729 3940499 4317239 4515899 4661219*
1652459 1797779 1996439 2373179 3169949 3966719 4343459 4542119 4687439
1678679 1823999 2022659 2399399 3196169 3992939 4369679 4568339 4713659
1807199 1952519 2151179 2527919 3324689 4121459 4498199 4696859 4842179
1986137 2131457 2330117 2706857 3503627 4300397 4677137 4875797 5021117
2282069 2427389 2626049 3002789 3799559 4596329 4973069 5171729 5317049

На самом деле их скорее всего больше, просто программа не предназначена для поиска неполных квадратов - они являются побочным продуктом и используются для статистики .
Что интересно, в обоих случаях элементы, не являющиеся простыми числами, раскладываются на два простых числа:
$1076363 = 389 \cdot 2767$
$4661219 = 151 \cdot 30869$,
а их пары являются простыми числами.
Ну и немного статистики:
\begin{tabular}{|l|l|} \hline 35 & 6707 \\ \hline 36 & 1664 \\ \hline 37 & 141 \\ \hline 38 & 17 \\ \hline 39 & 2 \\ \hline \end{tabular}
Тут в первом столбце - количество простых чисел в квадрате (ищется 40 чисел), второй - количество таких квадратов.
В следующей таблице приведено распределение количества неполных квадратов по интервалам. Не знаю как это можно использовать .

(большая таблица)

\begin{tabular}{|l|l|l|l|l|l|l|} \hline Начало & Конец & 39 & 38 & 37 & 36 & 35 \\ \hline 0 & 100000 & 0 & 0 & 0 & 0 & 0 \\ \hline 100000 & 200000 & 0 & 0 & 0 & 0 & 0 \\ \hline 200000 & 300000 & 0 & 0 & 0 & 0 & 1 \\ \hline 300000 & 400000 & 0 & 0 & 0 & 0 & 0 \\ \hline 400000 & 500000 & 0 & 0 & 0 & 0 & 1 \\ \hline 500000 & 600000 & 0 & 0 & 0 & 1 & 3 \\ \hline 600000 & 700000 & 0 & 0 & 0 & 0 & 3 \\ \hline 700000 & 800000 & 0 & 0 & 0 & 1 & 5 \\ \hline 800000 & 900000 & 0 & 0 & 0 & 2 & 7 \\ \hline 900000 & 1000000 & 0 & 0 & 0 & 3 & 6 \\ \hline 1000000 & 1100000 & 0 & 0 & 0 & 1 & 6 \\ \hline 1100000 & 1200000 & 0 & 0 & 0 & 1 & 24 \\ \hline 1200000 & 1300000 & 1 & 0 & 2 & 8 & 17 \\ \hline 1300000 & 1400000 & 0 & 0 & 2 & 8 & 36 \\ \hline 1400000 & 1500000 & 0 & 0 & 0 & 4 & 31 \\ \hline 1500000 & 1600000 & 0 & 0 & 0 & 8 & 40 \\ \hline 1600000 & 1700000 & 0 & 0 & 0 & 16 & 43 \\ \hline 1700000 & 1800000 & 0 & 1 & 3 & 7 & 45 \\ \hline 1800000 & 1900000 & 0 & 0 & 1 & 18 & 82 \\ \hline 1900000 & 2000000 & 0 & 0 & 1 & 21 & 84 \\ \hline 2000000 & 2100000 & 0 & 0 & 0 & 27 & 94 \\ \hline 2100000 & 2200000 & 0 & 0 & 4 & 27 & 98 \\ \hline 2200000 & 2300000 & 0 & 0 & 3 & 28 & 119 \\ \hline 2300000 & 2400000 & 0 & 0 & 3 & 31 & 146 \\ \hline 2400000 & 2500000 & 0 & 1 & 3 & 40 & 176 \\ \hline 2500000 & 2600000 & 0 & 2 & 4 & 42 & 158 \\ \hline 2600000 & 2700000 & 0 & 1 & 6 & 48 & 206 \\ \hline 2700000 & 2800000 & 0 & 0 & 6 & 56 & 217 \\ \hline 2800000 & 2900000 & 0 & 1 & 7 & 85 & 252 \\ \hline 2900000 & 3000000 & 0 & 1 & 5 & 74 & 285 \\ \hline 3000000 & 3100000 & 0 & 1 & 6 & 68 & 303 \\ \hline 3100000 & 3200000 & 1 & 1 & 2 & 95 & 356 \\ \hline 3200000 & 3300000 & 0 & 1 & 8 & 67 & 369 \\ \hline 3300000 & 3400000 & 0 & 0 & 9 & 108 & 347 \\ \hline 3400000 & 3500000 & 0 & 1 & 10 & 97 & 442 \\ \hline 3500000 & 3600000 & 0 & 1 & 9 & 112 & 509 \\ \hline 3600000 & 3700000 & 0 & 1 & 12 & 125 & 511 \\ \hline 3700000 & 3800000 & 0 & 0 & 17 & 130 & 518 \\ \hline 3800000 & 3900000 & 0 & 2 & 6 & 160 & 592 \\ \hline 3900000 & 4000000 & 0 & 2 & 12 & 145 & 575 \\ \hline \end{tabular}

[Nataly-Mak]

Progger
спасибо вам огромное, что не бросили задачу.

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



При поиске это, конечно, надо учитывать. Я в своих давних экспериментах поступала так: сначала искала ассоциативные квадраты Стенли 7-го порядка; этот поиск выполняется довольно быстро даже по моей примитивной программе. Затем для тех центральных элементов, для которых квадраты 7-го порядка нашлись, уже искала ассоциативный квадрат 9-го порядка. Увы, мне далеко уйти не удалось.

Посмотрите на иллюстрацию. Все вложенные ассоциативные квадраты - порядков 3, 5, 7 - имеют ту же самую константу ассоциативности 2518246, потому что у них одинаковый центральный элемент.
Это всё просто и очевидно.
А вот самая большая матрёшка - ассоциативный квадрат 9-го порядка - уже не получилась, то есть она вполне себе хорошая, но не все числа в ней простые.

Ну, и о дырках, то бишь неправильных элементах.
Формально в решении дырка одна (не простое число, помеченное звёздочкой), фактически же дырки две - это неправильная комплементарная пара (1076363, 1441883).

Осталось спросить третьего героя эпопеи: на чём он остановился?