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

[Dmitriy40]

Да, я пытался разобраться в его алгоритме, на его же примере с $d=90$, но увидев что после вычёркивания $2$ и $3$ (оба лишь единственный вариант) для $5$ остаётся уже 4 варианта и все они вычёркивают по $5$ чисел, но вот дальше $7$ может вычеркнуть и $4$ и $3$ числа в зависимости от выбранного варианта для $5$. Проверив ещё чуть дальше убедился что никаких логических предпочтений выбирать варианты нет, а значит для построения гарантированно минимального числа придётся запускать полный перебор всех вариантов размещений вычетов. Вы фактически тоже подтверждаете это примером с вычёркиванием $7$, который "откладываете". Размышления как это всё логически обосновать без перебора всех вариантов и проверки следующих простых привели к мысли плюнуть и сделать просто обычный "жадный" алгоритм (термин из теории программирования), вычёркивающий любую подходящую комбинацию с максимальным количеством вычёркиваемых чисел на каждом шаге. Не обращая внимания что там будет дальше. Ну и ещё одну оптимизацию сделал, по мелочи. Это позволило запустить код на PARI/GP и добраться до $2111\#$ и далее, где и обнаружены контрпримеры к высказанным товарищами гипотезам. Это всё происходит в соседней теме.

-- 08.04.2021, 21:29 --

Yury_rsn
Никого из редакции OEIS здесь нет (UPD. Хотя нет, минимум один редактор бывает, но это неважно). Но это и не нужно, OEIS имеет право править любой (зарегистрировавшийся там), почти как и вики.
Надо ли править тот файл мне не очень понятно, в его названии или описании нигде нет слова minimal, а все числа наверняка являются правильными (лень проверять), в том смысле что по ним действительно находятся указанные интервалы. Потому его нельзя назвать ошибочным. Но почему там числа не минимальные мне непонятно. Может стоит добавить лишь указание что числа не минимальные и всё.

PS. Yury_rsn, не надо цитировать всё, есть кнопка Вставка.

[Yury_rsn]

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

Переписал программу расчёта взаимно простых с праймориалом чисел на асме, запустил, работает в 25 раз быстрее оптимизированного PARI/GP и в 200 раз быстрее неоптимизированного (оптимизированный не находил небольшие разности, только превышающие разности для предыдущего простого). Заодно сделал вывод всех встреченных разностей (только для текущей максимальной). Не знаю чем это кому-то поможет, но пусть будет. Так как список получился широким, то уберу под тег.

37#=7420738134810:
40/1
46/933091
48/7006073,39997751
50/48595307,48941621,78092957,126296171
54/132966023,213069617,494290273,539834299,964360157,1220754023,1524758177,1630313627,1687623739,1713880187,2091956627
56/2782823513
64/4683065593,151152153883
66/187219155593,271066740083 ...

Я опять извиняюсь, а разве может не быть среди разностей $d=31\cdot2=62$ ?

[Dmitriy40]

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

Я опять извиняюсь, а разве может не быть среди разностей $d=31\cdot2=62$ ?

Вероятно может, но разность $64$ встретилась раньше $62$. Тут я накапливал лишь последний обнаруженный максимум, не все вообще (хотя бы потому что разностей $2$ или $4$ там миллиарды).

[Yury_rsn]

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

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

Я опять извиняюсь, а разве может не быть среди разностей $d=31\cdot2=62$ ?

Вероятно может, но разность $64$ встретилась раньше $62$. Тут я накапливал лишь последний обнаруженный максимум, не все вообще (хотя бы потому что разностей $2$ или $4$ там миллиарды).

Ага, я вот это и хотел понять - встречается ли 66 раньше, чем 62.

Цитата:

PS. Yury_rsn, не надо цитировать всё, есть кнопка Вставка.

Я убрал в том комменте лишний текст.

[Dmitriy40]

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

Ага, я вот это и хотел понять - встречается ли 66 раньше, чем 62.

Это осталось непонятным: может $62$ вообще не встречается. А может всего лишь позже чем $64$.
Я подумаю, может и сделаю вывод всех разностей не меньше чем начальная (с 1 которая). Но это будет каша, вывод уже и так не слишком компактный, но пока хоть обозримый ... А этих боюсь будет много, очень.
Или скорее сделаю просто запоминание самого факта, какие разности встретились. Но не полный список, лишь впервые.
$37\#$ считалось больше 3ч.

[Yury_rsn]

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

Проверив ещё чуть дальше убедился что никаких логических предпочтений выбирать варианты нет,

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

Ну, и вопрос, который нас всё еще интересует на самом деле, - какие максимумы возможны на отрезках до $p^2_{r+1}$ в каждом $p_{r}\#$

-- 08.04.2021, 22:57 --

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

Это осталось непонятным: может $62$ вообще не встречается.

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

[vicvolf]

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

Размышления как это всё логически обосновать без перебора всех вариантов и проверки следующих простых привели к мысли плюнуть и сделать просто обычный "жадный" алгоритм (термин из теории программирования), вычёркивающий любую подходящую комбинацию с максимальным количеством вычёркиваемых чисел на каждом шаге. Не обращая внимания что там будет дальше. Ну и ещё одну оптимизацию сделал, по мелочи. Это позволило запустить код на PARI/GP и добраться до $2111\#$ и далее, где и обнаружены контрпримеры к высказанным товарищами гипотезам. Это всё происходит в соседней теме.

Я так и думал, что для вычисления вычетов для больших $p_r$ Вы используете методы оптимизации. Это конечно чудесно и Вы большой молодец, но для проверки гипотез это не всегда подходит. Ведь Ваш алгоритм может совпадать даже частично с алгоритмом, используемом в гипотезе и поэтому могут быть ложное совпадение результатов.

[Dmitriy40]

vicvolf
Для доказательства да, использовать сложно. А вот для поиска контрпримеров — вполне можно. Особенно если нужно найти хоть какой-нибудь контрпример, а не обязательно минимальный.

-- 08.04.2021, 22:53 --

Yury_rsn
Программу перезапустил, $31\#$ она уже просчитала, добавил в то своё сообщение (чтобы не плодить тексты) список обнаруженных разностей и где они впервые появились (или 0 если не обнаружены).
Про "оказывается нет" всё удалил, это я отвечал совсем не про то.

-- 09.04.2021, 2:09 --

Досчиталось и $37\#$, и да, разница $62$ присутствует, как и все остальные.

[Yury_rsn]

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

Досчиталось и $37\#$, и да, разница $62$ присутствует, как и все остальные.

Как минимум, теперь можно предположить, что во всех праймориалах появляются все разности, - от 2 до максимумов Якобсталя.
И видно, что первые появления разностей не пропорциональны их величине. (раньше казалось, что чем больше разность, тем правее она встречается в первый раз)

Для наглядности
62: _58 985 331 407 - максимум по стыкам
64: __4 683 065 593 -
66:187 219 155 593

[Dmitriy40]

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

Как минимум, теперь можно предположить, что во всех праймориалах появляются все разности, - от 2 до максимумов Якобсталя.

Нельзя: даже если забыть про отсутствие в $3\#$ разницы $2$, то в $13\#$ отсутствует разница $20$, а в $19\#$ нет разницы $32$. И они обе меньше удвоенного предыдущего простого.

[Yury_rsn]

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

в $13\#$ отсутствует разница $20$

Да, я проверил методом "окошек" - никак не получится.
По делимости на 2,3, чтобы получилась разница 20, число А должно быть сравнимо с 5 по модулю 6.
Тогда остаются незачеркнутыми такие окошки - A+2, A+6, A+8, A+12, A+14, A+18
(2, 6, 8, 12,14,18).

Для пятерок есть только два варианта 5(2, 12) и 5(8, 18)
А уже для семерок вообще нет вариантов, чтобы получилась цепочка из двух чисел.
Любые разности чисел 2, 6, 8, 12,14,18 между собой, не кратны 7.
Аналогично и для 11, и 13.

Т.е., чтобы вычеркнуть четыре оставшихся окошка, у нас остаются только три простых числа.
---
Как видно, "вычеркиваемость" интервалов определенной длины зависит от того, на какие простые числа из данного праймориала, могут делиться все возможные разности между числами-"окошками".
$12-2=2\cdot5$

$18-8=2\cdot5$
Любые разности между другими окошками кратны только 2 или 3

[Yury_rsn]

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

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

Примерно выглядит это так:
первое число диапазона делится на 2 и на 5,
второе - на 3,
третье на 2 и на 19, и на 29

Уже эти три условия дают выбор всего одного из 16530 чисел. А если добавите ещё пару условий, лучше про делимость на большие числа, то уже и перебор можно запустить.

Можно ли как-то оценить ограниченность длины интервалов на отрезке от $p^2_{r}$ до $p^2_{r+1}$, учитывая, что
максимальные делители любого числа, находящегося на этом отрезке, находятся в пределах от $p^2_{r}$/2 до $p^2_{r+1}$/2
Это, по идее, сильно ограничивает количество возможных комбинаций перестановок.

Ведь интервалы одинаковой длины на разных участках праймориала $p_{r}\#$ отличаются между собой только большими делителями чисел внутри интервала. (делителями, которые больше $p_{r}$)

[Dmitriy40]

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

Ведь интервалы одинаковой длины на разных участках праймориала $p_{r}\#$ отличаются между собой только большими делителями чисел внутри интервала. (делителями, которые больше $p_{r}$)

Не только, есть ещё стыки праймориалов. Там конечно тоже границы "выбиваются" кратными $p_{r+1}$, но вот до этого интервалы не идентичны вроде бы, да и их на один меньше.
Я думал об этом, но похоже лёгок лишь переход к одному-двум-трём следующим праймориалам, дальше же постепенно наступает полный хаос и переполнение памяти (придётся хранить все интервалы в праймориале, а их порядка $\varphi(p_r\#)$, что очень много).

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

Можно ли как-то оценить ограниченность длины интервалов на отрезке от $p^2_{r}$ до $p^2_{r+1}$,

Учитывая что на этом интервале все взаимно простые с $p_r\#$ являются и простыми, Вы хотите вот так не напрягаясь получить оценку интервалов между простыми? Ну-ну. Видя насколько сложные формулы для уже доказанных оценок я сильно сомневаюсь что у вас получится что-то вменяемое. Или оно будет слишком грубое и соответственно малополезное.

Без очень веских оснований не стоит считать всех математиков дураками надеяться что узнав пару фактов из матанализа (и арифметики вычетов) вдруг нашли волшебную палочку доказательство/решение открытой математической проблемы. Не только с этими интервалами, я про вообще.

[Yury_rsn]

(Оффтоп)

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

Без очень веских оснований не стоит

я вас чем-то обидел?
Вроде шел спокойный обмен мнениями. Никто ни от кого ничего не требовал.
Если возникла идея, ее нельзя формулировать?
Мне эта тема (функция Якобсталя в привязке к гипотезе Лежандра) интересна.
Были бы доступны статьи на русском, меньше бы приходилось догадываться и спрашивать. Мне казалось, что и другим участникам интересно.
Удивительно, как такая чисто-нейтральная наука, как математика, вызывает иногда непредсказуемые эмоции.

-- 10.04.2021, 19:47 --

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

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

Ну, не получится, и ладно.
Но вдруг у кого-то мелькнет идея.
Всяко бывает

[Dmitriy40]

(Оффтоп)

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

я вас чем-то обидел?

Нет конечно, просто задаёте вопросы, на некоторые из которых уже есть ответы, а про некоторые известно что это трудная математическая проблема. И почему бы не подумать не сводится ли вопрос к таким известным штукам ...
Вон например и vicvolf и vorvalm здесь накидали утверждений, неверность которых оказывается давно известна, в том числе и им самим, уж первому точно, даже здесь в теме выше было опровержение. Зачем спрашивается ... А Вы кстати могли (не проверял да или нет) ими пользоваться как верными ...
Ну и я привык как-то что если программа не завершилась за пару минут, то стоит подумать и оценить сколько она времени будет работать, а не ждать месяцы и годы в надежде что она вдруг закончит счёт если оценка даёт цифры в миллионы лет. Переводя на математику, перед попытками что-то доказать стоит проверить а не доказываете ли "очередную теорему Ферма" с помощью четырёх действий ... Или формулу простого числа из семи действий без высшей математики. Т.е. не сводится ли (или не упрощается, оценками сверху/снизу) вопрос к уже известным. Да, я и сам частенько вместо того чтобы подумать пишу программу и жду что насчитает, но если за час не решила задачу, то может это открытая проблема и ждать не стоит ...
Если мои слова Вас задели, приношу извинения, это получилось не намеренно.