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

[Dmitriy40]

Подскажите плиз кто знает, исследовался ли вопрос зависимости диаметра последовательности простых чисел от её длины? Интересует как минимум, так и максимум. Т.е. для длины 2 минимум это очевидно простые-близнецы, про максимум есть статья в вики prime gaps, а вот про последовательности длиннее 2? Например какие значения может принимать разница $p[i+26]-p[i]$ (разница между первым и 27-м последовательным простым числом)? Ну минимум можно взять из k-туплетов, максимум оценить как произведение максимального primegap на количество чисел -1 (26), но последняя оценка сильно завышена, как показывает опыт. А первая, минимума, слишком занижена, такие плотные участки весьма и весьма редки. Или все результаты есть чисто экспериментальные факты от полного перебора всех простых чисел в диапазоне? Тогда можно где-то ознакомиться с данными результатами? Может в OEIS что-то такое есть - но тогда никак не придумаю как же оно там названо?

И сопутствующий вопрос: есть где-то текущий рекорд проверенных простых чисел, подряд, начиная с начала? Не просто какое-то самое большое или заданной формы, а именно до куда проверили тотально ВСЁ с начала? И не вероятностными методами, а прямыми (всякие решета)? Видел таблицы количества простых чисел, но лишь до $10^{23}$, т.е. это и есть рекорд последовательной проверки?

[12d3]

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

Ну минимум можно взять из k-туплетов, максимум оценить как произведение максимального primegap на количество чисел -1 (26), но последняя оценка сильно завышена, как показывает опыт. А первая, минимума, слишком занижена, такие плотные участки весьма и весьма редки.

Касательно минимума, первая гипотеза Харди-Литтлвуда утверждает, что количество k-туплетов бесконечно большое для любого возможного шаблона k-туплета. И считается, что она скорее верна, чем нет, но доказательства нет.
Касательно максимума, его нет, потому что разность последовательных простых может быть сколь угодно большой.

[grizzly]

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

Например какие значения может принимать разница $p[i+26]-p[i]$ (разница между первым и 27-м последовательным простым числом)?

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

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

А первая, минимума, слишком занижена, такие плотные участки весьма и весьма редки.

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

Что касается оценки сверху, то здесь Ваш вопрос мне, надеюсь, понятен. Например, известно, что между $n^3$ и $(n+1)^3$ имеется простое число. Но неизвестно, имеется ли простое между $n^2$ и $(n+1)^2$. Очевидно, что утверждение "существует $k$ простых между $n^2$ и $(n+k)^2$ " слабее гипотезы Лежандра. Делались ли попытки доказать такую ослабленную гипотезу, я не знаю. Присоединяюсь к вопросу.

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

Видел таблицы количества простых чисел, но лишь до $10^{23}$, т.е. это и есть рекорд последовательной проверки?

Посмотрите в комментариях к A006880 -- там есть до $10^{26}$.

[Dmitriy40]

grizzly в сообщении #961903 писал(а):

Посмотрите в комментариях к A006880 -- там есть до $10^{26}$.

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

Спасибо за ответы, походу я туманно выразился, попробую уточнить. Интересуют не глобальные минимумы и максимумы (на всей числовой оси) - про них понятно что минимум это к-туплет, максимум бесконечен - а зависимость минимума и максимума от диапазона чисел. Т.е. например какое максимальную величину может принимать разность $p[i+26]-p[i]$ в интервале $i=[0..10^{18}]$? Или минимум и максимум той же разности в диапазоне $i=[10^{16}..10^{17}]$? Это чисто пример, числа хотелось бы уметь подставлять более-менее любые, хотя бы до $10^{20}$ и длин последовательностей до 10000. Даже абсолютная точность не сильно нужна, порядка 10% уже сильно облегчило бы.

PS. Про смысл. Хочу попробовать применить к поиску подходящих простых чисел для магических квадратов и кубов. Не перебирать все простые числа проверяя на квадраты, а сформировать список допустимых шаблонов (как для к-туплетов) и проверять числа на простоту только если есть вероятность что все числа по шаблону окажутся простыми. Но это реально только если шаблонов сотни-тысячи, а для последовательностей длиной от 16 (меньшие не особо интересны) её диаметр оцененный по максимуму интервала между соседними простыми числами даёт безумное количество шаблонов, я даже не оценивал ещё, навскидку видно нереальность.
Вторая мысль, не искать последовательность длины к примеру 125 (с дополнительными ограничениями) до чисел скажем $10^{40}$ если будет точно известно что её там нет и быть не может. Вообще хоть очень примерно оценить где начинаются длинные последовательности простых чисел с дополнительными ограничениями. Ограничения типа таких: A055380 или A175309.

[grizzly]

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

Или минимум и максимум той же разности в диапазоне $i=[10^{16}..10^{17}]$?

В качестве минимума можете смело принимать $p_{30}-p_{5}=113-11=102$. Такое почти наверняка встретится не раз, ну а меньше точно не будет (это не общее утверждение, а только для конкретного вопроса и для подобных, которые сколько-то реально использовать в компьютерных вычислениях).
С максимумом сложнее, конечно. Но если Вам для практических расчётов, то я бы посоветовал вычислить на этом диапазоне среднее, исходя из асимптотических законов (или даже из тех же таблиц, неважно), и накинуть сверху процентов 10-15. Это даст диапазон намного меньше любых известных теоретических оценок максимумов. Для вычислений этого Вам на ближайшие пару жизней хватит, а если и пропустите пару кортежей из 1000, вряд ли именно там будет желанное решение.

Здесь могут попасться хорошие алгоритмы к теме или просто может быть интересно.

[Dmitriy40]

Благодарю. На эту страницу кажется уже натыкался при поиске primegaps, правда детально по ссылкам не ходил.

А вот по каким критериям взяли 5-е и 30-е число? Я не понял.

И ещё. Для доказательства минимальности решения (это один из важных аспектов) нужна гарантия отсутствия пропусков вариантов, т.е. любые оценки могут быть весьма примерными, но должны быть гарантированными, иначе останется вероятность пропуска решений именно в пропущенном кортеже.
Экстраполировать поведение диаметра последовательности можно попробовать, но сильно далеко (в разы дальше просчитанной области) боюсь, ведь встречаются аномалии (те же к-туплеты), а т.к. нет вообще никаких теоретических намёков на поведение, а что есть мне недоступны для понимания ... Ох боюсь-боюсь.
Потому и обращаюсь к вам, может кто знает или слышал про готовые такие исследования.

-- 14.01.2015, 15:57 --

Я вот даже не могу понять можно ли перейти от primegap (который между двумя соседними простыми числами) к диаметру последовательности простых чисел. Как поведёт себя сумма этих primegap с учётом ограничения на допустимость последовательных чисел. Судя по картинке primegap достаточно монотонны, но что получится после суммирования нескольких их? Может ли быть 100 наибольших интервалов подряд быть (такой к-антитуплет ранга 100)?
Кстати, а искали/проверяли ли вообще такое понятие как антитуплет? Т.е. не минимальный диаметр последовательности, а максимальный? Хм, собственно он-то мне как раз и нужен.

[grizzly]

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

А вот по каким критериям взяли 5-е и 30-е число?

Ошибся, нужно было брать 31-е и 5-е -- чтобы разница тоже была 26. Критерий такой, что если может встретиться какой-нибудь кортеж хотя бы дважды, то дальше он будет повторяться с завидным (не)постоянством (только я ещё не думал над тем, может ли кортеж из моего примера встретиться второй раз). Скорее всего, существуют кортежи ещё более плотные, чем в начале натурального ряда, но опасаться этого, работая с такими короткими кортежами и маленькими числами (до $10^{100}$), точно не нужно.

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

Для доказательства минимальности решения (это один из важных аспектов) нужна гарантия отсутствия пропусков вариантов

Сложно советовать что-то практическое, ничего не зная о том, какими методами и алгоритмами решается задача перебора. У Вас уже есть рабочие алгоритмы для этой задачи или Вы только планируете их писать? В любом случае попытайтесь оценить время работы алгоритма перебора в диапазоне только всего $10^{17}$. Возьмите для первой оценки все параметры, о которых Вы спрашиваете, максимально "хорошими", но в пределах хоть какой-то правдоподобности. Я не удивлюсь, если оценка времени будет около миллиона лет и интерес в уточнении primegap (в сторону ухудшения) надолго пропадёт.

(Оффтоп)

Кроме менеджерских советов помочь ничем больше не смогу :)
А слово "туплет" -- это какой-то распространённый термин? Как-то совсем не звучит. Не лучше ли использовать "кортеж"?

[Dmitriy40]

(Оффтоп)

grizzly в сообщении #962078 писал(а):

А слово "туплет" -- это какой-то распространённый термин? Как-то совсем не звучит. Не лучше ли использовать "кортеж"?

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

-- 14.01.2015, 17:56 --

А, если с разницей 26, то немного понятней.

По алгоритмам. Их пока нет. Лишь обдумываю с какой стороны подбираться к прикидкам сложности. Может вообще нет смысла даже про алгоритмы думать.
Сейчас идёт решето Эратосфена, после него проверка на нужный класс последовательностей. Для чисел около $10^{16}$ скорость совсем не радует, меньше $10^{14}$ в сутки, и с увеличением чисел заметно падает. Причём решето занимает 99.9% времени. Вот если бы выполнить решето на 1%, потом проверить на шаблоны и если ни в один не попадает, то и не завершать решето - было бы приличное ускорение. Надеюсь. Как именно проверять на шаблоны и сколько их будет - пока без понятия, но видно, что миллиарды - перебор. Миллионы - не знаю, может для чисел за $10^{18}$ будут выгоднее. Тысячи (и десятки тысяч) могут наверное и уже помочь. А учитывая сколько существует разных шаблонов к-кортежей есть смутная надёжда что и нужных мне шаблонов будет не слишком много ...
Просто может оказаться что данные оценки уже сделаны, не хочется ломом пытаться повторить ажурные результаты.

[grizzly]

Здесь под номером 3 найдёте ссылку на текстовый файл 2012 г. свежести с известными наиболее плотными шаблонами. Для $k=26$ (26-кортеж) $p_{26}-p_0=114$, только пример шаблона у них не найден. Вопрос с границей снизу этот файл для Ваших нужд примерно решает. Вычислительную сложность вопроса тоже можно примерно оценить -- посмотрите, сколько людей уже попытались раньше и что им удалось сделать.

[Nataly-Mak]

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

(Оффтоп)

grizzly в сообщении #962078 писал(а):

А слово "туплет" -- это какой-то распространённый термин? Как-то совсем не звучит. Не лучше ли использовать "кортеж"?

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

(Оффтоп)

По указанной ссылке в английской Википедии есть такая фраза:

Цитата:

A prime constellation is sometimes referred to as a prime k-tuplet, but some authors reserve that term for instances that are not part of longer k-tuplets.

Точно перевести не могу из-за незнания английского.
Но вижу, что называют и "prime k-tuplet".
Отсюда, видимо, и калька термина.
Я пишу в своих темах "k-туплеты" с подачи maxal. Он применял именно такой термин в личной переписке. Не думаю, что это неправильное применение.

[Dmitriy40]

Да, спасибо, про k-tuplets я в курсе, оттуда и брал данные, и сразу сказал что это реальная оценка минимума для бесконечного интервала. Но для любого конечного - нет, минимум может быть и значительно больше, особенно если мы не знаем заранее есть ли на этом интервале реальный кортеж или нет.
Но минимум менее интересен.
Вот про "k-antituplets" (антикортеж, не максимально плотный, а наоборот, минимально плотный, с максимальными интервалами между простыми числами) что-нибудь узнать бы, это намного сильнее ограничивает допустимую область.

[grizzly]

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

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

Давайте, чтобы закрыть часть темы с нижней оценкой, я резюмирую свои утверждения:
1) Имеется первая гипотеза Харди-Литлвуда, согласно которой любой допустимый кортеж повторится бесконечное число раз с вычислимой асимптотической плотностью.
2) Можете быть уверены, что на таких маленьких интервалах, которые Вам интересны, эта гипотеза верна. В частности, можете быть почти уверены, что все эти нижние границы будут в Вашем поиске найдены и не один раз.
3) В любом случае, можете быть уверены, что лучших (с точки зрения Вашей задачи) априорных оценок для нижних границ (как-то зависящих от пределов интервала) не существует.
В последнем пункте я уверен ровно настолько, насколько могу быть уверен, что хоть сколько-то правильно понимаю стоящую перед Вами задачу.

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

(Оффтоп)

Если для Вас эта задача не однодневка, предлагаю постепенно развивать её прямо на форуме. Мне эта тема интересна, может и ещё кто подключится. Если Вы не против, тогда попросите, пжл, модераторов перенести задачу в какой-нибудь менее динамичный раздел форума.

[Dmitriy40]

Про минимум. Его желательно бы не уменьшать, а наоборот, увеличивать. Чтобы сужалась разница между минимумом и максимумом - это резко уменьшает число шаблонов. Именно поэтому к-кортежи слишком слабое ограничение, в малых интервалах (длиной до $10^{20}$) реальный минимум будет заметно больше, просто потому что плотность к-кортежей окажется сильно меньше размера интервала и вероятность его нахождения упадёт почти в ноль. Я же проверял прямым счётом, на миллиардных интервалах диаметр длинных кортежей в разы превышает теоретический минимум. Вот пример для диаметров 27-кортежа в интервалах длиной 1млрд начиная с $10^{12}$:
1000e9:264..1494
1001e9:246..1692
1002e9:272..1590
1003e9:260..1634
1004e9:270..1536
1005e9:242..1562
1006e9:266..1610
1007e9:276..1530
1008e9:254..1510
1009e9:262..1494
Как видно минимум вдвое больше минимального теоретического диаметра 27-кортежа (он равен 120), а максимум в девять раз меньше оценки по prime gap ($582(27-1)=15132$ для чисел около триллиона). Длина интервала вдесятеро меньше! И число простых чисел соответственно почти в 10 раз меньше. Представляете как уменьшается число сочетаний по 27 чисел из массивов десятикратно отличающихся длиной? Там же факториал длины.

Собственно задача и состоит именно в сужении интервала [120..15132] до [242..1692] для данного проверяемого интервала 10млрд начиная с 1трлн. И как именно сужать интервал для произвольных параметров (длина кортежа, начало проверяемого интервала чисел, его длина). Особенно максимум.

Про антикортежи и шаблоны. Как уже говорил, сейчас ишутся все простые числа и потом уже из них выбираются кортежи и проверяются на дополнительные условия. Основной тормоз - поиск простых чисел. Хочу попробовать сделать наоборот, для каждого проверяемого интервала (длиной скажем $10^{15}$) ограничить кортежи диапазоном [min..max] реально могущим встретиться в проверяемом интервале, перечислить все возможные комбинации простых чисел в этом диапазоне для кортежей заданной длины, отбросить не удовлетворяющие дополнительным условиям - получится набор шаблонов. После этого основной цикл: выполняем для проверяемого интервала решето Эратосфена на 0.1%, много (но далеко не все) составных чисел выбрасывается, проверить каждый шаблон не вычеркнулось хоть одно число из него, если в результате вычернулись числа из всех шаблонов, то можно не искать в проверяемом интервале все простые числа на 100%, а перейти к следующему интервалу, т.к. уже точно ясно что найденные простые числа не удовлетворят дополнительным условиям. Насколько это будет выгодно зависит от размера интервала и числа шаблонов. Вот только число шаблонов растёт (кажется) по экспоненте от размера max-min, потому и хочется максимально сильно его ограничить, чтобы не получить миллиарды шаблонов. Ограничить именно max-min, как уменьшая max, так и увеличивая min.

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

[grizzly]

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

Про минимум. Его желательно бы не уменьшать, а наоборот, увеличивать.

Ну до такого уровня понимания я уже дорос :)

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

Как видно минимум вдвое больше минимального теоретического диаметра 27-кортежа

Это чистое везение. Потому что на одном миллиарде. На промежутке в $10^{17}$ надеяться совершенно не на что. С этой стороны, как я уже говорил, ничего большего мы не получим -- если нужен поиск наверняка, лучших оценок не существует.

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

а максимум в девять раз меньше оценки

А вот за это стоит побороться.

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

оценки по prime gap ($582(27-1)=15132$

Простите, а где Вы взяли такую оценку максимума? Давайте уясним: всё ещё недоказанная гипотеза Лежандра даёт оценку максимума prime gap между ДВУМЯ соседними простыми при размере чисел порядка 1 трлн. в $2\sqrt{n} \approx 2\cdot 10^6$. А то, что нашли Вы -- это всего навсего (если я правильно интерпретирую) максимум среди 10 минимумов. (UPD: зачёркнуто.)

Если мы и сумеем сузить теоретический максимум для 27-кортежа, то не меньше, чем до $10^7$ -- это я Вам обещаю. А теперь ещё раз вернитесь к оценке трудоёмкости задачи и подумайте. Здесь нужно искать оптимизацию в свойствах магических квадратов, а не в кортежах, я думаю (впрочем, я дилетант в магических квадратах, но некоторые темы на этом форуме просматривал с удовольствием). В идеале -- рассматривать только кортежи уже отобранные со спец. свойствами (как Вы говорили ранее и здесь тоже). Это действительно может сильно упростить.

Я бы пытался идти по другому пути. Просеивать решетом только до примерно $\sqrt{\sqrt{n}}$ (можно уточнить эмпирически) -- останется проверяемый набор шаблонов почти из простых. Потом убрать шаблоны без нужных свойств. Потом проверить с оставшимися квадраты. Потом проверить подошедшие почти простые на простоту.

Остальное мне нужно ещё обдумывать -- это у Вас парадигма к этой задаче уже имеется, а у меня мозги плывут :)

-- 15.01.2015, 15:17 --

С интерпретацией максимумов я погорячился. Но для максимумов на таких интервалах использовать общие теоретические оценки бессмысленно. Нужно искать таблицы фактических данных. А 582 взято как раз из таких таблиц, верно?

[Dmitriy40]

582 взял как точное число, из таблицы интервалов с https://ru.wikipedia.org/wiki/Интервалы_между_простыми_числами, там до числа 1346294310749 все интервалы между простыми числами строго меньше 582. А значит и 26 последовательных интервалов будут меньше чем 582*26. Т.е. это точная верхняя граница (максимум) для чисел меньше 1346294310749.
Конечно как оно поведёт себя дальше не совсем понятно, но до $10^{18}$ есть точные данные, а дальше ну апроксимируем с запасом или поищем хотя бы на указанной вами выше странице.

-- 15.01.2015, 14:35 --

Ой-ой, если теория даёт лишь оценку $2\sqrt{n}$, то это же вообще мрак.