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

[Yury_rsn]

StaticZero в сообщении #1472732 писал(а):

Yury_rsn, это наименьшая длина последовательностей натуральных чисел, при которой каждая из них содержит взаимно простые с произведением $n$ первых простых чисел.

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

[StaticZero]

Yury_rsn, да, окошко длины $j(n)$ ездит по числовой прямой, а в него видно всех, кого нужно.

[vorvalm]

Последовательность А048670 OEIS

Эта последовательность дает максимальные разности между последовательными
простыми числами в праймориале $p_r\#.$
В каком месте праймориала находятся эти разности не указывается.
Единственной оценкой этого места может служить праймориал $p_{r-1}\#$,
т.е. праймориал рангом ниже, который входит в состав праймориала $p_r\#$
и составляет его начальную часть, в которой не может быть этих разностей.
Это довольно грубая оценка. Более точную оценку максимальной разности
между последовательными простыми числами можно получить исходя
из максимальной разности между вычетами ПСВ (приведенная система вычетов)
по модулю $M(p_r)=p_r\#$. Действительно, если в ПСВ нет какой-то
разности между вычетами, то ее не может быть и в интервале простых чисел ПСВ
$(1<p<p_{r+1}^2).$
Интересно сравнить данные последовательности А048670 и
последовательности максимальных разностей между вычетами ПСВ
по модулю $p_r\#$. До $p_r=31$ эти данные полностью совпадают. Это означает,
что вычеты ПСВ, образующие эти разности, являются простыми числами.
Но при дальнейшем увеличении модуля $M(p_r)=p_r\#$ эти данные начинают
расходиться. Привожу сравнительные данные этих последовательностей,
начиная с модуля $M(23)=23\#$ до модуля $M(97)=97\#$.

$p_r\;\;\;\;\;\;\;\;23,\;29,\;31,\;37,\;41,\;43,\;\;47,\;53,\;\;59,\;\;61,\;\;67,\;\;71,\;\;73,\;\;\;79,\;\;83,\;\;89,\;\;97...$
ПСВ$,\;\;\;\;\;40,\;46,\;58,\;64,\;74,\;90,\;\;92,\;98,\;106,118,126,140,\;144,148,166,\;172,178...$
AO48670 $\;\;\;40,\;46,\;58,\;66,\;74,\;90,100,106,118,132,152,\;174,190,200,\;216,\;234,258...$

По характеру распределения вычетов ПСВ по модулю $M(p_r)$ максимальную
разность между вычетами надо искать в виде $2p.$
Например, совершенно точно установлено, что в любой ПСВ по модулю $M(p_r)$
есть разности между последовательными вычетами, равными $2p_{r-1}$.
Знаменитая разность $127-113=14$ находится в ПСВ по модулю $11\#$.
Поэтому, нижней границей максимальной разности между вычетами ПСВ
по модулю $p_r\#$ можно считать именно $d=2p_{r-1}$, т.е.

$2p_{r-1}\leqslant d_{\max}$

А вот с верхней границей $d_{\max}$ большие проблемы.
Экспериментальные данные для достаточно больших ПСВ показывают,
что максимальная разность в них может превосходить $2p_r.$
Например, в ПСВ по модулю $43\#$ есть разность $90$, в ПСВ по модулю $83\#$
есть разность $166$, но разности $2p_{r+1}$ в ПСВ по модулю $p_r\#$ пока не найдено
и в качестве гипотезы можно считать, что

$2p_{r-1}\leqslant d_{\max}<2p_{r+1}$

[Yury_rsn]

vorvalm в сообщении #1472754 писал(а):

Последовательность А048670 OEIS

Эта последовательность дает максимальные разности между последовательными
простыми числами в праймориале $p_r\#.$

Именно простыми, а не взаимно простыми с праймориалом?

Цитата:

..Более точную оценку максимальной разности
между последовательными простыми числами можно получить исходя
из максимальной разности между вычетами ПСВ (приведенная система вычетов)
по модулю $M(p_r)=p_r\#$. Действительно, если в ПСВ нет какой-то
разности между вычетами, то ее не может быть и в интервале простых чисел ПСВ
$(1<p<p_{r+1}^2).$
Интересно сравнить данные последовательности А048670 и
последовательности максимальных разностей между вычетами ПСВ
по модулю $p_r\#$. До $p_r=31$ эти данные полностью совпадают. Это означает,
что вычеты ПСВ, образующие эти разности, являются простыми числами.
Но при дальнейшем увеличении модуля $M(p_r)=p_r\#$ эти данные начинают
расходиться.

Подождите, но ведь из определения функции Якобсталя, которое мы сегодня как раз уточнили, следует, что она и есть интервалы между членами ПСВ?
Или я неправильно понял перевод?

Чем всё-таки отличается ПСВ и А048670 OEIS ?

-- 07.07.2020, 17:32 --

StaticZero в сообщении #1472752 писал(а):

Yury_rsn, да, окошко длины $j(n)$ ездит по числовой прямой, а в него видно всех, кого нужно.

красивая визуализация!

Если можно, подскажите, чем функция Якобсталя отличается от интервалов в ПСВ ?
(см.предыдущие комменты)

-- 07.07.2020, 18:08 --

vorvalm в сообщении #1472754 писал(а):

В каком месте праймориала находятся эти разности не указывается.
Единственной оценкой этого места может служить праймориал $p_{r-1}\#$,
т.е. праймориал рангом ниже, который входит в состав праймориала $p_r\#$
и составляет его начальную часть, в которой не может быть этих разностей.

Хорошая мысль!

[vorvalm]

Yury_rsn в сообщении #1472759 писал(а):

Чем всё-таки отличается ПСВ и А048670 OEIS ?

Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.
ПСВ - приведенная система вычетов по модулю М. Если модуль ПСВ равен
праймориалу. то это означает, что вычеты ПСВ взаимно просты и не сравнимы
по модулю.
Чувствуете разницу?
Кстати, максимальные разности между последовательными простыми числами в
праймориале те же, что и в ПСВ по модулю, равному этому праймориалу. а вот
разности между последовательными вычетами ПСВ другие.

[Dmitriy40]

vorvalm в сообщении #1472770 писал(а):

Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.

Это не так:

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

Yury_rsn в сообщении #1472687 писал(а):

И по их краям образуются простые числа.

Не везде, $2183$ и $2183+18$ оба не простые. Как и $39469$ с $39469+24$, и $217127$ с $217127+26$, и т.д.

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

[Yury_rsn]

vorvalm в сообщении #1472770 писал(а):

Yury_rsn в сообщении #1472759 писал(а):

Чем всё-таки отличается ПСВ и А048670 OEIS ?

Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.
ПСВ - приведенная система вычетов по модулю М. Если модуль ПСВ равен
праймориалу. то это означает, что вычеты ПСВ взаимно просты и не сравнимы
по модулю.
Чувствуете разницу?

Если можно, на примере.
Вот фрагмент последовательности из середины ПСВ по праймориалу 7.
... 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
121, 127, 131, 137, 139, 143, 149 ...
Если я правильно понимаю, то разности 121-113 и 127-121, например, относятся к ПСВ по праймориалу 7.
А разность 127-113 - это разность между последовательными простыми в данном праймориале?
Так?

Если так, то вполне понятна фраза:

Цитата:

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

Но, мне кажется, что определение функции Якобсталя говорит о том, что берутся во внимание только разности между вычетами, даже если они и не простые.
Т.е., именно 121-113 и 127-121

-- 07.07.2020, 23:11 --

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

[Не везде, $2183$ и $2183+18$ оба не простые. Как и $39469$ с $39469+24$, и $217127$ с $217127+26$, и т.д.
Остальные мне просто лень проверять, допускаю что и там полно не простых границ.

Я, наверное, не совсем четко выразился.

Цитата:

А на диапазоне от 169 до 196 (длина 27) - максимум не превышает 22, да и то, этот максимум улетел за девять тысяч (13#: 16/1, 18/2183, 22/9439). А именно в этом месте реальные интервалы гораздо меньше. И по их краям образуются простые числа.

Имел в виду, что если максимальный отрезок, длиной 22 (функция Якобсталя для данного праймориала),
был бы расположен в пределах диапазона от 169 до 196, то на его краях обязательно были бы простые числа.

Ведь это же максимальное количество идущих подряд чисел, каждое из которых не взаимно просто с 13#
Но на отрезке вокруг квадрата 13 не может быть составных чисел, которые не делятся на 2,3,5,...11,13, но делятся на какие-то другие небольшие простые числа.

[Yury_rsn]

да.
правильнее было бы взять интервал 144-169, а не 169-196.

[Yury_rsn]

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

И первый интервал равен следующему простому минус 1 (это кстати легко доказать), а не удвоенному предыдущему.

Прозевал раньше это замечание.
Вы правы, спасибо.
---
Я к вопросу гипотезы Лежандра пришел совсем из другой задачи, но потом увидел, что эту идею уже раньше описал Евгений Колесников.
http://blogs.it-claim.ru/ekolesnikov/fi ... doklad.pdf

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

[Dmitriy40]

Yury_rsn в сообщении #1472858 писал(а):

- дают надежду доказать, что для отрезков, не превышающих квадрата праймориала, максимальная длина меньше, чем даже "..первый интервал, равный следующему простому минус 1"

Что Вы подразумеваете под "квадратом праймориала"? Например для $23\#$ это будет $23^2$ или $(23\#)^2$? Если второе, то это очевидно и легко доказывается (потому что все возможные длины встретятся не далее $23\#+23$ для $23\#$ и потом будут лишь повторяться), если первое то это легко проверить хоть до миллионных праймориалов (которые, праймориалы, тогда вообще ни при чём).

[Yury_rsn]

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

Yury_rsn в сообщении #1472858 писал(а):

- дают надежду доказать, что для отрезков, не превышающих квадрата праймориала, максимальная длина меньше, чем даже "..первый интервал, равный следующему простому минус 1"

Что Вы подразумеваете под "квадратом праймориала"? Например для $23\#$ это будет $23^2$ или $(23\#)^2$? Если второе, то это очевидно и легко доказывается (потому что все возможные длины встретятся не далее $23\#+23$ для $23\#$ и потом будут лишь повторяться), если первое то это легко проверить хоть до миллионных праймориалов (которые, праймориалы, тогда вообще ни при чём).

Спасибо за уточнение. Тяжело постоянно следить за сокращенными фразами. И они постоянно норовят оказаться двусмысленными

Я имел в виду первый случай - $23^2$.
Функция Якобсталя - это длина самого большого интервала между соседними взаимно простыми числами (т.е., между соседними вычетами по ПСВ данного праймориала).
Например, для 23# самый большой интервал возникает только после числа 20332471 (функция Якобсталя равна 40).

И это означает, что больше нигде, на всем протяжении ряда от 1 и до 23#, разность между соседними вычетами не превышает 40.
Хоть между 20332471 и 20332511, хоть между $22^2$ и $23^2$.
---
Но нас, в конце концов, интересует - какие максимальные интервалы между взаимно простыми с p# возможны именно на интервалах от $(p-1)^2$ до $p^2$

[Yury_rsn]

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

11#: 12/1, 14/113
13#: 16/1, 18/2183, 22/9439
17#: 18/1, 22/9439, 24/39469, 26/217127
19#: 22/1, 24/1333, 34/60043 — заметьте какое интересное исключение здесь: и короче, и нет интервала 26, и интервал 24 обнаружен сильно раньше
23#: 28/1, 34/60043, 36/8302457, 40/20332471
29#: 30/1, 34/60043, 36/3543523, 40/9740461, 42/36806389, 46/417086647 — а здесь интервалы 36,40 обнаружены сильно раньше предыдущего случая
31#: 36/1, 40/2734891, 42/6077119, 48/7006073, 50/689448377, 54/3734704159, 56/26886024107, 58/125601285782 — и опять интервалы на других числах
37#: 40/1, 46/933091, 48/7006073, 50/48595307, 54/132966023, 56/2782823513, 64/4683065593, 66/8720486098464

Смотрите:
11#: 12/1, 14/113 - в районе интервала 100-121 самый большой отрезок НЕвзаимнопростых с 11# - длиной 14, а внутри самого интервала только часть, длиной 8.
Т.е., внутри интервала 100-121, как минимум, $21/8$ $\sim$ 2 простых числа.

13#: 16/1, 18/2183, 22/9439 - внутри интервала 144-169 несколько отрезков НЕвзаимнопростых с 13# - длиной по 5.
Т.е., внутри интервала 144-169, как минимум, $25/5$ $\sim$ 5 простых чисел.

И т.д.

-- 08.07.2020, 22:54 --

17#: 18/1, 22/9439, 24/39469, 26/217127 - а в реальности в районе интервала 256-289 самый большой отрезок НЕвзаимнопростых с 17# - отрезок длиной 9, а внутри самого интервала только часть, длиной 6.
Т.е., внутри интервала 256-289, как минимум, $33/6$ $\sim$ 5 простых чисел.

19#: 22/1, 24/1333, 34/60043 - а в реальности внутри интервала 324-361 самый большой отрезок НЕвзаимнопростых с 19# - отрезок длиной 9 (338 339 340 341 342 343 344 345 346).
Т.е., внутри интервала 324-361, как минимум, $37/9$ $\sim$ 4 простых чисел.
Хотя на самом деле их, конечно, больше.

...

[Yury_rsn]

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

Возникла идея, не знаю, приветствуется ли это на форуме, - попытаться сообща разобраться в одной из статей.
"An upper bound on Jacobsthal’s function" https://www.researchgate.net/publicatio ... s_function

Я с помощью гугл-переводчика понял суть первой теоремы, но дальше слегка застрял. Наверное, трудно вникнуть в "непереводимую игру слов".
Было бы здорово, если бы кто-то помог "решить / разобраться"

В начале статьи есть одно неясное место.
Авторы пишут "оценки (других авторов) довольно слабые: в то время как из расчета Хагедорна имеем $h (49) = 742$, эти оценки дают $h (49) <1015$ и $h (49) <1040$ соответственно. Таким образом, мы относительно мало знаем о явном поведении $h (k)$ для k больше 49."

Но дальше они пишут свою формулу, и к ней такой комментарий:
"В этой статье мы устраняем этот пробел, используя новый вычислительный метод для вычисления явных верхних оценок $h (k)$.
Этот метод дает гораздо более строгие оценки, чем те, которые были даны Канольдом и Стивенсом; например, этот метод дает оценку $h (49)$, которая менее чем в 3 раза превышает истинное значение $h (49)$.
...
Мы использовали этот метод для вычисления верхних границ $h (k)$ для k от 50 до 10 000: для всех k в этом диапазоне мы находим $ h(k)< 0,27749612254\cdot k^2 \cdot \log(k) $
граница на сотни порядков сильнее, чем у Канольда и Стивенса в этом диапазоне."

Что это значит - "менее чем в 3 раза превышает истинное значение"?
И, действительно, при подставлении 49 в последнюю формулу получаем число, намного бОльшее, чем 742. Т.е., - 2592,996.

Да, а теорема красивая
"Theorem 2.1. Let d and n be two coprime squarefree integers. Then for any
arithmetic sequence
$b + d, b + 2d, . . .$
there necessarily exists a corresponding sequence of consecutive integers
$cb + 1, cb + 2, . . .$
such that
$GCD(cb + x,n) = GCD(b + xd,n)$ for all x "

[Батороев]

Yury_rsn
Рассматривая интересующие Вас интервалы, надо иметь в виду то, что при переходе с одного примориала на следующий ($p_r\#$), Вы "тиражируете" эти интервалы $p_r$ раз.

[Yury_rsn]

Батороев в сообщении #1505795 писал(а):

Yury_rsn
Рассматривая интересующие Вас интервалы, надо иметь в виду то, что при переходе с одного примориала на следующий ($p_r\#$), Вы "тиражируете" эти интервалы $p_r$ раз.

Тиражирование происходит, да.
Но интервалы при каждом переходе удлиняются за счет того, что новое число $p_r$ попадает в "пустую" ячейку между соседними интервалами.

Какие соседние интервалы удлиняются за счет новых вычеркивающих чисел?
Самые длинные новые интервалы - они где-то в середине праймориала возникают, или и по краям тоже?