Максимальная возможная разность между вычетами ПСВ(p\#)

[vicvolf]

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

vicvolf
Ну раз существуют вон аж сколько контрпримеров, значит Вы очевидно в чём-то ошибаетесь. Например в этом:

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

далее $p_r \cdot p_{r+2}$

Следующий не обязательно будет такой, сюда может влезть $p_{r+1}^2$ если оно вдруг меньше $p_r \cdot p_{r+2}$, а такое вполне бывает хотя бы для $p_r=\{2,5,11,17,19,29,41,43,59,71,79,83\}$.

В данном случае справа я рассматриваю весь ПСВ, а не интервал $(p^2_{r-1},p^2_r)$.

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

Разумеется я согласен что каждое простое объединяет не более двух интервалов, но Вы очевидно ошибаетесь с оценкой их размера.
Чисто теоретически я (пока?) не вижу запрета соседним интервалам быть $d_{max}$ и 4p$d_{max}-2$ (или $d_{max}-4$) и тогда если в их общую границу попадёт следующее простое (в какой-то степени), то максимальный интервал почти удвоится за один шаг. Конечно это очень маловероятно, но запрещено ли? Не уверен.
Отдельно забавно что бывают и одинаковые интервалы слева и справа, но конечно не максимальные, например:
$p_r=3347:\;\;p_r^{372}:60+60=120$
$p_r=6763:\;\;p_r^{11}:54+54=108$

Возьмем $p_r=41$ в этом сдучае $d=74=2 \cdot 37=2p_{r-1}$. Здесь я не ошибаюсь с оценкой?
Предположим дальше даже удвоится расстояние, хотя Вы такого случая не нашли. Тогда получим $d \leq 4p_{r-1}$. Если у Вас $d > 4p_{r-1}$, то ошибка в программе.

[Dmitriy40]

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

Если у Вас $d > 4p_{r-1}$, то ошибка в программе.

Вообще-то в этой теме выше полно примеров даже с $d>4 p_{r+1}$. Какой из них неправилен? Ошибки в программе конечно возможны, но вон выше приводил и числа начала интервалов, и даже список делителей всех чисел внутри интервала. Причём все эти интервалы был честно найдены проверкой каждого числа в них по $\gcd(x,p_r\#)$, очень я сомневаюсь что она постоянно выдаёт ошибки. Плюс список делителей вычислялся просто делением с остатком, оно что, тоже ошибочно? Равенство $p_r\#=1997\#$ было проверено в отдельной программе, она значит тоже ошиблась, несколько раз ...
Покажите ошибку в посчитанных данных — буду искать откуда взялась.

-- 09.04.2021, 14:43 --

Код PARI/GP для проверки интервала $p_r=1997$:

(Длинные строки!)

? a=31636705307173316605161655451699792984859189015341690722215434815152421179915685902795794135882436199503582428247001763806701956465392090044306164043638860353115174141798130676701883881281865842800578012689564482791636912537881114203210142512275046896247864805244230181606222760091925605202826167505422719524165268052087859024533536122035933033193796449598692440626544982151891156226193988184318578672056317660974718507851707814781546179089321839742808865058782847231902094013178086782428515197359861565101401104576983535845963984147205543539866177967404594580250826842360697512544093691482691793960314459995798558529991295987786847772621376715801725473303555192668704131496786063536610870905346422854714017107006429702421438179394966140763110767511946282576195854584548972510035697235225961613626878915021970402047326593335624714112505847;
? prr=vecprod(primes([1,1997])); x=a+2; while(gcd(x,prr)>1, x+=2); print("d=",x-a);
d=8034

Интервал подтверждён. Жду указания на ошибку в этой банальной программе.

[vicvolf]

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

$p_r=2887, d=11448, l=4p_{r-2}-2=11442, d/l=1.000524$
$p_r=2897, d=11518, l=4p_{r-2}-2=11514, d/l=1.000347$
Претензии по несовпадению размеров интервалов не принимаются: алгоритм пытается разместить вычеты максимально плотно и из-за разницы в длине заполняемого промежутка размещение тоже отличается, потому интервалы и не совпадают для каждого конкретного $p_r$. Это не ошибка (а то даже сам перепугался), это особенность моего алгоритма размещения вычетов.
Ещё раз специально повторю: мой алгоритм не выдаёт именно максимально плотное размещение! Лишь некоторое приближение. Потому указанные выше цифры не являются минимальными! Скорее всего минимальные контрпримеры в 1.2-1.5 раза меньше.

Вот здесь Вы писали, при вычислении данной таблицы.

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

Равенство $p_r\#=1997\#$ было проверено в отдельной программе, она значит тоже ошиблась, несколько раз ...
Покажите ошибку в посчитанных данных — буду искать откуда взялась. Жду указания на ошибку в этой банальной программе.

А при чем тут эта программа. Я говорю о вычислениях той таблицы.

[Dmitriy40]

vicvolf
Ещё раз: что неправильного в вычислениях выше? Какие именно вычисления неправильны? Если они подтверждаются прямой проверкой? Ткните пальцем, я прямо сейчас запущу перепроверку, как сделал с $p_r=1997$ выше. Хотя и его достаточно чтобы опровергнуть Ваше заявление что $d>4p_{r+1}$ и тем более $d>4p_{r-2}-2$ не бывает. Оно уже больше. И несколько раз перепроверено. Так в чём же ошибка в вычислениях?

Я писал не что "интервалы не совпадают с конкретными", а что интервалы не максимальны (а число $p_r$ соответственно не минимально). И могут различаться в зависимости от метода размещения вычетов даже для одного и того же $p_r$. Но все интервалы проверены именно вот той банальной программой, которая ищет второй конец интервала именно как $\gcd(x,p_r\#)=1$. И по крайней мере везде где указано начало интервала, там он точно весь проверен. А где не указано — он может быть и больше насчитанного, но вот меньше указанного быть никак не должен.

-- 09.04.2021, 17:45 --

vicvolf
Давайте конкретно: для $p_r=1997$ претензии по вычислению интервала $d=8034$ есть? Нет? А для него $d>4p_{r+1}$ и соответственно и $d>4p_{r-1}$ и $d>4p_{r-2}-2$, что опровергает Ваше заявление что таковых быть не может. Вот же он, есть!

[vicvolf]

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

Но все интервалы проверены именно вот той банальной программой, которая ищет второй конец интервала именно как $\gcd(x,p_r\#)=1$.

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

[Dmitriy40]

vicvolf
PARI/GP с целыми числами работает без погрешностей.
Везде где указано начало интервала, даже без длинного числа в комплекте — он весь проверен (потому что по другому просто не найти его начало, расстановка вычетов даёт конец интервала). Но это занимает время и потому раньше (и сейчас для многих) не делал.
Остальные могут быть и больше насчитанных, в принципе, но выборочная проверка показывает точное совпадение (за исключением самой первой версии таблиц где занизил интервал на 2). Именно поэтому считаю что все интервалы точные (за исключением самых первых таблиц где он занижен).
Но даже одного контрпримера достаточно для опровержения, даже если остальные и ошибочны (а это не так).

Совсем другое дело что для каждого $p_r$ найденный интервал вовсе не максимально возможный, а любой интервал наверняка встречается и заметно раньше найденных $p_r$ (например уже и сам снизил $p_r=2111 \to p_r=1997$ и это наверняка далеко не предел).

[vorvalm]

Dmitriy40
Вопрос. То ваше число, о котором я спрашивал ранее
простое или составное ? (d=10720)

[Dmitriy40]

vorvalm
Число из этого сообщения по утверждению PARI/GP составное, но минимальный простой делитель больше $10^9$ и искать его долго и лень.
Остатки от его деления на большие простые:

1322/2003,  1356/2011,  202/2017,  1029/2027,  1462/2029,  760/2039,  1659/2053,  1714/2063,  1751/2069,  1546/2081,  1830/2083,  215/2087,  2039/2089,  199/2099,  1948/2111,  263/2113,  2079/2129,  1133/2131,  1043/2137,  38/2141,  204/2143,  228/2153,  297/2161,  357/2179,  1240/2203,  502/2207,  532/2213,  573/2221,  628/2237,  650/2239,  1060/2243,  1384/2251,  685/2267,  810/2269,  826/2273,  891/2281,  922/2287,  994/2293,  1041/2297,  1072/2309,  1246/2311,  1419/2333,  2146/2339,  1985/2341,  105/2347,  2025/2351,  1477/2357,  1501/2371,  1620/2377,  1699/2381,  1744/2383,  1809/2389,  1834/2393,  1847/2399,  2397/2411,  1921/2417,  2021/2423,  2091/2437,  2152/2441,  2285/2447,  2374/2459,  2404/2467,  52/2473,  132/2477,  206/2503,  374/2521,  466/2531,  540/2539,  651/2543,  671/2549,  791/2551,  813/2557,  935/2579,  1076/2591,  2535/2593,  2557/2609,  2571/2617,  2605/2621,  2621/2633,  2641/2647

[vicvolf]

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

vicvolf
Совсем другое дело что для каждого $p_r$ найденный интервал вовсе не максимально возможный, а любой интервал наверняка встречается и заметно раньше найденных $p_r$ (например уже и сам снизил $p_r=2111 \to p_r=1997$ и это наверняка далеко не предел).

Но Вы же прошли все взаимно простые с $p_r=1997$ и нашли, что максимальное расстояние равно 8034. Вы хотите сказать, что возможно оно является максимальным для меньших $p_r$?

По моей формуле для $p_r=1997$ получаем максимальный интервал 7948. Значит при больших значениях $p_r$ предположение, что интервал 8034 получается объединением двух интервалов не проходит. Хотелось бы знать, как на самом деле?

Хорошо бы программно определить начало $a$ интервала 8034. А потом взять $p_r=1993$ и найти с полученного начала $a$ значение $b$, где заканчивается первый интервал взаимно простых чисел с $p_r=1993$, затем должно быть одно не взаимно простое число и со значения $b+2$ начаться второй интервал взаимно простых чисел с $ p_r=1993$, который должен закончиться на каком-то числе $c$, затем должно быть опять одно не взаимно простое число и со значения $c+2$ начаться третий интервал взаимно простых чисел с $ p_r=1993$ и.т.д пока мы не выйдем за пределы $a+8034$. Можно это сделать?

[Dmitriy40]

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

Но Вы же прошли все взаимно простые с $p_r=1997$ и нашли, что максимальное расстояние равно 8034. Вы хотите сказать, что возможно оно является максимальным для меньших $p_r$?

Вы опять как-то не так меня поняли.
Я не нашёл что максимальное расстояние для $p_r=1997$ равно $8034$! Я нашёл что в $1997\#$ есть интервал длиной $8034$ (и нашёл где именно). И его оказалось достаточно чтобы убедиться в (не)верности предположений. Но возможно есть и больше, где-то в другом месте праймориала, этого я не знаю. Мой алгоритм не гарантирует нахождение именно максимального интервала, лишь какого-то более-менее близкого к максимальному. И для одного и того же $p_r$ чуть разные модификации алгоритма могут выдать и 4.001х интервал, и 4.6х интервал и 5.09х интервал (а могут и 0.6х интервал). Чтобы найти именно максимальный интервал надо перебрать или все варианты остатков по всем простым или все интервалы в праймориале. И то и другое абсолютно нереально.

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

Можно это сделать?

Можно, я же выложил список из 4017 минимальных простых делителей всех нечётных чисел внутри интервала 8034 (под тегом офтопа), берите и смотрите какие там останутся интервалы слева и справа от $1997, 1993, 1987, \ldots$, они каждое разбивают соответствующий интервал на две части.

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

Значит при больших значениях $p_r$ предположение, что интервал 8034 получается объединением двух интервалов не проходит. Хотелось бы знать, как на самом деле?

Не понимаю вопроса, я же уже дважды на него ответил. Берите выше список минимальных простых делителей чисел внутри интервала и смотрите сколько раз там встретится $1997$, я вижу что ровно один раз, значит оно объединило два меньших интервала в один. Вот так и есть на самом деле. А Ваше предположение получается в чём-то неточно.
Аналогично и для множества меньших простых, как выше уже и сказал:

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

Видно что $1997$ объединило два меньших интервала, как впрочем и каждое из $1901\ldots1993$, т.е. каждое из них появилось лишь только справа или только слева от $1997$, но не одновременно и там и там. Впрочем торможу, очевидно же, что и слева и справа может оказаться только число меньшее половины от $p_r$.

[Dmitriy40]

Хм, оказывается этот интервал $8034$ вовсе не парой представлен в $1997\#$, вон сколько разных позиций нашлось, и кажется все не парные:
107319961180601..925644210291547+8034
107783851201420..127407136736097+8034
111256724920753..565686666093827+8034
112684295905926..264893524071227+8034
117081347469586..279622567246007+8034
118169036061891..357873885769937+8034
120360578688624..304282202768607+8034
127533963980838..502247694518727+8034
135689431042765..457434733243477+8034
144523741659879..925934673269117+8034
217786361570292..129755770672837+8034
244756076165349..668203853051637+8034
277038247318865..582730417712617+8034
297058852603115..111598214793357+8034
316367053071733..624714112505847+8034 - раньше был только этот найден
378586569164617..596122500027307+8034
379801490924159..660153454296077+8036 - ОЙ! этот даже больше!
400829956313638..890302233724747+8034
500115560753559..114173076142387+8034
508030069662647..518032977826697+8034
522129945820980..966397928449767+8034
577989569764153..589455422103907+8034
588691089898945..575113169017077+8034
652768457877120..323290616354467+8034
723356510433499..839493725059397+8034
812945282263222..943608059732057+8034
859404623510546..084649528374767+8034
907538180476681..467848711345747+8034
986824744983785..185237409366927+8034

[vorvalm]

Dmitriy40
Спасибо за остатки.

[vorvalm]

Dmitriy40
Я, кажется, нашел свою ошибку в определении предельного $d_{\max}$ в ПСВ.
Но мне необходим остаток от деления того числа на 2657 $(p_{r+1})$.
Ваш список обрывается на 2647. Я хочу проверить прохождение цепочки кратных $p_{r+1}$
через $d= 10720.$

[vicvolf]

Dmitriy40
Спасибо, за потробные данные о ПСВ$1997\#$.

Получается, что отношение $d/p_{r+1}$ является медленно возрастающей функцией. Это вполне соответствует оценкам:
$a(n) << n^2(\log n)^2$, see Iwaniec
$a(n) \geqslant (2e^\gamma + o(1)) n \log^2 n \log \log \log n / (\log \log n)^2$ , see Pintz.

[Dmitriy40]

(Оффтоп)

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

Но мне необходим

Мне снова ответить одним словом "ОК"? Мало ли что кому необходимо ... Неужели так сложно оформить вопрос вопросом?!
И кстати лишние разбиения строк раздражают, ваше счастье что жаловаться модераторам некому, а сами они в подобные темы без повода похоже стараются не заглядывать.

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

Но мне необходим остаток от деления того числа на 2657 $(p_{r+1})$.
Ваш список обрывается на 2647. Я хочу проверить прохождение цепочки кратных $p_{r+1}$ через $d= 10720.$

1504/2657,  2567/2659,  1003/2663,  1874/2671,  158/2677,  1703/2683,  180/2687,  1711/2689,  1696/2693,  2232/2699,  909/2707,  1280/2711,  739/2713,  2538/2719,  923/2729,  1999/2731,  1944/2741,  1716/2749,  2610/2753,  2691/2767,  2422/2777,  2196/2789,  45/2791,  1150/2797,  1131/2801,  837/2803,  847/2819,  352/2833,  818/2837,  623/2843,  1791/2851,  563/2857,  838/2861,  2361/2879,  2007/2887,  2819/2897,  2472/2903,  923/2909,  2141/2917,  432/2927,  2881/2939,  374/2953,  2890/2957,  543/2963,  124/2969,  2411/2971,  822/2999,

vicvolf
Есть значок $\ll$.
Если есть оценка снизу и она не равна константе и растёт, то я вообще не понимаю смысла во всей этой теме, ведь тогда и Ваше и vorvalm предположение гарантированно когда-то нарушаются. Т.е. Вы знали что оно неверно, но упорно продолжали на нём настаивать (и что у меня ошибки в вычислениях) ... Выходит вот я и нашёл где именно (точнее не дальше чего) они точно нарушаются. Ну и смысл ... Разве что только лишняя проверка что это факт, ну и оценку можно сверить (хотя и в этом смысла тоже нет, сравнение её не улучшит и не опровергнет) ...