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

[vicvolf]

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

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

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

В п. 1 все верно, а зачем менять это условие в Утверждении п.3. Тем более Вы тогда не можете использовать в доказательстве простые числа: $2,...,p_r$.
Я понимаю, что из последнего варианта следует первый, но это лучше использовать при доказательстве первого варианта, а не гипотезы Лежандра.

-- 03.04.2021, 12:07 --

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

Но ведь максимальные d на всём праймориале - т.е., функция Якобсталя - тоже каким-то образом возникают из свойств вложенности праймориалов.

Именно так. Но когда мы берем интервал $(1,p^2_{r+1})$, то при $p_r>11$ мы отсекаем эти значения.

[Yury_rsn]

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

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

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

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

В п. 1 все верно, а зачем менять это условие в Утверждении п.3. Тем более Вы тогда не можете использовать в доказательстве простые числа: $2,...,p_r$.
Я понимаю, что из последнего варианта следует первый, но это лучше использовать при доказательстве первого варианта, а не гипотезы Лежандра.

Я решил выделить основную идею в отдельный шаг доказательства.
Рассматривать условие $d(p^2_{r+1}) < 2p_{r}$ ведь имеет смысл только на отрезке от $p_{r}^2$ до $p_{r+1}^2$.
«Левее» этого отрезка условие просто становится неверным. Число $2p_{r}$ будет больше любой разности последовательных квадратов.
Общность доказательства от этого не теряется.

[vicvolf]

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

Рассматривать условие $d(p^2_{r+1}) < 2p_{r}$ ведь имеет смысл только на отрезке от $p_{r}^2$ до $p_{r+1}^2$. «Левее» этого отрезка условие просто становится неверным. Число $2p_{r}$ будет больше любой разности последовательных квадратов.

Это я не понял. На отрезке $(1,p^2_r)$ число $2p_{r}$ наоборот меньше разности последовательных квадратов. Например, $p_r=5,2p_r=10$. На интервале $(1,25)$ возьмем последовательные натуральные числа $12,13$. Разность их последовательных квадратов $13^2-12^2=169-144=25>10$.

[Yury_rsn]

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

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

Рассматривать условие $d(p^2_{r+1}) < 2p_{r}$ ведь имеет смысл только на отрезке от $p_{r}^2$ до $p_{r+1}^2$. «Левее» этого отрезка условие просто становится неверным. Число $2p_{r}$ будет больше любой разности последовательных квадратов.

Это я не понял. На отрезке $(1,p^2_r)$ число $2p_{r}$ наоборот меньше разности последовательных квадратов. Например, $p_r=5,2p_r=10$. На интервале $(1,25)$ возьмем последовательные натуральные числа $12,13$. Разность их последовательных квадратов $13^2-12^2=169-144=25>10$.

Это я, наверное, нечетко выразился.
Давайте по вашему примеру, чтобы не запутаться.
$p_r=5,2p_r=10$. Я имел в виду, что левее числа $p^2=25$ мы рассматриваем последовательные квадраты, которых сами меньше 25.
Т.е., 25 и 16 ($5^2;4^2$), 16 и 9 ($4^2;3^2$), и т.д.

И скорректирую цитируемую фразу:

Рассматривать условие $d(p^2_{r+1}) < 2p_{r}$ имеет смысл только на отрезке от $p_{r}^2$ до $p_{r+1}^2$. «Левее» этого отрезка условие становится неверным.
Число $2p_{r}$ будет больше любой разности последовательных квадратов, меньших чем $p_{r}^2$

[vicvolf]

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

Цитата:

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

Но гипотеза Лежандра говорит о том, что между любыми квадратами последовательных натуральных чисел обязательно находится простое число (без ограничений в интервале).

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

И скорректирую цитируемую фразу:
Рассматривать условие $d(p^2_{r+1}) < 2p_{r}$ имеет смысл только на отрезке от $p_{r}^2$ до $p_{r+1}^2$. «Левее» этого отрезка условие становится неверным.
Число $2p_{r}$ будет больше любой разности последовательных квадратов, меньших чем $p_{r}^2$

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

[Yury_rsn]

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

Я без понятия, написал программку что выдала первые несколько значений и поискал их в OEIS. И нашёл.
Процесс очень похож на поиск простых решетом Эратосфена, но как оттуда выцепить интервалы не представляю.

-- 05.07.2020, 23:31 --

Добавлю где обнаружились максимальные разности:
$11\#:113+14$
$13\#:9439+22$
$17\#:217127+26$
$19\#:60043+34$
$23\#:20332471+40$
$29\#:417086647+46$
Впрочем оказывается эти числа (точнее на 1 больше) есть в самой последовательности OEIS в разделе Links под именем "Robert Gerbicz, Table of n, a(n), u(n) for n=1..57, where every integer from [u(n),u(n)+a(n)-2] is divisible by at least one of the first n primes. Note that u(n) is not unique."

Я сегодня утром задал вопрос:

Цитата:

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

Слова "на стыке чего" - натолкнули меня на мысль кое-что посчитать.
Как вам эти соотношения?
$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$

[vorvalm]

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}$. Эти стыки легко можно вычислить.

[Dmitriy40]

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\#$ можно допустить что они на стыке каких-то праймориалов, то про остальные этого уже не скажешь.
Т.е. никакой особой регулярности не видно.

[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}$. Эти стыки легко можно вычислить.

Да, прозевал.
Можно ли привести таблицу этих стыков - для нескольких первых праймориалов?

[vicvolf]

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$

Да, это на границе, поэтому $d=2p_{r-1}$ и Вы правильно отразили, что максимум достигается на границе стыков.

Цитата:

$23\#:20332471+40$ _ _ _ _ _ _$20332471=19\#\cdot2 + 17\#\cdot2 - 13\#\cdot3 + 11\# - 5\#+1$
$29\#:417086647+46$ _ _ _ _ _ $417086647=23\#\cdot2 - 19\#\cdot3 + 23$

А это вне первого ПСВ$p_{r-1}\#$ с границей, но интервал $(1,p^2_{r+1})$ находится внутри первого ПСВ$p_{r-1}\#$, а на нем максимальное расстояние меньше $2p_{r-1}$, поэтому $d(p^2_{r+1})<2p_{r-1}$. Например, для ПСВ$29\#$ максимальное значение расстояния на первом, входящем в него ПСВ$23\#$ равно 40, что меньше $2 \cdot 23=2p_{r-1}$.

[Yury_rsn]

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

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

Цитата:

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

Но гипотеза Лежандра говорит о том, что между любыми квадратами последовательных натуральных чисел обязательно находится простое число (без ограничений в интервале).

Может быть я где-то ошибаюсь, но цепочка рассуждений примерно такая:

$p_{r}$ - это любое простое число.
$p_{r+1}$ - это следующее простое число.
Расстояние между ними может быть любым четным числом - от 2 до бесконечности.

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

Но мы будем сейчас рассматривать только отрезок от $p_{r}^2$ до $p_{r+1}^2$. Как будет видно дальше, этого вполне достаточно.

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

2. Если эта гипотеза верна, то очевидно, что
$(p_{r}+1)^2 - p_{r}^2 > 2p_{r}$,
$(p_{r}+2)^2 - (p_{r}+1)^2 > 2p_{r}$,
$(p_{r}+3)^2 - (p_{r}+2)^2 > 2p_{r}$,
...
$(p_{r+1} - 1)^2 - (p_{r+1} - 2)^2 > 2p_{r}$,
$p_{r+1}^2 - (p_{r+1} - 1)^2 > 2p_{r}$.
Т.е, между всеми последовательными квадратами, расположенными между $p_{r}^2$ до $p_{r+1}^2$ - обязательно будет встречаться хотя бы одно простое число.
(По краям интервала d обязательно находятся простые числа на отрезке до $p_{r+1}^2$. Очевидно, что любой интервал, длиной $d=2p_{r}$, хоть одним краем попадает между соседними квадратами)

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

Всё упирается только в верность гипотезы из пункта 1.

[vicvolf]

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

4. Поскольку $p_{r}$ - это любое простое число, то ограничение рассматриваемого отрезка только областью от $p_{r}^2$ до $p_{r+1}^2$, никак не уменьшает общность. Переходя от одного простого числа к другому, мы последовательно рассматриваем всю числовую ось.

$1^2,2^2$ в Ваш интервал не попадают, хотя между ними целых два простых числа: $2,3$. Хотя это легко проверяется. Вообще для конечного числа значений можно проверить, а для бесконечного надо доказать. Хотя надо обязательно писать фразу типа - легко проверить, что для таких-то конечных значений гипотеза справедлива.

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

Числовые примеры иногда могут вводить в заблуждение, хотелось бы увидеть ваш алгоритм в формализованном виде.
Можно вас попросить, написать это доказательство в общих символах?

[vorvalm]

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

Можно ли привести таблицу этих стыков - для нескольких первых праймориалов?

Эти стыки можно найти, решая систему сравнений.

$x\cdot p_{r-2}\#+1\mod p_{r-1}=0 x\cdot p_{r-2}\#-1\mod p_r=0 $

для любых $p_r$

[vicvolf]

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

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}\#$ меньше $2p_{r-1}$, который надо дополнительно доказывать. Я же говорил, что его надо еще проверять и проверять.