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

[Yury_rsn]

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

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

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

Можете это доказать?

- это следует из ранее приведенной цитаты:

Цитата:

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

2. Т.е., если для простого числа p известно, что максимальная разность между взаимно простыми с праймориалом p# числами не превышает p,
то это означает, что все интервалы между соседними квадратами от $((p-1)/2)^2$ до $p^2$ содержат простые числа.
Т.е., выполняется гипотеза Лежандра на этих отрезках.

---
Только обязательно должно выполняться важное условие:
"максимальная величина интервала для праймориала p# на отрезке от 1 до $p_{r+1}^2$ не должна превышать 2p - для всех p#, начиная с некоторого". (Т.е., исключений типа $p_r\#=\{5\#, 7\#, 11\#, 31\#\}$ - не должно быть бесконечно много)

Рассмотрим значение 2p вместо p на том же примере.

"... пусть для праймориала 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$.

2. Теперь вопрос -
а может ли отрезок между $196^2$ и $197^2$
содержать только составные числа (т.е., ни одного простого)?

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

И рассмотрим праймориал предыдущего простого числа - 193
Максимальный интервал для этого 193# по условию не превышает $2\cdot193$, и следовательно между квадратами $193^2$ и $194^2$ обязательно будет находиться хотя бы одно простое число.
Аналогично, и для $194^2$ и $195^2$, и для $195^2$ и $196^2$, и для $196^2$ и $197^2$.
---
Далее по индукции

[vicvolf]

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

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

А как Вы собираетесь доказать, что выполняется данное требование?

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

Т.е., исключений типа $p_r\#=\{5\#, 7\#, 11\#, 31\#\}$ - не должно быть бесконечно много)

Для этих прайморилов соотношение $d(p^2_{r+1}) \leq 2p_r$ как раз выполняется.

[Yury_rsn]

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

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

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

А как Вы собираетесь доказать, что выполняется данное требование?

Это еще надо придумать
Есть некоторые мысли.

Цитата:

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

Т.е., исключений типа $p_r\#=\{5\#, 7\#, 11\#, 31\#\}$ - не должно быть бесконечно много)

Для этих прайморилов соотношение $d(p^2_{r+1}) \leq 2p_r$ как раз выполняется.

- а вдруг появятся другие исключения?
Ну, то есть надо доказать гипотезу, которая выше, и тогда всё будет хорошо.

-- 27.03.2021, 16:58 --

Цитата:

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

11#:    2:17    4:13    6:23    8:89    10:139  12:1    14:113
13#:    2:17    4:19    6:23    8:89    10:139  12:199  14:113
17#:    2:29    4:19    6:23    8:89    10:139  12:199  14:113
19#:    2:29    4:37    6:23    8:89    10:139  12:199  14:113
23#:    2:29    4:37    6:31    8:89    10:139  12:199  14:113
29#:    2:41    4:37    6:31    8:89    10:139  12:199  14:113
31#:    2:41    4:37    6:47    8:89    10:139  12:199  14:113
37#:    2:41    4:43    6:47    8:89    10:139  12:199  14:113
41#:    2:59    4:43    6:47    8:89    10:139  12:199  14:113
43#:    2:59    4:67    6:47    8:89    10:139  12:199  14:113
47#:    2:59    4:67    6:53    8:89    10:139  12:199  14:113
53#:    2:59    4:67    6:61    8:89    10:139  12:199  14:113
59#:    2:71    4:67    6:61    8:89    10:139  12:199  14:113
61#:    2:71    4:67    6:73    8:89    10:139  12:199  14:113
67#:    2:71    4:79    6:73    8:89    10:139  12:199  14:113
71#:    2:101   4:79    6:73    8:89    10:139  12:199  14:113
73#:    2:101   4:79    6:83    8:89    10:139  12:199  14:113
79#:    2:101   4:97    6:83    8:89    10:139  12:199  14:113
83#:    2:101   4:97    6:131   8:89    10:139  12:199  14:113
89#:    2:101   4:97    6:131   8:359   10:139  12:199  14:113
97#:    2:101   4:103   6:131   8:359   10:139  12:199  14:113
101#:   2:107   4:103   6:131   8:359   10:139  12:199  14:113
103#:   2:107   4:109   6:131   8:359   10:139  12:199  14:113
107#:   2:137   4:109   6:131   8:359   10:139  12:199  14:113
109#:   2:137   4:127   6:131   8:359   10:139  12:199  14:113
113#:   2:137   4:127   6:131   8:359   10:139  12:199  14:293
127#:   2:137   4:163   6:131   8:359   10:139  12:199  14:293
131#:   2:137   4:163   6:151   8:359   10:139  12:199  14:293
137#:   2:149   4:163   6:151   8:359   10:139  12:199  14:293
139#:   2:149   4:163   6:151   8:359   10:181  12:199  14:293
149#:   2:179   4:163   6:151   8:359   10:181  12:199  14:293
151#:   2:179   4:163   6:157   8:359   10:181  12:199  14:293
157#:   2:179   4:163   6:167   8:359   10:181  12:199  14:293
163#:   2:179   4:193   6:167   8:359   10:181  12:199  14:293
167#:   2:179   4:193   6:173   8:359   10:181  12:199  14:293
173#:   2:179   4:193   6:233   8:359   10:181  12:199  14:293
179#:   2:191   4:193   6:233   8:359   10:181  12:199  14:293
181#:   2:191   4:193   6:233   8:359   10:241  12:199  14:293
191#:   2:197   4:193   6:233   8:359   10:241  12:199  14:293
193#:   2:197   4:223   6:233   8:359   10:241  12:199  14:293
197#:   2:227   4:223   6:233   8:359   10:241  12:199  14:293
199#:   2:227   4:223   6:233   8:359   10:241  12:211  14:293
 

14 - характерная разность для логики вложенности праймориалов друг в друга.
Матрешки, типа

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

Т.е., не может такого быть, что если, например, в праймориале 13# разность d=14 в первый раз появилась на 113 позиции, то, допустим, в 97# она вдруг появится раньше (к примеру, на 89 позиции).

Предположим теперь, что гипотеза $d(p^2_{r+1}) \leq 2p_r$ НЕ выполняется, начиная с некоторого $p_r\#$.
Откуда на этом праймориале на отрезке от 1 до $p_{r}^2$ может взяться бОльшая разность, если ее не было на предыдущем праймориале?
Значит, можно предположить, что "увеличенная" разность $d(p^2_{r+1}) > 2p_r$ может возникнуть в каком-то новом праймориале только на отрезке от $p_r^2$ до $p_{r+1}^2$

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

[vicvolf]

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

Достаточно, чтобы условие $d(p^2_{r+1}) \leq 2p_r$ выполнялось только на отрезке от $p_r^2$ до $p_{r+1}^2$

Правильно.

[vorvalm]

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

[vicvolf]

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

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

Почему?

[vorvalm]

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

Почему?

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

[vicvolf]

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}$.

[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}$.

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

-- 29.03.2021, 03:51 --

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

Чтобы определить, есть ли разность $d$ в ПСВ не обязательно создавать ПСВ и искать в ней эту разность.
Можно поставить вопрос иначе. По данной разности найти ПСВ, в которой эта разность есть.
Для этого надо представить искомую разность $d$ в виде группы вычетов по модулю $M=6.$
Здесь возможны 2 варианта по разностям в группе:
1) 2, 4, 2, 4,.....(0, 2, 6, 8, 12,...$d$)
2) 4, 2, 4, 2,.....(0, 4, 6, 10, 12,...$d$)
Вычеты 0 и $d$ являются крайними вычетами группы и должны оставаться на своих местах.
Остальные вычеты мы будем вычеркивать в зависимости от сравнимости их с простыми числами $p>3$.
Для этого надо найти цепочки вычетов, сравнимых с простыми модулями $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.
Этот процесс поддается программированию

Я только сейчас разобрался с этим способом. У меня что-то подобное тоже получалось, но у вас более эффективно

Только давайте уточним терминологию, плиз.

Цитата:

Для этого надо найти цепочки вычетов, сравнимых с простыми модулями $p=5, 7, 11,...$

По-моему, точнее будет сказать - "вычетов, сравнимых между собой по модулю этих простых чисел.
Тогда сразу становится понятным, что это за цепочки. 4 $\equiv$24 $\equiv$34(mod 5)
16 $\equiv$ 30(mod 7)
...

Цитата:

Цепочки сравнимых вычетов мы трогать не можем, но свободные простые числа могут менять свои места

Ну, по идее, цепочки можно сдвигать - если есть возможность.
Просто в этом случае они имеют только один вариант взаимного размещения, при котором у них не совпадают вычеты. И они тем самым перекрывают максимальное количество вычетов.
Как минимум, имеется "зеркальное" расположение - 6 $\equiv$16 $\equiv$36(mod 5)
10 $\equiv$ 24(mod 7) и т.д.

[vorvalm]

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

Только давайте уточним терминологию, плиз.

Не надо. Сравнимые вычеты по модулю сравнимы и между собой.

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

Ну, по идее, цепочки можно сдвигать - если есть возможность.

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

[vicvolf]

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

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}$.

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

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

[Yury_rsn]

Цитата:

vorvalm в сообщении #1511021 писал(а):
Чтобы определить, есть ли разность $d$ в ПСВ не обязательно создавать ПСВ и искать в ней эту разность.
Можно поставить вопрос иначе. По данной разности найти ПСВ, в которой эта разность есть.

Ок. Интересный подход
Имхо, есть определенные перспективы.

[vorvalm]

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

[vicvolf]

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

Итак, максимальная разность между вычетами ПСВ($p_r\#$) может быть равна $4p_{r+1}$.

Очевидно, что $c$ не может быть больше 4.

Наверху в строке говорится о максимальной разности в ПСВ($p_r\#$) - $4p_{r+1}$, а в нижней строке уже $4p_{r}$?

[vorvalm]

Спасибо. Опечатка.Должно быть

$c=d/p_{r+1}$