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

[Dmitriy40]

Вообще-то мне лень скорее расписывать подробно/детально/формально/строго очевидные вещи (даже с теми 9-ю пунктами мороки было слишком). Но пусть так.

PS. Не знаю доводилось ли вам писать документацию/инструкции для конечных пользователей (именно для них, это важно), мне доводилось, и эта ситуация ту очень напоминает: чтобы грамотно и детально и аккуратно расписать самые очевидные вещи (типа не совать кошек в микроволновки) приходится писать целые страницы канцелярита. Тут же вместо канцелярита кучи формул. А так как я пишу не научную статью, то доводить всё и так очевидное до нормальной строгости раздражает. Я по прежнему считаю утверждение (о строгом возрастании функции Якобсталя) тривиальным, как и его доказательство (во всяком случае на уровне 100% работающей идеи), но формальная запись последнего занимает да, вовсе не одну строку. Но хотя бы к счастью и не несколько тысяч утверждений как для строгого доказательства $1+1=2$.

[Yury_rsn]

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

рекурсивно понимается как что на каждом шаге мы применяем один и тот же алгоритм (последовательность действий) к каждому новому полученному объекту (в данном случае списку элементов). Т.е. получили что-то, к нему снова вставляем новое простое на первую свободную позицию, получаем что-то новое и снова повторяем вставку по ровно тем же правилам. Это можно реализовать рекурсивной функцией, а можно циклом, не суть, важно что правила остаются постоянными, одними и теми же, на каждом шаге.
Иногда после такой процедуры мы сразу получаем максимальный интервал (например $1\ldots p_{n+1}$), но это редко и только для небольших примориалов, для остальных же нам придётся неким образом переставить элементы чтобы получить максимальный интервал.
Тут есть тонкость: почему перестановка вообще даёт максимальный интервал, это я не очень понимаю (что именно здесь подразумевается под перестановкой) и комментировать не буду. Точнее понятно что перестановка для максимального интервала точно будет среди этих допустимых перестановок (т.е. она существует), это легко понять по списку минимальных простых делителей которые трансформируются в список остатков по модулям и наоборот, но что они тут утверждают я похоже не до конца понимаю.

Интересная мысль - а что, если поставить обратную задачу?
Якобсталь ищет максимальные интервалы, а какой длины будет минимальный интервал?

Естественно, при условии соблюдения описанного вами выше алгоритма:
Т.е., обязательно берется полная перестановка, из всех чисел праймориала,
и по процедуре "...получили что-то, к нему снова вставляем новое простое на первую свободную позицию, получаем что-то новое и снова повторяем вставку по ровно тем же правилам. " строим интервал, пытаясь при этом получить наименьшую длину интервала".

Я вчера поэкспериментировал для 53#. (Там, где якобсталевский максимум - d=106)

Меньше, чем d=54 не получилось. Правда, сразу два варианта.
Первая строка - модули всех нечетных чисел интервала, вторая - перестановка.

5, 3, 47, 53, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3, 23, 5, 3, 29, 31, 3, 5, 37, 3, 41, 43, 3
5, 3, 47, 53, , , 7, , 11, 13, , 17, 19, , 23, , , 29, 31, , , 37, , 41, 43, 
---
43, 3, 5, 47, 3, 41, 7, 3, 11, 13, 3, 17, 5, 3, 19, 23, 3, 5, 29, 3, 7, 31, 3, 53, 37, 3
43, 3, 5, 47, , 41, 7, , 11, 13, , 17, , , 19, 23, , , 29, , , 31, , 53, 37, 

И тогда, на будущее, можно будет сформулировать более общий вопрос:
Интервалы какой длины задаются всем множеством перестановок данного праймориала?
От минимума до максимума.

Ну, и вообще, на помечтать , - хотелось бы найти закономерность, как можно сопоставить каждую конкретную полную перестановку с длиной получаемого из нее интервала?

[Dmitriy40]

Yury_rsn
Алгоритм "ставим в первую свободную позицию" очень сильно ограничивает набор вариантов. И кстати начиная с какого-то небольшого примориала исключает получение максимального интервала. Соответственно нет оснований полагать что он всегда выдаст и минимально возможный интервал. Но его можно использовать для получения оценки сверху.
И кстати при его использовании перебора и не нужно, ведь в начале числового ряда простые появляются именно в нужном порядке, строго на первом же свободном месте. Так что алгоритм всегда будет выдавать просто начало последовательности простых.

Теперь если брать все возможные варианты.
Понятно что для 3#,5# минимальный интервал совпадает с максимальным — на нём и так не умещаются повторы простых.
Для 7# минимальный интервал уже может быть меньше максимального, например 8 вместо 10: 5,3,7.
Для 11# аналогично, например 12 вместо 14: 3,5,7,3,11.
Для 13# аналогично, например 14 вместо 22: 13,3,5,7,3,11.
Возможно минимальный интервал всегда равен максимальному простому плюс один ...

[Yury_rsn]

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

Yury_rsn
Алгоритм "ставим в первую свободную позицию" очень сильно ограничивает набор вариантов.

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

Опять-таки, это очень легко видно с помощью таблицы. Просто и наглядно

[Dmitriy40]

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

Я тоже так сначала подумал, но потом до меня дошло, что это просто будет другая перестановка.

Я Вас не пойму: т.е. Вы не согласны ни с
"Алгоритм "ставим в первую свободную позицию" очень сильно ограничивает набор вариантов."
ни с
"Так что алгоритм всегда будет выдавать просто начало последовательности простых."
?
Тогда это уже не "следующее простое ставим в первую свободную позицию", а что-то другое. Стоит тогда наверное описать что именно другое, а то непонятно о чём конкретно Вы говорите.

[Yury_rsn]

Dmitriy40
Если можно, гляньте, пжл, как я представляю этот процес.

Цитата:

Изобразил пошаговый процесс построения таблицы по заданной перестановке.
По-моему, очень наглядно.

В двух словах:
Для 53#, d=106 берем одну из перестановок в таблице Зиллера. (Например, 3 7 13 11 5 37 23 41 43 31 29 19 47 53 17)
И последовательно заполняем числами 3, 7, 13, 11, ... остающиеся после каждого шага свободные столбцы.
Первый столбец занимает число 3.
Второй - число 7.
...
Двенадцатый - число 23
...
И так далее.

На первом листе - по шагам, сверху вниз.
https://docs.google.com/spreadsheets/d/ ... p=drivesdk

...
Т.е., порядок чисел в перестановке, слева направо, однозначно определяет конкретный интервал

[Dmitriy40]

Yury_rsn
Ну как бы да, всё же просто.
Но это не обратный алгоритм, поиска минимума, а лишь восстановление делителей (и длины интервала) по имеющейся перестановке.

[Yury_rsn]

Dmitriy40

Цитата:

"]Китайская теорема об остатках восстанавливает число по его остаткам от деления на взаимно простые числа. Это число при этом гарантированно меньше произведения использованных взаимно простых. Список минимальных простых делителей интервала легко преобразуется в список остатков начального числа (левой границы) по всем использованным простым. Это преобразование обратимо (да, и это тоже тривиально/очевидно). Т.е. китайская теорема об остатках гарантированно выдаст интервал с теми же свойствами по делимости на использованные простые что и у исходного.

Кстати, а это ж, наверное, и есть суть идеи Зиллера.
Перестановки однозначно соответствуют интервалу.
Для того, чтобы найти максимальный интервал, надо перебрать все перестановки.
Для 53# из всего лишь 8!, сорок с чем-то тысяч.

А по каждой перестановке строится соответствующие интервалы, и выбираются те, которые с максимальной длиной

-- 07.12.2021, 16:33 --

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

Yury_rsn
Ну как бы да, всё же просто.
Но это не обратный алгоритм, поиска минимума, а лишь восстановление делителей (и длины интервала) по имеющейся перестановке.

Похоже, что максимум, что минимум ищется одинаково - перебором перестановок.
И последующим вычислением длины каждого получающегося интервала.

[Yury_rsn]

Чего-то меня переклинило, видно.
Для 53# количество перестановок не 8!, а 16!
А это уже совсем другие расклады.

[Dmitriy40]

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

Кстати, а это ж, наверное, и есть суть идеи Зиллера.

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

А это уже совсем другие расклады.

И то и другое нет: $54!/16!\approx 10^{58}$, что точно сильно больше отношения месяца (счёт до 251#) к 0.5с (счёт до 53#), отношение $27!/8!\approx 2/7\cdot10^{23}$ тоже значительно больше чем 2.6млн.
Почитайте всё же что-нибудь про скорость роста сложности вычислений.
Суть его/их идей описана не в разделе 1, где лишь используемые термины и функции, а в разделе 2. Грубо говоря, в разделе 1 что они считали, а в разделе 2 как они это считали быстро.

[Yury_rsn]

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

Суть его/их идей описана не в разделе 1, где лишь используемые термины и функции, а в разделе 2.

Спасибо, что наводите фокус - на что обратить внимание. Этого как раз не хватает.

[vorvalm]

Интересный случай. Если в оитервале $d = 100$ ( $ПСВ(47\#)$ начальное число 161813978410349234) конечному числу присвоить

кратность 53, то получим интервал $d = 106$ $ПСВ(53\#)$

[vicvolf]

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

Интересный случай. Если в оитервале $d = 100$ ( $ПСВ(47\#)$ начальное число 161813978410349234)

Как это может быть начальное число интервала $d = 100$ в ПСВ$(47\#)$ быть четное? Четные вычеты уже не существуют в ПСВ$(2\#)$.

[vorvalm]

Я взял это число не из ПСВ, но из последовательности a048670.
Меня удивило то, что интервалы $d=100$ и $d = 106$ имеют
абсолютно одинаковый расклад цепочек простых чисел.

[Yury_rsn]

Ещё одна интересная тема - опровержение гипотезы Якобсталя.
Он предположил, что максимальные интервалы d образуются с помощью самых маленьких простых чисел.
Например, если взять шесть простых 2, 3,5,7,11,13, то функция Якобсталя для их произведения имеет максимальное значение. Если какое-то из этих шести простых заменить на какое-то другое, то d невозможно увеличить.

Якобсталь и предположил, что праймориалы всегда дают максимум.
Но, оказывается, уже при n=24 нашелся контрпример.
Если в наборе простых 2,3,...,89, вместо 67 или 71 взять число 101, то функция Якобсталя увеличивается.

Зиллер в 2019 опубликовал ещё одну статью, где рассчитал данные по этой гипотезе.
Оказалось, что похоже, начиная с некторого числа, вообще выполняется "антигипотеза" Якобсталя. Праймориалы вообще уже не дают максимумов.