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

[vicvolf]

Выполню просьбу:

Гипотеза

$d(p^2_{R+1}) \leq 2p_{R-1}$, где $d(p^2_{R+1})$ - максимальное расстояние между простыми числами на интервале $(1,p^2_{R+1})$, а $p_{R+1}$ - $R+1$ - простое число.

Доказательство

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

Поэтому ПСВ$p_r\#$ можно представить в виде: $1,p_r,...,p_{r-1}\#-p_r,p_{r-1}\#-1,p_{r-1}\#+1,p_{r-1}\#+p_r,...$.

Если одно из граничных значений ПСВ$p_{r-1}\#$, например, $p_{r-1}\#-1$ будет кратно $p_r$, а на $r+1$ шаге решета Эратосфена окажется кратным $p_{r+1}$ другой граничный вычет $p_{r-1}\#+1$, то между вычетами образуется максимальное расстояние для первого ПСВ$p_{r-1}\#$ с учетом границы (вложенного в ПСВ$p_r\#$), равное $p_{r-1}\#+p_r-(p_{r-1}\#-p_r)=2p_r$.

На $r+1$ шаге решета Эратосфена получается ПСВ$p_{r+1}\#$, поэтому если обозначить $R=r+1$, то максимальное расстояние между вычетами ПСВ$p_{R-1}\#$ равно $2p_{R-1}$.

Теперь рассмотрим интервал $(1,p^2_{R+1})$, на которых в ПСВ$p_{r}\#$ находятся только простые числа.

Если в качестве простого числа взять $p_R=11$, то получим интервал $(1,169)$, который полностью попадает в первый ПСВ$7\#$, вложенный в ПСВ$11\#$. Поэтому на основании сказанного выше для расстояния между простыми числами на интервале $(1,169)$ выполняется: $d(p^2_R=169) \leq 2p_{R-1}=2 \cdot 7=14$.

Аналогичная ситуация выполняется для $p_R>11$: $d(p^2_R) \leq 2p_{R-1}$.

Можно проверить, что это условие выполняется и для $p_R<11$. Например, для $p_R=3$ выполняется $d(9) \leq 4$.

[Yury_rsn]

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

Yury_rsn
Вы пропустили (или не заметили) ...

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

Вычисляя разности по найденным формулам я заметил, что
максимальные разности вплоть до ПСВ ($19\#$) равны $2p_{r-1}$
и при $M=19\# \;\;d_{\max}=34$.
Я определил место этих разностей в ПСВ. Оказалось, что они
образуются на стыках $p_{r-1}\#$, когда числа $n\cdot p_{r-1}\#\pm 1$ кратны
одно $p_{r}$, другое $p_{r-1}$. Эти стыки легко можно вычислить.

Я их начал вычислять, и, кажется, формулы не совсем такие.
Давайте уточним.

$4\cdot5\#$
119 _ 121
7 _ 11
образуется максимальная разность 14 - для 11#

$45\cdot7\#$
9449 _ 9451
11 _ 13
разность 22 - для 13#

$127\cdot11\#$
293369 _ 293371
17 _ _ _ _ 13
разность 26 - для 17#

Т.е., разности в ПСВ $p_{r}\#$ образуются на стыках $p_{r-2}\#$, когда числа $n\cdot p_{r-2}\#\pm 1$ кратны
одно $p_{r}$, другое $p_{r-1}$

---
Ок.
А начиная с ПСВ 23# закономерности меняются?
Или пока не понятно?

[vorvalm]

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

А начиная с ПСВ 23# закономерности меняются?

Нет. Эти разности $2p_{r-1}$ существуют в любой ПСВ, но не являются максимальными, кроме
ПСВ$(29\#)$ , $(31\#)$ , $(41\#)$.

[vicvolf]

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

Т.е., разности в ПСВ $p_{r}\#$ образуются на стыках $p_{r-2}\#$, когда числа $n\cdot p_{r-2}\#\pm 1$ кратны одно $p_{r}$, другое $p_{r-1}$

Именно так, но расстояние $p_{r-2}\#+p_{r-1}- (p_{r-2}\#-p_{r-1})=2p_{r-1}$

Dmitriy40
Большая просьба подсчитать максимальное расстояние между взаимно простыми числами на интервале от 1 до $p_{r-2}\#+p_{r-1}$ при различных $r$ за приемлемое время и выдать значение максимального расстояния и его расположение.

[Dmitriy40]

vicvolf
Надеюсь под взаимно простыми подразумевались взаимно простые с $p_r\#$. Тогда вот ($p_r\#$, интервал, максимальное расстояние, список где встретилось в интервале):

? prr=6; forprime(pr=5,35, prr*=pr; pr1=precprime(pr-1); ps=prr/pr/pr1+pr1; a=[];d=0;ii=1; forstep(i=3,ps,2, if(gcd(i,prr)==1, if(i-ii==d, a=concat(a,[ii])); if(i-ii>d, d=i-ii;a=[ii]); ii=i); ); printf("%d#=%d, 1..%d:%d=%d\n", pr,prr,ps,d,a); );
5#=30, 1..5:0=[]
7#=210, 1..11:10=[1]
11#=2310, 1..37:12=[1]
13#=30030, 1..221:16=[1]
17#=510510, 1..2323:18=[1,1129,2183]
19#=9699690, 1..30047:24=[1333,4759,14593,24257]
23#=223092870, 1..510529:34=[60043,134293]
29#=6469693230, 1..9699713:36=[3543523,3897083,3911293,4585201,6283513,7340191,8302457,8537611,9018091,9127133,9207511]
31#=200560490130, 1..223092899:48=[7006073]
37#=7420738134810, 1..6469693261:64=[4683065593]
41#=304250263527210, 1..200560490167:66=[43673042131,145019268533,187219155593]

Видно что по крайней мере на этих праймориалах добавка $p_{r-1}$ никакого эффекта не даёт.
Также видно что начиная с $19\#$ максимальное расстояние уже не с $1$.
Тоже видно что поначалу максимальное расстояние равно $p_{r+1}-1$, как и должно быть для интервала $[1\ldots p_{r+1}]$, но с увеличением расстояния формула нарушается, но и $2p_{r-1}$ никогда не равно.

[vicvolf]

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

vicvolf
Надеюсь под взаимно простыми подразумевались взаимно простые с $p_r\#$. Тогда вот ($p_r\#$, интервал, максимальное расстояние, список где встретилось в интервале):

? prr=6; forprime(pr=5,35, prr*=pr; pr1=precprime(pr-1); ps=prr/pr/pr1+pr1; a=[];d=0;ii=1; forstep(i=3,ps,2, if(gcd(i,prr)==1, if(i-ii==d, a=concat(a,[ii])); if(i-ii>d, d=i-ii;a=[ii]); ii=i); ); printf("%d#=%d, 1..%d:%d=%d\n", pr,prr,ps,d,a); );
5#=30, 1..5:0=[]
7#=210, 1..11:10=[1]
11#=2310, 1..37:12=[1]
13#=30030, 1..221:16=[1]
17#=510510, 1..2323:18=[1,1129,2183]
19#=9699690, 1..30047:24=[1333,4759,14593,24257]
23#=223092870, 1..510529:34=[60043,134293]
29#=6469693230, 1..9699713:36=[3543523,3897083,3911293,4585201,6283513,7340191,8302457,8537611,9018091,9127133,9207511]
31#=200560490130, 1..223092899:48=[7006073]
37#=7420738134810, 1..6469693261:64=[4683065593]

Видно что по крайней мере на этих праймориалах добавка $p_{r-1}$ никакого эффекта не даёт.
Также видно что начиная с $19\#$ максимальное расстояние уже не с $1$.
Тоже видно что поначалу максимальное расстояние равно $p_{r+1}-1$, как и должно быть для интервала $[1\ldots p_{r+1}]$, но с увеличением расстояния формула нарушается, но и $2p_{r-1}$ никогда не равно.

Все правильно. Большое спасибо! Мне нужно было убедиться, что на первом ПСВ$p_{r-2}\#$ расстояние меньше $2p_{r-1}$. Вы это подтвердили. Оно могло быть равно $2p_{r-1}$ только на границе между ПСВ$p_{r-2}\#$, поэтому я включил границу.
Например, такая ситуация произошла на границе между вторым и третьим ПСВ$p_{r-2}\#$ в этом случае:
$19\#:60043+34$ _ _ _ _ _ _ _ _$60043=13\#\cdot2 -17$ и получилось максимальное расстояние $d=2p_{r-1}=2 \cdot 17=34$, а внутри первого ПСВ$13\#$ максимальное расстояние $d=24<34$, как Вы подсчитали.

[Yury_rsn]

vicvolf в сообщении #1512849 писал(а):

Выполню просьбу:

Гипотеза

$d(p^2_{R+1}) \leq 2p_{R-1}$, где $d(p^2_{R+1})$ - максимальное расстояние между простыми числами на интервале $(1,p^2_{R+1})$, а $p_{R+1}$ - $R+1$ - простое число.

Доказательство

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

Поэтому ПСВ$p_r\#$ можно представить в виде: $1,p_r,...,p_{r-1}\#-p_r,p_{r-1}\#-1,p_{r-1}\#+1,p_{r-1}\#+p_r,...$.

Если одно из граничных значений ПСВ$p_{r-1}\#$, например, $p_{r-1}\#-1$ будет кратно $p_r$, а на $r+1$ шаге решета Эратосфена окажется кратным $p_{r+1}$ другой граничный вычет $p_{r-1}\#+1$, то между вычетами образуется максимальное расстояние для первого ПСВ$p_{r-1}\#$ с учетом границы (вложенного в ПСВ$p_r\#$), равное $p_{r-1}\#+p_r-(p_{r-1}\#-p_r)=2p_r$.

На $r+1$ шаге решета Эратосфена получается ПСВ$p_{r+1}\#$, поэтому если обозначить $R=r+1$, то максимальное расстояние между вычетами ПСВ$p_{R-1}\#$ равно $2p_{R-1}$.

Теперь рассмотрим интервал $(1,p^2_{R+1})$, на которых в ПСВ$p_{r}\#$ находятся только простые числа.

Если в качестве простого числа взять $p_R=11$, то получим интервал $(1,169)$, который полностью попадает в первый ПСВ$7\#$, вложенный в ПСВ$11\#$. Поэтому на основании сказанного выше для расстояния между простыми числами на интервале $(1,169)$ выполняется: $d(p^2_R=169) \leq 2p_{R-1}=2 \cdot 7=14$.

Аналогичная ситуация выполняется для $p_R>11$: $d(p^2_R) \leq 2p_{R-1}$.

Можно проверить, что это условие выполняется и для $p_R<11$. Например, для $p_R=3$ выполняется $d(9) \leq 4$.

Хм..
Кажется, всё доказательство основано на идее, что максимальные расстояния могут возникнуть только на стыках предыдущих праймориалов.
Но ведь максимумы функции Якобсталя как раз демонстрируют, что они умеют появляться и мимо стыков праймориалов.

-- 05.04.2021, 23:37 --

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

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

Как вам эти соотношения?
$11\#:113+14$ _ _ _ _ _ _ _ _ _$113=5\#\cdot4 - 7$
$13\#:9439+22$ _ _ _ _ _ _ _ _ $9439= 11\#\cdot4 + 7\# - 11$
$17\#:217127+26$ _ _ _ _ _ _ _ $217127=13\#\cdot7 + 11\#\cdot3 - 13$
$19\#:60043+34$ _ _ _ _ _ _ _ _$60043=13\#\cdot2 -17$
$23\#:20332471+40$ _ _ _ _ _ _$20332471=19\#\cdot2 + 17\#\cdot2 - 13\#\cdot3 + 11\# - 5\#+1$
$29\#:417086647+46$ _ _ _ _ _ $417086647=23\#\cdot2 - 19\#\cdot3 + 23$

Плохо.
Если для первых ещё можно допустить что они вида $x-d/2$, то $23\#$ и $29\#$ к такому виду уже не приведёшь.
Для $11\#$ и $19\#$ можно допустить что они на стыке каких-то праймориалов, то про остальные этого уже не скажешь.
Т.е. никакой особой регулярности не видно.

Так я именно это и имел в виду - там, где проявляется "эффект функции Якобсталя" (например - 23#), - там сбивается вся красота простых формул.
Максимум у Якобсталя появляется НЕ на стыке предыдущих праймориалов.

upd
Кстати, для 29 я просто неправильно посчитал
$417086647=19\#\cdot43 - 23$

[Dmitriy40]

Yury_rsn
Насчёт правее или левее, вот вам данные по стыкам праймориалов $p_{r-2}\#$ и расстояниях на них (праймориал, максимальное расстояние, где встречается):

5#=30: d=6:[1,23]
7#=210: d=10:[1,199]
11#=2310: d=14:[113,2183]
13#=30030: d=22:[9439,20569]
17#=510510: d=26:[217127,293357]
19#=9699690: d=34:[60043,9639613]
23#=223092870: d=38:[29609561,193483271]
29#=6469693230: d=46:[417086647,6052606537]
31#=200560490130: d=58:[74959204291,125601285781]
37#=7420738134810: d=62:[2723740849799,4696997284949]
41#=304250263527210: d=74:[79622514581573,224627748945563]
43#=13082761331670030: d=82:[6136950437487829,6945810894182119]
47#=614889782588491410: d=86:[223928193956026517,390961588632464807]
53#=32589158477190044730: d=94:[9171015693500690983,23418142783689353653]
59#=1922760350154212639070: d=106:[522656315200217698447,1400104034953994940517]
61#=117288381359406970983270: d=118:[15251726167324940933581,102036655192082030049571]
67#=7858321551080267055879090: d=122:[1622809735530155467375019,6235511815550111588503949]
71#=557940830126698960967415390: d=134:[223434366489670279723129283,334506463637028681244285973]
73#=40729680599249024150621323470: d=142:[12251123298134136340115501239,28478557301114887810505822089]
79#=3217644767340672907899084554130: d=146:[373820356184888303848168311227,2843824411155784604050916242757]
83#=267064515689275851355624017992790: d=158:[113432160468908532259480385863871,153632355220367319096143632128761]
89#=23768741896345550770650537601358310: d=166:[5778890002143848542586755859217397,17989851894201702228063781742140747]
97#=2305567963945518424753102147331756070: d=178:[458816837954175912628962062911613131,1846751125991342512124140084420142761]

Сравнивать их с точными максимальными расстояниями и местом их появления (единичной разницей пренебречь) оставлю Вам.
Но сразу видно что совпадение с функцией Якобсталя далеко не полное, отличается как минимум для $23\#, 37\#, 43\#$ и далее кажется везде.

Интересно что в таблице мест появления есть несоответствия, например для $31\#$ у меня адрес $74959204291$, там же указан второй $125601285781$, но это видимо не ошибка, а просто одно из чисел в промежутке делится на само $31$, что они у себя исключают. Так что оказывается пользоваться таблицей надо с осторожностью.

[vicvolf]

vicvolf в сообщении #1512849 писал(а):

Если одно из граничных значений ПСВ$p_{r-1}\#$, например, $p_{r-1}\#-1$ будет кратно $p_r$, а на $r+1$ шаге решета Эратосфена окажется кратным $p_{r+1}$ другой граничный вычет $p_{r-1}\#+1$, то между вычетами образуется максимальное расстояние для первого ПСВ$p_{r-1}\#$ с учетом границы (вложенного в ПСВ$p_r\#$), равное $p_{r-1}\#+p_r-(p_{r-1}\#-p_r)=2p_r$.

Обратите внимание, что я здесь говорю только про первый ПСВ$p_{r-2}\#$ с учетом границы.Там максимум,если достигается на границе, то равен $2p_{r-1}$, поэтому я просил проверить с учетом границы. А если он не достигается на границе первого ПСВ$p_{r-2}\#$, то внутри первого ПСВ$p_{r-2}\#$ максимум меньше $2p_{r-1}$, что и подтвердил расчет.
Глобальный максимум всего ПСВ$p_{r}\#$ может быть больше, но он находится за пределами первого ПСВ$p_{r-2}\#$, а у меня интервал $(1,p^2_{r+1})$ находится в пределах первого ПСВ$p_{r-2}\#$ при $p_r>11$. Поэтому для простых чисел этого интервала выполняется $d(p^2_{r+1}) <2p_{r-1}$.

[Yury_rsn]

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

Yury_rsn
Насчёт правее или левее, вот вам данные по стыкам праймориалов $p_{r-2}\#$ и расстояниях на них (праймориал, максимальное расстояние, где встречается):[code]

Спасибо!
Сравнением уже завтра займусь

Пересчитал формулы, которые выше - по стыкам позапредыдущих праймориалов

$11\#:113+14$ _ _ _ _ _ _ _ _ _$113=5\#\cdot4 - 7$
$13\#:9439+22$ _ _ _ _ _ _ _ _ $9439= 7\#\cdot45 - 11$
$17\#:217127+26$ _ _ _ _ _ _ _ $217127=11\#\cdot94 - 13$
$19\#:60043+34$ _ _ _ _ _ _ _ _$60043=13\#\cdot2 -17$
$23\#:20332471+40$ _ _ _ _ _ _$20332471=17\#\cdot40 - 87929$
$29\#:417086647+46$ _ _ _ _ _ $417086647=19\#\cdot43 - 23$

Ваше число, из сегодняшней таблицы, по стыкам праймориала:
$23\#:29609561+38$ _ _ _ _ _ _$29609561=17\#\cdot58 - 19$

[vicvolf]

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

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

А начиная с ПСВ 23# закономерности меняются?

Нет. Эти разности $2p_{r-1}$ существуют в любой ПСВ, но не являются максимальными, кроме
ПСВ$(29\#)$ , $(31\#)$ , $(41\#)$.

Да, разности $2p_{r-1}$ образуются в случае объединения максимальных разностей на границах ПСВ$p_{r-2}\#$. Поэтому они располагаются симметрично внутри ПСВ$p_r\#$ на большом расстоянии друг от друга и при следующем шаге решета Эратосфена не могут объединяться. Внутри ПСВ$p_{r+1}\#$, на следующем шаге решета Эратосфена, могут объединяться только разности меньших размеров, которые находятся на расстоянии одного вычета, кратного $p_{r+1}$. Однако, таких разностей, находящихся на расстоянии одного вычета, кратного $p_{r+1}$, может быть больше двух. За счет их объединения и возникают расстояния между вычетами ПСВ$p_{r+1}\#$ больше $2p_{r}$.
Как подсчитал vorvalm данные расстояния не могут превосходить в ПСВ$p_r\#$ значение $4p_{r+1}$. Отсюда следует, что максимальное расстояние между простыми на интервале $(1,p^2_{r+1})$ в ПСВ$p_r\#$ не превосходит $4p_{r+1}$.

[Yury_rsn]

vicvolf в сообщении #1513036 писал(а):

Как подсчитал vorvalm данные расстояния не могут превосходить в ПСВ$p_r\#$ значение $4p_{r+1}$. Отсюда следует, что максимальное расстояние между простыми на интервале $(1,p^2_{r+1})$ в ПСВ$p_r\#$ не превосходит $4p_{r+1}$.

Есть ли доказательство - "не превосходит $4p_{r+1}$"?
Или это пока только наблюдения в некоторых частных случаях?
Я вроде не помню. Если есть напишите, пожалуйста.

В OEIS есть формула верхней границы. Теренс Тао и товарищи.
Она трехэтажная, с кучей вложенных логарифмов.

[vicvolf]

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

Исходя из указанного метода определения разностей в ПСВ($p_r\#$), можно сделать вывод,
что максимальная разность между вычетами в этих ПСВ не может превышать $d=4p_{r+1}$

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

vicvolf в сообщении #1511769 писал(а):

Почему?

В любую разность $d>4p_{r+1} $ попадет цепочка вычетов, кратных $p_{r+1}$

Полное доказательство может быть у vorvalm.

[vorvalm]

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

В OEIS есть формула верхней границы. Теренс Тао и товарищи.

Дайте ссылку.

[Yury_rsn]

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

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

В OEIS есть формула верхней границы. Теренс Тао и товарищи.

Дайте ссылку.

A048670
В разделе FORMULA

Кроме того, где-то недавно видел статью Теренса Тао и Ко, где эта формула уточняется.
Там среди авторов - Конягин.
Надо поискать, счас не нашел