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

[vicvolf]

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

Вот начало таблицы для интервала от следующего простого до его же квадрата, показываю только моменты смены любого из двух чисел:

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

5#:     6       23
7#:     8       89
11#:    14      113
23#:    18      523
29#:    20      887
31#:    34      1327
97#:    36      9551
113#:   44      15683
139#:   52      19609
173#:   72      31397
389#:   86      155921
599#:   96      360653
607#:   112     370261
701#:   114     492113
1153#:  118     1349533
1163#:  132     1357201
1409#:  148     2010733
2153#:  154     4652353
4129#:  180     17051707
4561#:  210     20831323

Эта таблица согласуется с моей гипотезой $d(p^2_{r+1}) \leq 2p_{r-1}$.

[Yury_rsn]

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

Итак, максимальная разность между вычетами ПСВ($p_r\#$) может быть равна $4p_{r+1}$.
Последовательность AO48670 показывает, что с ростом порядкового номера
простых чисел относительная разность ($c=d/p_r$) между вычетами ПСВ($p_r\#$)
увеличивается и к концу таблицы составляет $c=3,5$.

Можно уточнить - вы имеете в виду максимальную разность в любом месте интервала длиной $p_r\#$ ?
Т.е., именно функцию Якобсталя, а не максимальную разность на отрезке от $p_{r}^2$ до $p_{r+1}^2$ ?

[vorvalm]

Разность $ 4p_{r+1}$ относится к интервалу $p_r\#$

[vicvolf]

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

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

Можно более подробнее, пожалуйста.

Вы правильно обратили внимание, что $p_{r+1}$ ПСВ$p_r\#$ вкладываются в одно ПСВ$p_{r+1}\#$. Но обратите внимание, как при этом вкладывается интервал $(1,p^2_{r+1})$. Интервал $(1,121)$ захватывает несколько ПСВ$5\#$, а интервал $(1,169)$ находится уже в одном ПСВ$7\#$, интервал $(1,289)$ находится также в одном ПСВ$11\#$ и.т.д. Поэтому эти интервалы не могут находится на стыке ПСВ, как это было в случае ПСВ$5\#$ и давать ситуация слияния максимальных расстояний на границах ПСВ.

Немного дополню.

Возьмем ПСВ$11\#$, состоящий из ПСВ$7\#$, до выбрасывания чисел кратных $11$: $1,11,...113,121,127,...,169,...199,209,211,221,....2299,2309$

Обратим внимание, что интервал $(1,169)$ не выходит за пределы первого ПСВ$7\#$, поэтому не может быть ситуация, что при удалении чисел кратных $11$ ,будет удалено число на границе ПСВ и получится расстояние равное $2 \cdot 10+2=22=2p_r$, а удаляется число $121$ внутри ПСВ$7\#$ и получаем расстояние $2 \cdot 6+2=14=2p_{r-1}$.

Аналогично с ПСВ$13\#$, состоящее из ПСВ$11\#$, до выбрасывания чисел кратных $13$: $1,13,..,199,209,211,221,..,289,..,2297,2309,2311,..30029$. Интервал $(1,289)$ не выходит за пределы первого ПСВ$11\#$, поэтому не может быть ситуация, что при удалении чисел кратных $13$ ,будет удалено число на границе ПСВ и получится расстояние равное $2 \cdot 12+2=26=2p_r$, а удаляется число $209$ внутри ПСВ$7\#$ и получаем новое расстояние $199,211$, которое меньше $113,127$, поэтому последнее остается наибольшим, но уже меньшим $2p_{r-1}$ и.т.д.

[Yury_rsn]

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

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

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

Можно более подробнее, пожалуйста.

Вы правильно обратили внимание, что $p_{r+1}$ ПСВ$p_r\#$ вкладываются в одно ПСВ$p_{r+1}\#$. Но обратите внимание, как при этом вкладывается интервал $(1,p^2_{r+1})$. Интервал $(1,121)$ захватывает несколько ПСВ$5\#$, а интервал $(1,169)$ находится уже в одном ПСВ$7\#$, интервал $(1,289)$ находится также в одном ПСВ$11\#$ и.т.д. Поэтому эти интервалы не могут находится на стыке ПСВ, как это было в случае ПСВ$5\#$ и давать ситуация слияния максимальных расстояний на границах ПСВ.

Немного дополню.

Возьмем ПСВ$11\#$, состоящий из ПСВ$7\#$, до выбрасывания чисел кратных $11$: $1,11,...113,121,127,...,169,...199,209,211,221,....2299,2309$

Обратим внимание, что интервал $(1,169)$ не выходит за пределы первого ПСВ$7\#$, поэтому не может быть ситуация, что при удалении чисел кратных $11$ ,будет удалено число на границе ПСВ и получится расстояние равное $2 \cdot 10+2=22=2p_r$, а удаляется число $121$ внутри ПСВ$7\#$ и получаем расстояние $2 \cdot 6+2=14=2p_{r-1}$.

Аналогично с ПСВ$13\#$, состоящее из ПСВ$11\#$, до выбрасывания чисел кратных $13$: $1,13,..,199,209,211,221,..,289,..,2297,2309,2311,..30029$. Интервал $(1,289)$ не выходит за пределы первого ПСВ$11\#$, поэтому не может быть ситуация, что при удалении чисел кратных $13$ ,будет удалено число на границе ПСВ и получится расстояние равное $2 \cdot 12+2=26=2p_r$, а удаляется число $209$ внутри ПСВ$7\#$ и получаем новое расстояние $199,211$, которое меньше $113,127$, поэтому последнее остается наибольшим, но уже меньшим $2p_{r-1}$ и.т.д.

У меня не получается мысленно охватить в полном объеме - насколько ваши соображения работают во всех возможных ситуациях.
А вдруг возникнут какие-то другие исключения или совпадения?

В памяти всплывает цитата из Википедии:

Цитата:

На самом деле, интервал между простыми величины P может встретиться между простыми, гораздо меньшими, чем P#. Например, самая первая последовательность из 71 последовательных составных чисел находится между 31398 и 31468, в то время как 71# является 27-значным числом.

https://ru.wikipedia.org/wiki/%D0%98%D0 ... 0%BC%D0%B8

[vicvolf]

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

В памяти всплывает цитата из Википедии:

Цитата:

На самом деле, интервал между простыми величины P может встретиться между простыми, гораздо меньшими, чем P#. Например, самая первая последовательность из 71 последовательных составных чисел находится между 31398 и 31468, в то время как 71# является 27-значным числом.

Вот как раз об этом я и говорю - максимальное расстояние между вычетами ПСВ$71\#$ равно 174, а на интервале данной ПСВ расстояние значительно меньше $d(73^2)=34<2 \cdot 67=2p_{r-1}$.

Я уже объяснял, почему $d(p^2_{r+1}) < 2p_{r}$. Легко убедиться, что в ПСВ$11\#$ максимальное расстояние на интервале равно $d(13^2)=14=2p_{r-1}$. Я также объяснял, почему при больших ПСВ максимальное расстояние на интервале уменьшается и выполняется $d(p^2_{r+1}) < 2p_{r-1}$.

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

[Yury_rsn]

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

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

На самом деле максимальный интервал для праймориала p# на отрезке от 1 до $p_{r+1}^2$ не должен превышать 2p, чтобы выполнялась гипотеза Лежандра

Справедлива более сильная гипотеза:

$d(p^2_{r+1}) \leq 2p_{r-1}$.

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

Равенство $d(p^2_{p_{r+1}})=2p_{r-1}$ достигается при $p_r=11$, т.е. $d(13^2)=2 \cdot 7=14$.

Обратим внимание, как получилось расстояние $14$. На границе 3ПСВ5$\#$ и 4ПСВ5$\#$ находятся максимальные расстояния $6$: $113-119,121-127$. При следующем шаге решета Эратосфена и переходе к ПСВ7$\#$ удаляется кратное 7 число 119, а при следующем шаге при переходе к ПСВ11$\#$ удаляется кратное 11 число 121 и получается максимальное расстояние $113-127$.

Далее такая ситуация не возникает, потому что интервал $(1,169)$ получается в первой ПСВ7$\#$, а интервал $(1,289)$ - в первой ПСВ11$\#$ и.т.д. Мы не попадаем на границу ПСВ и не может возникнуть ситуация со слиянием максимальных расстояний на границах ПСВ, как в первом случае. Поэтому далее везде выполняется $d(p^2_{r+1}) < 2p_{r-1}$.

Кажется, начинает доходить
Можно одну мелочь уточнить?

Цитата:

На границе 3ПСВ5$\#$ и 4ПСВ5$\#$ находятся максимальные расстояния $6$: $113-119,121-127$.

3ПСВ5 и 4ПСВ5 - это наверное ошибка?
Должно быть 4ПСВ5 и 5ПСВ5 ?

Чего-то меня это мелкая ошибка сбила с толку, и дальше мысль пошла не по резьбе )

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

[Yury_rsn]

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

...
Для этого надо найти цепочки вычетов, сравнимых с простыми модулями $p=5, 7, 11,...$
не затрагивая вычетов 0 и $d.$
Затем распределить эти цепочки так, чтобы они, по возможности, не мешали друг другу,
т.е. имели бы минимум общих вычетов.
Последовательно вычеркивая эти цепочки, мы дойдем до того,
что останутся вычеты, не входящие ни в какие цепочки.
Чтобы вычеркнуть их, на каждый вычет потребуется свое простое число в любом порядке.
Наибольшее простое число, которым будет вычеркнут последний вычет и будет тем $p_r$,
который и определяет ПСВ, в которой есть данная разность $d.$

Пример 1.
$d=40$. Берем группу вычетов с разностями (4,2,4,2...)
(0,4,6,10,12,16,18,22,24,28,30,34,36,40)
Всего вычетов 14. Надо вычеркнуть 12 вычетов.
Определяем цепочки сравнимых вычетов с максимальным числом вычетов.

$p=5,\;(4,24,34),\;\;\;\;\;\;\;\;N=3.$
$p=7,\;(16,30)),\;\;\;\;\;\;\;\;\;\;N=2.$
$p=11,\;(6,28),\;\;\;\;\;\;\;\;\;\;\;N=2.$
$p=13,\;(10,36),\;\;\;\;\;\;\;\;\;N=2$
$p=17,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1$
$p=19,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$
$p=23,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$


$\sum N=12.$ Следовательно, разности $d=40$ есть ПСВ по модулю $M(23).$
Причем, по числу вычетов, не имеющих цепочек, можно определить число разностей $d$ в данной ПСВ.
Цепочки сравнимых вычетов мы трогать не можем, но свободные простые числа могут менять свои места и число
разностей d равно числу перестановок из этих вычетов.
В нашем случае $P_3=3!=6.$ Но т.к. разность $d=40$ может быть представлена
симметрично, то их число увеличивается до 12.
Этот процесс поддается программированию

Пример 2
$d=90$.
(0,4,6,10,12,16,18,22,24,28,30,34,36,40,42,48,52,54,58,60,64,66,70,72,76,78,82,64,88,90)
Всего вычетов 31. Надо вычеркнуть 29 вычетов.
Определяем цепочки сравнимых вычетов.

$p=5,\;(12,22,42,52,72,82),\;N=6.$
$p=7,\;(4,18,46,60,88),\;\;\;\;\;\;\;N=5.$
$p=11,\;(10,54,76),\;\;\;\;\;\;\;\;\;\;\;\;N=3.$
$p=13,\;(6,58,84),\;\;\;\;\;\;\;\;\;\;\;\;N=3$
$p=17,\;(30,64),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=2$
$p=19,\;(28.66),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=2.$
$p=23,\;(24,70),\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=2.$
$p=29,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$
$p=31,\;(16,78),\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=2.$
$p=37,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$
$p=41,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$
$p=43,\;(-),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;N=1.$

$\sum N=29.$ Следовательно, разности $d=90$ есть в ПСВ по модулю $M(43).$
В нашем случае $P_4=4!=24.$ Но т.к. разность $d=90$ может быть представлена
симметрично, то их число увеличивается до 48.

Вопрос по второму примеру - $d=90$
Похоже, приходится подбирать цепочки методом тыка?
Если в первом примере, для $d=40$ особенно нет вариантов, как расположить цепочки - сразу заметно, что по-другому они не станут.
То во втором случае вариабельность больше, и удачный вариант расстановки не так очевиден.
Есть ли какой-то эффективный метод "правильной" начальной расстановки цепочек - для вычеркивания максимального интервала,
или только путем подбора?

[vorvalm]

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

Есть ли какой-то эффективный метод "правильной" начальной расстановки цепочек - для вычеркивания максимального интервала,
или только путем подбора?

По крайней мере цепочки сравнимых с 5,7,11 не должны мешать друг другу, а остальное
дело удачи.
Попробуйте потренироваться с $d=100$.

[vicvolf]

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

Можно одну мелочь уточнить?

Цитата:

На границе 3ПСВ5$\#$ и 4ПСВ5$\#$ находятся максимальные расстояния $6$: $113-119,121-127$.

3ПСВ5 и 4ПСВ5 - это наверное ошибка?
Должно быть 4ПСВ5 и 5ПСВ5 ?

Да, эта описка.

[Yury_rsn]

vicvolf
Правильно ли я помню тезисы коллективного обсуждения в этой ветке?

1. Для любого праймориала $p_r\#$, все взаимно простые с этим праймориалом числа, расположенные на отрезке от 1 до $p_{r+1}^2$ - являются простыми.

2. Для каждого праймориала определяем разность d - между любыми соседними вычетами в ПСВ этого праймориала (т.е. между соседними взаимно простыми с этим праймориалом числами).
Любой интервал длиной d, расположенный между соседними взаимно простыми с этим праймориалом числами, и находящийся на отрезке от 1 до $p_{r+1}^2$ - слева и справа граничит с простыми числами. Это следствие из пункта 1.

3. Для того, чтобы гипотеза Лежандра была верна, необходимо, чтобы для каждого праймориала $p_r\#$ выполнялось условие:
- на отрезке от 1 до $p_{r+1}^2$ максимальное значение d, не должно превышать $2p_{r}$ (первый вариант),
или
- (уточненный вариант). Максимальное значение d не должно превышать $2p_{r}$ - на отрезке от $p_{r}^2$ до $p_{r+1}^2$

4. Можно доказать, что исходя из вложенности праймориалов, на самом деле выполняется даже более сильное условие
$d(p^2_{r+1}) < 2p_{r-1}$.
---

Таким образом, если не упущены какие-то важные моменты, и все вышеприведенные пункты не содержат ошибок, то можно предположить гипотезу Лежандра доказанной?

[vicvolf]

Yury_rsn
п.п. 1 и 2 очевидны, а вот п.3 надо аккуратно доказать.

[Yury_rsn]

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

Yury_rsn
п.п. 1 и 2 очевидны, а вот п.3 надо аккуратно доказать.

.
Да, п.3 я просто продемонстрировал на числовом примере.
Постараюсь сегодня, наверное ближе к концу дня, переписать в общем виде.

[Yury_rsn]

Цитата:

"... пусть для праймориала 197# на отрезке от 1 до $199^2$ максимальный интервал между соседними взаимно простыми с 197# числами всегда меньше $2\cdot197$. (где бы он ни был (максимальный интервал) расположен на отрезке от 1 до $199^2$, справа и слева от него будут находиться простые числа)
- формула разности квадратов $(n+1)^2-n^2=2n+1$. Число $2\cdot197$ по этой формуле - ($\approx2n+1$), соответствует разности квадратов $198^2-197^2$.
Следовательно, мы можем утверждать, что между $197^2$ и $198^2$ обязательно будет находиться как минимум одно простое число.

И для отрезка между $198^2$ и $199^2$ - тем более это условие выполняется. Интервал $2\cdot197$ - также меньше разности квадратов $199^2$ - $198^2$.

Запишем эти рассуждения в общем виде.

1. Для любого простого числа $p_{r}$ предположим, что всегда выполняется условие:
- максимальная величина интервала, длиной d, между любыми соседними, взаимно простыми с праймориалом $p_{r}\#$ числами, на отрезке от 1 до $p_{r+1}^2$ не должна превышать 2$p_{r}$.

2. Как известно, все взаимно простые с праймориалом $p_{r}\#$ числа, расположенные на отрезке от 1 до $p_{r+1}^2$, являются простыми.
Следовательно, по краям любого интервала, длиной d, расположенного в любом месте на отрезке от 1 до $p_{r+1}^2$, находятся простые числа.

3. Утверждение:
"Если выполняется условие из п.1, то между всеми подряд последовательными квадратами, расположенными на отрезке от $p_{r}^2$ до $p_{r+1}^2$, всегда будет находиться хотя бы одно простое число".

Док-во.
Расстояние между соседними квадратами равно $(n+1)^2-n^2=2n+1$. Число $2p_{r}$, согласно этой формулы, на единицу меньше расстояния между квадратами $(p_{r})^2$ и $(p_{r}+1)^2$. И, следовательно, между этими последовательными квадратами находится, как минимум, одно простое число.

Очевидно, что число $2p_{r}$ точно так же не превышает расстояния между следующими последовательными квадратами $(p_{r}+1)^2$ и $(p_{r}+2)^2$,
и между следующими $(p_{r}+2)^2$ и $(p_{r}+3)^2$,
... и между $(p_{r+1}-1)^2$ и $(p_{r+1})^2$.

---
Таким образом, условие $d(p^2_{r+1}) < 2p_{r}$ является достаточным для того, чтобы утверждать:
"Между любыми двумя последовательными квадратами, расположенных на отрезке между $p_{r}^2$ и $p_{r+1}^2$, всегда находится хотя бы одно простое число"

[Yury_rsn]

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

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

В памяти всплывает цитата из Википедии:

Цитата:

На самом деле, интервал между простыми величины P может встретиться между простыми, гораздо меньшими, чем P#. Например, самая первая последовательность из 71 последовательных составных чисел находится между 31398 и 31468, в то время как 71# является 27-значным числом.

Вот как раз об этом я и говорю - максимальное расстояние между вычетами ПСВ$71\#$ равно 174, а на интервале данной ПСВ расстояние значительно меньше $d(73^2)=34<2 \cdot 67=2p_{r-1}$.

Я уже объяснял, почему $d(p^2_{r+1}) < 2p_{r}$. Легко убедиться, что в ПСВ$11\#$ максимальное расстояние на интервале равно $d(13^2)=14=2p_{r-1}$. Я также объяснял, почему при больших ПСВ максимальное расстояние на интервале уменьшается и выполняется $d(p^2_{r+1}) < 2p_{r-1}$.

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

Хотелось бы еще обсудить этот важный аспект.
Вложенность праймориалов показывает логику возрастания d на отрезке между квадратами соседних простых чисел - от $p_{r}^2$ до $p_{r+1}^2$.
Ок.
Но ведь максимальные d на всём праймориале - т.е., функция Якобсталя - тоже каким-то образом возникают из свойств вложенности праймориалов. Только эти максимальные интервалы появляются где-то дальше, вроде бы.
Мы можем проследить логику возникновения этих максимумов?
На стыке чего и чего они образовываются? Исходя из каких условий?