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

[Yury_rsn]

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

можно немного упорядочить "слежку" за большими интервалами вычислительными методами (которыми не владею).
Например максимальный интервал в примориале $7\#$ - это стык примориалов $5\#$ (число $120$). Далее он растиражируется и в примориале $11\#$ таких интервалов будет уже $11$. И т.д.

Может быть ошибаюсь, но, кажется, это наблюдение не всегда задает самые большие вычеркиваемые интервалы.
Условно говоря, выражение $12+2$ может быть меньше, чем $8+7$.
Т.е., большие отрезки на стыках, наследуемые из предыдущих праймориалов, могут соседствовать с короткими отрезками.
И их увеличение за счет соединения будет не таким большим, как соединение двух отрезков средней величины.
По-моему, в 23# возникает первый такой случай.

[Dmitriy40]

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

Меня, собственно, интересует не сама функция $\pi(x)$, но только
её значения при $x=p\#$. т.е. число простых чисел в праймориалах.

Эти значения есть в A000849 вплоть по $67\#$. До $+\infty$ конечно далековато, но прикинуть предел наверное можно ... А дальше уже только теория.
Например берите вместо точного значения $\pi(x)$ значение $\operatorname{li}(x)$, его относительная погрешность падает примерно как $1/\sqrt{x}$, для больших чисел верными будут старшая половина знаков, куда вам больше-то ...

[Батороев]

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

Батороев
Да, похоже я упустил что числа всего лишь взаимно простые и взял обычные простые. Беру свои слова обратно, sorry.

Ничего страшного, ведь тема и о тех, и о других!
Как я понял идею топик-стартера, то рассматривая зону от $n^2$ до $(n+1)^2$, он хочет доказать, что интервалы между взаимнопростыми в примориале $p_r\#$ (где $p_r$ - максимальное простое число, не превосходящее $n$) меньше числа $2n+1$... но в данном интервале указанные взаимнопростые являются простыми числами (т.к. первое взаимнопростое данному примориалу, но не простое число не входит в указанный интервал (${p_{r+1}}^2>(n+1)^2$).

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

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

Единственная ошибка заключается в том, что Вы думаете, что это мое утверждение, а не просто пример... того, как два интервала могут сливаться. ))

Если использовать (как Вы в предпоследнем тосте) линейки, то нам потребутся "резиновые".
Берем большую числовую ось (например, максимальную для Вашего мат.пакета).
Разбиваем ее на примориалы $3\#$. Отмечаем в каждом из них взаимнопростые с этим примориалом ($\varphi_{3\#}=2$ числа: $1$-е и $5$-е).
В сторонке берем первый примориал $3\#$ и расстягиваем его в $5$ раз. Числа, бывшие в примориале $3\#$ взаимнопростыми, также расстягиваются и "элегантно превращаются" в числа, кратные $5$ ($2$ числа: $5$ и $25$).
Оставшиеся числа являются взаимнопростыми примориалу $5\#$. Таких чисел $\varphi_{5\#}=8$.
Покрываем числовую ось такими линеками с обозначенными кратными.
И т.д.

p.s. Как мне видится, такой алгоритм вполне программируем.

[Dmitriy40]

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

т.к. первое взаимнопростое данному примориалу, но не простое число не входит в указанный интервал (${p_{r+1}}^2>(n+1)^2$)

Это не совсем верно, $p_{r+1}^2$ может быть и равно $(n+1)^2$, это будет для простых $(n+1)=p\#+1$. И немало праймориалов (см. A005234) дают раз простые $p\#+1$. Кстати там же сказано что для них следующее простое будет меньше $p\#+p^2$.

[Yury_rsn]

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

Как я понял идею топик-стартера, то рассматривая зону от $n^2$ до $(n+1)^2$, он хочет доказать, что интервалы между взаимнопростыми в примориале $p_r\#$ (где $p_r$ - максимальное простое число, не превосходящее $n$) меньше числа $2n+1$...
...
p.s. Как мне видится, такой алгоритм вполне программируем.

Да, хотелось бы понять, как ведет себя функция расстояний между взаимно простыми внутри праймориала (примориала).
Как показывают расчеты (по материалам Дмитрия), максимумы расстояний появляются где-то в середине праймориала.
Длина праймориала очень быстро возрастает, поэтому можно ожидать, что в начале ряда, в том числе и на отрезке от $n^2$ до $(n+1)^2$ наибольшие расстояния между соседними взаимно простыми гораздо меньше максимума - значения функции Якобсталя.
Похоже, что на отрезке от $n^2$ до $(n+1)^2$ почему-то "два интервала из предыдущего праймориала еще не могут слиться" в один большой, $> 2n+1$

Вот это и интересует - почему?
Что этому мешает?
Ведь вроде бы взаимно простые располагаются на всей длине праймориала абсолютно хаотично, не считая центральной симметрии.

[Батороев]

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

Это не совсем верно, $p_{r+1}^2$ может быть и равно $(n+1)^2$, это будет для простых $(n+1)=p\#+1$.

Во-первых, я рассматривал общий случай... без частностей. А во-вторых, я писал о другом интервале (между двумя соседними квадратами, а не на границе примориалов).

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

И немало праймориалов (см. A005234
) дают раз простые $p\#+1$.

Т.к. я продолжаю рассматривать взаимнопростые, то число $p\#+1$ однозначно является взаимнопростым.

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

Кстати там же сказано что для них следующее простое будет меньше $p\#+p^2$.

Рассматриваемый в теме интервал значительно меньше. Например, от $p\#+(p-1)^2$ до $p\#+p^2$.

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

Вот это и интересует - почему?
Что этому мешает?

Не исключено, что этот вопрос и сможет стать одним из ключевых в Вашей теме.

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

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

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

[Yury_rsn]

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

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

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

Это, как минимум, вытекает из той модели решета Эратосфена, которую я привел несколько комментов назад. Там, где в несколько строк.

[Батороев]

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

Простые подчиняются той же самой системе, что и взаимно простые.

Не согласен. Система взаимнопростых намного проще.

[Dmitriy40]

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

Я хочу найти предел отношения

$$\lim\frac{\pi(M)}{\varphi(M)}\;\;\;M=p\#\rightarrow \infty$$

Если в знаменателе функция Эйлера, то предел равен нулю. Точно доказать конечно не могу, прибегну к эмпирике. Для праймориалов функция Эйлера равна $\varphi(M=p\#)=\prod\limits_{t \le p} (t-1)$ (произведение всех уменьшенных на 1 простых до заданного), а $\pi(M)<1.1 M/\ln(M)$ (взял гарантированно верхний предел). Итого под пределом остаётся в числителе $1.1 p\#$, в знаменателе логарифм праймориала на произведение уменьшенных на 1 простых. А это можно представить как $\frac{1.1}{\ln(p\#)}\prod\limits_{t \le p} \frac{t}{t-1}$ ($t$ простое). Или итерационно $a_{n+1}=a_n\frac{\ln(t_n\#)}{\ln(t_n\#)+\ln(t_{n+1})}\frac{t_{n+1}}{t_{n+1}-1}, \; t_n \in prime, a_1=2.2/\ln(2),n>1$. Вычисление показывает что для простых до 100 млн (а это для праймориалов до $10^8\#\approx 2.5\cdot10^{43424119}$) дробь в итерационной формуле меньше $1$, хотя и приближается к ней. Само отношение для этого праймориала равно $0.00000036094$. Для праймориала $x\#=10^8\#$ дробь выглядит почти как $\frac{x^2}{(x+\ln(x))(x-1)}$ (после 6-ти девяток ещё 4 верных знака, точность порядка $2\cdot10^{-11}$, с погрешностью вверх). Проверка этой формулы до праймориала $10^{100}\#$ показало что $1$ она не превышает (даже учитывая что она больше реальной дроби). Т.е. последовательность $a_n$ монотонно убывающая.
Думаю этого достаточно для оценки предела.

[vorvalm]

Dmitriy40
В знаменателе именно функция Эйлера. Я вычислил это отношение до $p\#=67$.
Получил следующие данные.
13\# - 0,56
17\# - 0,46
19\# - o 40
....................
59\# - 0,16
61\# - 0,15
67\# - 0,14
Я полностью согласен с вашим выводом, однако
хотелось бы математически точного доказательства. Меня смущает следующее обстоятельство.
Согласно формуле Мертенса при p < x

$$\prod(1-\frac 1 p)\sim\frac C {\ln x}$$

но при $p/m $

$$ \prod(1-\frac 1 p)=\frac {\varphi(m)}{m} $$

и

$$ \pi(x)\sim \frac x{\ln x} $$

Совмещая эти формулы , получается, что

$$\lim \frac {\pi(M)}{\varphi(M)}\rightarrow \frac 1 {C'}$$

[Dmitriy40]

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

Я вычислил это отношение до $p\#=67$.

Тут видимо подразумевалось $p=67$ или $p\#=67\#$.
Но я то вычислил до $p\approx 10^{10}$ или $p\#=10^{10}\#$, причём даже с гарантированно завышенным значением $\pi(x)$ (разумеется считается до ближайшего меньшего простого, округлил до 5 значащих цифр сам):
$10^2\#=0.10919$
$10^3\#=0.014208$
$10^4\#=0.0018257$
$10^5\#=0.00022634$
$10^6\#=0.000027109$
$10^7\#=0.0000031594$
$10^8\#=0.00000036094$
$10^9\#=0.000000040602$
$10^{10}\#=0.0000000045112$
По моему поведение достаточно очевидно.

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

Согласно формуле Мертенса при p < x

$$\prod(1-\frac 1 p)\sim\frac C {\ln x}$$

Простите, но в вики я такой формулы не нашёл и потому Ваш вывод никак прокомментировать не могу.

[vorvalm]

https://ru.wikipedia.org/wiki/Теоремы_Мертенса
Посмотрите здесь.Скопируйте в Яндекс

[Dmitriy40]

Простите, а так точно можно?

$$\lim\limits_{n\to\infty} \ln(n) f(n) = C \to \ln(n) f(n) \sim C$$

Разве к произведению не может добавляться произвольный (уменьшающийся с ростом $n$) шум? А с шумом пропорциональность нарушается, с пределом равенство выполняется, без него уже нет.

[Dmitriy40]

Впрочем Ваш вывод можно повторить и без этого перехода.
Из доказанного

$$\prod\limits_{p\le k} \left (1-\frac{1}{p}\right ) = \frac{\varphi(m)}{m},\;k\#=m$$

домножив на $\ln(m)$ и заменяя справа $\ln(m)/m$ на $C/\pi(m)$ получим

$$\ln(m)\prod\limits_{p\le k} \left (1-\frac{1}{p}\right ) = \frac{\varphi(m)}{\pi(m)}C,\;k\#=m,\;0.9<C<1.1$$

Беря предел слева и справа по $m\to\infty$ получаем Вашу формулу с ненулевой и малой константой слева.

Что делать с этим противоречием я не знаю.

[vicvolf]

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

Вопрос - как найти значение величины максимального интервала между соседними членами этих последовательностей - в зависимости от конкретного праймориала?
Например, чему равно максимальное расстояние между соседними числами при $23 \#$ ?

Обозначим праймориал $p_r \#=2 \cdot...\cdot p_r$, где $r$ - порядковый номер простого числа. Тогда максимальный интервал между членами ПСВ равен $p_{r+1}-1$.