Кортежи последовательных простых чисел

[gris]

встретил кортеж квадриллионных простых по шаблону расстояний $0,6,98,6,100,6,18,6,74,6,18,6,100,6,98,6$.
Я понял, что кортеж получен так: шаблон двигали по массиву простых и проверяли совпадения при минимальной оптимизации. Или это делается более сложно?

[Dmitriy40]

Можно конечно и просто по простым двигать и проверять, но тут скорость ограничена скоростью генератора простых, примерно $10^{13}$ чисел в час (4 ядра на 3.5ГГц). Но поиск заданного паттерна можно вести и быстрее, где-то уже объяснял с примерами как (здесь и вокруг). Конкретно этот у меня ищется со скоростью $10^{18}$ чисел в час. Общая идея: не все числа допустимы в качестве первого, потому что тогда следующие в паттерне не будут простыми. Для этого паттерна из любых подряд $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$ чисел лишь одно нужно проверять дальше, остальные гарантированно не подходят. Из любых подряд 13 квадриллионов чисел (произведение первых 14 простых) проверять надо лишь 13 миллиардов, или одну миллионную. Т.е. для проверки всего интервала в 13 квадриллионов чисел в любом месте числовой оси достаточно проверить лишь $13 \cdot 16 = 208$ миллиардов чисел на простоту (а часто хватит и 25-40 миллиардов).
Причём чем длиннее паттерн, тем быстрее может идти проверка, но правда и тем дальше он обычно находится.

Ну и квадриллионы - далеко не рекорд, некоторые паттерны я проверял до $10^{27}$.

Остальные вопросы или непонятны, или не могу дать ответа.

-- 05.01.2020, 20:40 --

Как понимаю вот встреченный Вами кортеж: n=16, 520210977238677833: 0 6 104 110 210 216 234 240 314 320 338 344 444 450 548 554. Найден с нуля за 23 минуты.
Реально он был найден в рамках boinc проекта поиска КПППЧ (по инициативе известной (и забаненной) здесь Макаровой) как n=18, 520210977238677799: 0 34 40 138 144 244 250 268 274 348 354 372 378 478 484 582 588 622. Там да, ищутся паттерны по определённым правилам на множестве всех простых, подряд, решетом Эратосфена. Соответственно и время поиска выражается в тысячах процессоро-лет счёта.

[gris]

спасибо. Я Вашего ответа и ждал. А вот паттерн длиной 25 или 36 где может реализоваться? И сколько времени это займёт на таком компьютере?

да. это он. спасибо.

[Dmitriy40]

Паттерны длиной 25 нужны для магических квадратов 5х5, длиной 36 для квадратов 6х6. Квадраты выше чем 4х4 могут быть с разными свойствами.
Паттерны длиной 27 дадут магические кубы. И т.д.
Применения паттернов длиной не вида $n^2, b^3, n^4, ..., n^k$ мне неизвестны. Лишь чисто спортивный интерес (ну ещё в OEIS себя увековечить ).
Пока что нашлись кортежи длиной 24 и кажется 19 (нечётные искать сильно труднее, они намного реже встречаются).

Где могут быть паттерны длиной 25 и более - очень большой вопрос! В безуспешных попытках найти один из вариантов квадрата 5х5 (паттерн длиной 25 простых) я и дошёл до $10^{27}$. Займёт это у меня - годы, или тысячи лет, заранее неизвестно (но многое, что можно найти за недели, уже нашли). Хотя Врублёвский находил кортежи по известным паттернам на порядки быстрее меня, как не представляю, видимо математику вычетов лучше понимает, или имеет доступ к вычислительным кластерам.
Но вообще всё сильно зависит от конкретного паттерна, некоторые встречаются раньше, некоторые сильно дальше. Чем "плотнее" паттерн (меньше разница первого и последнего числа), тем его найти труднее, но могут быть и исключения. Вон паттерны нечётной длины сильно реже попадаются. И зависимость не только от длины или диаметра (разницы первого и последнего числа), но и от "внутренностей" тоже, два паттерна одной длины и одного диаметра могут искаться с на порядки отличающейся скоростью, ну и находиться тоже.

-- 05.01.2020, 21:38 --

Как Вы говорите, для любителей, забавное наблюдение: простые числа встречаются настолько часто, что их список совершенно невыгодно откуда-то скачивать, даже как угодно упакованный, быстрее их вычислить локально на самом компьютере. По крайней мере для не слишком больших чисел, скажем до $10^{20}$. Простая оценка на глазок в области чисел около $10^{18}$: скорость генерации примерно 700млн интервала в секунду (на ядро любого современного процессора), простых в нём будет порядка 35млн, даже при кодировании в один байт на простое (что в общем несложно) это потребует трафик сети 35МБайт/с или почти 300Мбит/с. А если ядер больше одного ... то необходимый трафик возрастает в разы.
Если же аккуратно переписать генератор под использование GPU, то граница отодвинется ещё на два-три порядка.
И хотя в сети есть выложенные списки простых (видел вплоть до $10^{12}$), да и просьбы скачать такие списки нередки, но для тех кто в теме это выглядит забавно: проще и быстрее взять готовую быструю программу и самому нагенерить сколько надо.

[gris]

я так понял. что найденный кортеж складывается в магический квадрат. равно как и его паттерн. то есть. если взять любой квадрат. превратить его в массив, отсортировать и использовать как паттерн, то можно найти квадрат из последовательных простых.
а в A256234 приведены начальные элементы кортежей, которые складываются в квадраты. последнего кортежа там нет. или эта последовательность не пополняется?

[Dmitriy40]

gris
Да, складывается:

Используется синтаксис Text

n=16, 520210977238677833: 0 6 104 110 210 216 234 240 314 320 338 344 444 450 548 554
        Ассоцитивный                                Пандиагональный                          Стенли
0       320     344     444             0       320     240     548             0       6       234     240
450     338     314     6               344     444     104     216             104     110     338     344
548     240     216     104             314     6       554     234             210     216     444     450
110     210     234     554             450     338     210     110             314     320     548     554
S=1108/2080843908954712440

Первая сумма для паттерна, вторая для кортежа из конкретных простых.

В OEIS в комментарии к b-file (таблице всех 56 штук) указано что проверено лишь до 5e17 в 2017 году, а этот кортеж найден дальше и недавно, потому он туда и не входит. Как не входят и ещё 20 известных квадратов в диапазоне 6e17-9e17 и начале 10e17, найденных в старом boinc проекте. С тех пор я не слежу за поиском квадратов. В диапазоне 5e17 сейчас в новом boinc проекте обработано до 5.3e17, т.е. примерно треть пропущенного ранее, и в этой трети присутствуют 7 квадратов (не показываю т.к. думаю Макарова их уже показала у себя) и данный является четвёртым из них. Добавлять их по одному-два в OEIS откровенно гемор, очень уж долго там утверждают правки и не дают (мне) править более трёх штук одновременно. Закроют товарищи весь пропущенный интервал 5e17, тогда можно будет и добавить (если они сами не добавят, OEIS открыта всем) все найденные квадраты вплоть до 9e17, или даже подождать пока и его закроют.

gris в сообщении #1433617 писал(а):

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

Да, можно. Именно так я и искал квадрат 5х5, по известным паттернам, которые точно складываются в квадрат.
Но это весьма и весьма трудоёмкий процесс, особенно для длинных или "особо хитрых" паттернов, например для квадрата 5х5 как сказал выше я не нашёл кортежа из простых вплоть до 1e27.

И ещё, квадратов сейчас найдено меньше сотни в сумме, вроде бы, а вот паттернов точно складывающихся в квадраты 4х4 лишь до диаметра (напомню, разница большего и меньшего числа) 200 известно 373 варианта, из них 13 из только простых близнецов. И очевидно что далеко не все эти квадраты найдены (хотя все самые интересные/"вкусные" уже найдены, поискать можно здесь по форуму). Хотя в предыдущем boinc проекте были проверены все простые до 1e18.

Кстати, для этого паттерна выше следующего вхождения нет вплоть до 2e19, т.е. минимум в 40 раз дальше первого обнаружения. Вот так вот ...

PS. В A256234 приведены не начальные числа кортежей, а магические суммы квадратов. Для данного она $S=2080843908954712440$, именно она будет в данной последовательности. Об этом прямо сказано в поле EXAMPLE последовательности.

[Dmitriy40]

Не понял завершена ли тема, так что добавлю ещё про скорость поиска и вероятность нахождения кортежей по известному паттерну.
Вот тот изначальный паттерн, кортеж по которому нашёлся за 23 минуты счёта, ради интереса продолжил поиск, думал сейчас как повалятся по штуке в час-два, ага, прошло уже 5 суток, однако второго вхождения так и не найдено! Первое было на 52e16, сейчас проверено уже до 15000e16. Странно, обычно они встречаются чаще, однако ж бывает и вот так ... А значит первое вхождение — счастливая случайность. Или неожиданная ошибка в давно проверенной программе, тоже не исключено.

[gris]

Dmitriy40 в сообщении #1434388 писал(а):

Или неожиданная ошибка в давно проверенной программе, тоже не исключено.

в чём ошибка? это же на самом деле последовательные простые?

(Оффтоп)

владелец мопеда пока размышляет.

[Dmitriy40]

gris
Возможна ошибка в пропуске решения. И хоть они и проверяются сторонней программой (PARI/GP), но лишь подходящие кандидаты, пропущенные разумеется проверить невозможно.
Найденные решения гарантированно (с точностью до аппаратных ошибок) правильные. Да и перепроверить их секундное дело (все утилиты давно настроены), хоть в WolframAlpha.

[gris]

Dmitriy40, вот вопрос по Энциклопедии. В A175309 приведены минимальные по началу кортежи длины от двух и далее последовательно. Вы сказали, что уже найдены кортежи длиной 19 и 24. Их пока нет. А в Энциклопедии бывают последовательности с пропусками? А что с кортежем-19?

+ спасибо, посмотрел.

[Dmitriy40]

gris
Кортежи чётной длины приведены в A055382, там они есть по 24-й включительно.
В A175309 их добавить невозможно пока неизвестна 19-я, т.е. кортеж длиной 19 (в OEIS нельзя добавлять последовательности с пропусками, кажется разрешали лишь указывать известное продолжение в поле комментария). Мне почему-то помнится он был найден Врублёвским на конкурс, но кажется/возможно он не доказал его минимальность. Правда сейчас не могу найти где видел про 19-шку. Может она и не была найдена и память меня подвела ...

[Dmitriy40]

Прошло 30 дней, досчиталось до 1e21, второго кортежа так и не найдено (напомню первый был найден за 23 минуты), надоело, остановил счёт.