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

vicvolf · 23/02/12 3451

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

А если посмотреть отношение $d/p_{r-2}$ ?
Впрочем ...
...
$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$ не превышает 0,3%.
Я проверял эту формулу при небольших $p_r \leq 113$ и там $d_r <4p_{r-2}-2$ и значительно. Интересно почему?

Dmitriy40 · 20/08/14 12075 Россия, Москва

На самом деле интервалы на 2 больше, я кажется перестраховался и занизил его. Ну и коэффициент будет чуть больше.
Плюс чуть подправив алгоритм добился ещё чуточку более плотной упаковки вычетов.
$p_r=2609, d=10388, l=4p_{r-2}-2=10362, d/l=1.002509$
$p_r=2617, d=10488, l=4p_{r-2}-2=10370, d/l=1.011379$
$p_r=2621, d=10440, l=4p_{r-2}-2=10434, d/l=1.000575$
$p_r=2633, d=10570, l=4p_{r-2}-2=10466, d/l=1.009937$
$p_r=2647, d=10538, l=4p_{r-2}-2=10482, d/l=1.005342$
$p_r=2657, d=10592, l=4p_{r-2}-2=10530, d/l=1.005888$
$p_r=2659, d=10654, l=4p_{r-2}-2=10586, d/l=1.006424$
$p_r=2663, d=10710, l=4p_{r-2}-2=10626, d/l=1.007905$
$p_r=2671, d=10804, l=4p_{r-2}-2=10634, d/l=1.015986$
$p_r=2677, d=10698, l=4p_{r-2}-2=10650, d/l=1.004507$
$p_r=2683, d=10738, l=4p_{r-2}-2=10682, d/l=1.005242$
$p_r=2687, d=10720, l=4p_{r-2}-2=10706, d/l=1.001308$
$p_r=2689, d=2028, l=4p_{r-2}-2=10730, d/l=0.189003$
$p_r=2693, d=10772, l=4p_{r-2}-2=10746, d/l=1.002420$
$p_r=2699, d=10908, l=4p_{r-2}-2=10754, d/l=1.014320$
Так что на 0.3% не надейтесь, реально самое плотное размещение будет ещё на несколько процентов плотнее (например интервал $106$ вместо реальных $53\#$ у меня появляется лишь на $67\#$ , а интервал $926$ вместо реальных $269\#$ лишь на $359\#$ ).
Ну и например как видно ниже для $2647\#$ существует размещение с интервалом $10720$ вместо $10538$ и для него коэффициент будет уже не $1.005342$ , а $1.022706$ .
Так что эти цифирки выше лишь для оценки значения, что оно не сходится к конкретному пределу, а довольно сильно болтается чуть выше $1.0$ . Но насколько именно выше сказать трудно.

-- 08.04.2021, 19:59 --

Заодно и изначальное условие пересчитал:
$p_r=2111, d=8456, 4p_{r+1}=8452, d/p_{r+1}=4.001893$
$p_r=2141, d=8606, 4p_{r+1}=8572, d/p_{r+1}=4.015866$
$p_r=2243, d=9008, 4p_{r+1}=9004, d/p_{r+1}=4.001777$
$p_r=2273, d=9138, 4p_{r+1}=9124, d/p_{r+1}=4.006138$
$p_r=2377, d=9540, 4p_{r+1}=9524, d/p_{r+1}=4.006720$
$p_r=2381, d=9566, 4p_{r+1}=9532, d/p_{r+1}=4.014268$
$p_r=2383, d=9590, 4p_{r+1}=9556, d/p_{r+1}=4.014232$
$p_r=2399, d=9648, 4p_{r+1}=9644, d/p_{r+1}=4.001659$
$p_r=2411, d=9672, 4p_{r+1}=9668, d/p_{r+1}=4.001655$
$p_r=2417, d=9724, 4p_{r+1}=9692, d/p_{r+1}=4.013207$
$p_r=2423, d=9828, 4p_{r+1}=9748, d/p_{r+1}=4.032827$
$p_r=2437, d=9784, 4p_{r+1}=9764, d/p_{r+1}=4.008193$
$p_r=2441, d=9852, 4p_{r+1}=9788, d/p_{r+1}=4.026154$
$p_r=2459, d=9944, 4p_{r+1}=9868, d/p_{r+1}=4.030807$
$p_r=2467, d=9920, 4p_{r+1}=9892, d/p_{r+1}=4.011322$
$p_r=2473, d=9952, 4p_{r+1}=9908, d/p_{r+1}=4.017763$
$p_r=2477, d=10080, 4p_{r+1}=10012, d/p_{r+1}=4.027167$
$p_r=2503, d=10160, 4p_{r+1}=10084, d/p_{r+1}=4.030147$
$p_r=2531, d=10208, 4p_{r+1}=10156, d/p_{r+1}=4.020481$
$p_r=2543, d=10300, 4p_{r+1}=10196, d/p_{r+1}=4.040800$
$p_r=2551, d=10238, 4p_{r+1}=10228, d/p_{r+1}=4.003911$
$p_r=2579, d=10384, 4p_{r+1}=10364, d/p_{r+1}=4.007719$
$p_r=2593, d=10440, 4p_{r+1}=10436, d/p_{r+1}=4.001533$
$p_r=2609, d=10538, 4p_{r+1}=10468, d/p_{r+1}=4.026748$
$p_r=2621, d=10554, 4p_{r+1}=10532, d/p_{r+1}=4.008355$
$p_r=2647, d=10720, 4p_{r+1}=10628, d/p_{r+1}=4.034626$
$p_r=2657, d=10686, 4p_{r+1}=10636, d/p_{r+1}=4.018804$
$p_r=2659, d=10678, 4p_{r+1}=10652, d/p_{r+1}=4.009763$
$p_r=2663, d=10730, 4p_{r+1}=10684, d/p_{r+1}=4.017222$
$p_r=2671, d=10748, 4p_{r+1}=10708, d/p_{r+1}=4.014942$
$p_r=2677, d=10796, 4p_{r+1}=10732, d/p_{r+1}=4.023854$
$p_r=2683, d=10770, 4p_{r+1}=10748, d/p_{r+1}=4.008188$
$p_r=2687, d=10794, 4p_{r+1}=10756, d/p_{r+1}=4.014132$
$p_r=2689, d=10822, 4p_{r+1}=10772, d/p_{r+1}=4.018567$
$p_r=2693, d=10912, 4p_{r+1}=10796, d/p_{r+1}=4.042979$
$p_r=2707, d=10884, 4p_{r+1}=10844, d/p_{r+1}=4.014755$
$p_r=2711, d=10968, 4p_{r+1}=10852, d/p_{r+1}=4.042757$
$p_r=2713, d=10920, 4p_{r+1}=10876, d/p_{r+1}=4.016182$
$p_r=2719, d=10978, 4p_{r+1}=10916, d/p_{r+1}=4.022719$
$p_r=2729, d=11010, 4p_{r+1}=10924, d/p_{r+1}=4.031490$
$p_r=2731, d=10984, 4p_{r+1}=10964, d/p_{r+1}=4.007297$
$p_r=2741, d=11094, 4p_{r+1}=10996, d/p_{r+1}=4.035649$
$p_r=2749, d=11130, 4p_{r+1}=11012, d/p_{r+1}=4.042862$
$p_r=2753, d=11150, 4p_{r+1}=11068, d/p_{r+1}=4.029635$
$p_r=2767, d=11200, 4p_{r+1}=11108, d/p_{r+1}=4.033129$
$p_r=2777, d=11212, 4p_{r+1}=11156, d/p_{r+1}=4.020079$
$p_r=2789, d=11258, 4p_{r+1}=11164, d/p_{r+1}=4.033680$
$p_r=2791, d=11298, 4p_{r+1}=11188, d/p_{r+1}=4.039328$
$p_r=2797, d=11238, 4p_{r+1}=11204, d/p_{r+1}=4.012139$
$p_r=2803, d=11412, 4p_{r+1}=11276, d/p_{r+1}=4.048244$
$p_r=2819, d=11418, 4p_{r+1}=11332, d/p_{r+1}=4.030357$
$p_r=2833, d=11560, 4p_{r+1}=11348, d/p_{r+1}=4.074727$
$p_r=2837, d=11484, 4p_{r+1}=11372, d/p_{r+1}=4.039395$
$p_r=2843, d=11496, 4p_{r+1}=11404, d/p_{r+1}=4.032269$
$p_r=2851, d=11570, 4p_{r+1}=11428, d/p_{r+1}=4.049702$
$p_r=2857, d=11608, 4p_{r+1}=11444, d/p_{r+1}=4.057323$
$p_r=2861, d=11698, 4p_{r+1}=11516, d/p_{r+1}=4.063216$
$p_r=2879, d=11778, 4p_{r+1}=11548, d/p_{r+1}=4.079667$
$p_r=2887, d=11634, 4p_{r+1}=11588, d/p_{r+1}=4.015878$
$p_r=2897, d=11722, 4p_{r+1}=11612, d/p_{r+1}=4.037892$
$p_r=2903, d=11700, 4p_{r+1}=11636, d/p_{r+1}=4.022001$
$p_r=2909, d=11700, 4p_{r+1}=11668, d/p_{r+1}=4.010970$
$p_r=2917, d=11884, 4p_{r+1}=11708, d/p_{r+1}=4.060130$
$p_r=2927, d=11910, 4p_{r+1}=11756, d/p_{r+1}=4.052399$
$p_r=2939, d=11930, 4p_{r+1}=11812, d/p_{r+1}=4.039959$
$p_r=2953, d=11940, 4p_{r+1}=11828, d/p_{r+1}=4.037876$
$p_r=2957, d=11920, 4p_{r+1}=11852, d/p_{r+1}=4.022950$
$p_r=2963, d=11932, 4p_{r+1}=11876, d/p_{r+1}=4.018862$
$p_r=2969, d=12068, 4p_{r+1}=11884, d/p_{r+1}=4.061932$
$p_r=2971, d=12072, 4p_{r+1}=11996, d/p_{r+1}=4.025342$
$p_r=2999, d=12110, 4p_{r+1}=12004, d/p_{r+1}=4.035322$
Тут много пропущенных, но последнее пропущенное $p_r=2801$ , дальше все простые перекрывают 4-х кратное следующее.
Зато как видно отношение заметно выше первоначального.
И на самом деле за счёт неоптимальности размещения алгоритмом оно может быть и ещё выше.

-- 08.04.2021, 20:02 --

Признаком неоптимальности могут служить например случаи уменьшения интервала при увеличении $p_r$ , чего очевидно быть не должно, но это такая особенность алгоритма размещения вычетов.

vicvolf · 23/02/12 3451

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

На самом деле интервалы на 2 больше, я кажется перестраховался и занизил его. Ну и коэффициент будет чуть больше.
Плюс чуть подправив алгоритм добился ещё чуточку более плотной упаковки вычетов.
$p_r=2609, d=10388, l=4p_{r-2}-2=10362, d/l=1.002509$
...
$p_r=2971, d=12072, 4p_{r+1}=11996, d/4p_{r+1}=4.025342$
$p_r=2999, d=12110, 4p_{r+1}=12004, d/4p_{r+1}=4.035322$
Тут много пропущенных, но последнее пропущенное $p_r=2801$ , дальше все простые перекрывают 4-х кратное следующее.
Зато как видно отношение заметно выше первоначального.
И на самом деле за счёт неоптимальности размещения алгоритмом оно может быть и ещё выше.

В последней колонке не поделено на 4.

Цитата:

Признаком неоптимальности могут служить например случаи уменьшения интервала при увеличении $p_r$ , чего очевидно быть не должно, но это такая особенность алгоритма размещения вычетов.

Таким образом, у нас не реальная картина, отличная от QEIS?

Dmitriy40 · 20/08/14 12075 Россия, Москва

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

В последней колонке не поделено на 4.

Всё что нужно поделено. Смотрите первые сообщения данной темы, там речь про коэффициент $4$ и относительно другого простого.
А, понял, это я в формуле слева от "=" ошибся, не убрал 4 из знаменателя, спасибо, поправил.

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

Таким образом, у нас не реальная картина, отличная от QUIS?

Эти интервалы вполне реальные, но не обязательно именно такие, это минимум, реально он может и больше, я не проверял, главное что он не меньше посчитанного. Ну и уж точно числа где встретились интервалы совсем не минимальные. Просто это существующий контрпример к высказанным тут выше гипотезам. Минимальность никто не обещал.

PS. Не надо цитировать всё.

vorvalm · 31/12/10 1555

Dmitriy40
Не могли бы вы привести начальный или конечный вычет
разности $d=10660$ ?

Lia · 20/03/14 12041

!	vicvolf Вы разучились пользоваться кнопкой "Вставка"? Замечание за систематический оверквотинг. vicvolf в сообщении #1513489 писал(а): Дима - это потрясно! За фамильярность тоже. Используйте никнеймы на форуме, пожалуйста, даже если вы соседи.

Dmitriy40 · 20/08/14 12075 Россия, Москва

Ради интереса проверил один интервал, в $2647\#$ именно по найденному смещению действительно в наличии интервал $10720$ , с числа $680797083..403252591$ по число $680797083..403263311$ . Так что в этом конкретном случае интервал очень даже реальный. Надеюсь в остальных тоже.

vorvalm
Могу, но программу уже поправил и интервалы немного изменились (увеличились). Может Вам хватит показанного выше примера про $2647$ ? Я его реально проверил через $\gcd(x,2647\#)$ , он действительный.

(Длинное число спрячу под тег, осторожно!)

vorvalm · 31/12/10 1555

Dmitriy40
Да мне неважно какой интервал. Желательно с наибольшим
отклонением от 4. Спасибо.

Dmitriy40 · 20/08/14 12075 Россия, Москва

vorvalm
Ну если тот выше в $2647\#$ длиной $10720$ почему либо не устраивает, то вот нашёл другой (программа снова как-то подправлена, потому не совпадает с предыдущими):
$p_r=2939, d=12696, 4p_{r+1}=11812, d/p_{r+1}=4.299357$ , $187532833849345..777613006823061+12696$ — проверен, реально такой.

(Длинное число)

-- 09.04.2021, 00:38 --

Запускал предыдущий промежуточный вариант программы в коротких отрезках около $2600\#$ , $3300\#$ , $5000\#$ , $9000\#$ , хотел посмотреть на динамику отношения, так вот оно такое ощущение что растёт. Сначала было около $4.02$ , потом $4.1$ , дальше $4.2$ , а потом и до $4.3$ доросло. С колебаниями, но средний тренд вполне просматривается.
Последний же вариант программы влёгкую выдал например
$p_r=5051, d=23478, 4p_{r+1}=20236, d/p_{r+1}=4.640838$ , $799056846507377..130775199474893+23478$
$p_r=9059, d=45812, 4p_{r+1}=36268, d/p_{r+1}=5.052608$ , $243426204189592..759762385267599+45812$ — отношение точно превысило $5.0$ !

(Очень длинное число)

Так что вовсе оно не стремится к $4$ , это лишь у меня алгоритм недостаточно хорош. Скорее оно медленно, но растёт.

vicvolf
Для этого же числа $p_r=9059$ отношение $d/(4 p_{r-2}-2)=45812/(4\cdot9043-2)=1.2665745$ , уже ну совсем не 0.3%.

vorvalm · 31/12/10 1555

Dmitriy40

Можно только поражаться колоссальным ресурсом вашего ПК,
но вернемся чуть назад. Меня интересует $p_r\#$ , где впервые
появляется $c \geqslant 4.$

Dmitriy40 · 20/08/14 12075 Россия, Москва

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

Меня интересует $p_r\#$ , где впервые
появляется $c \geqslant 4.$

Этого я посчитать не могу:

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

Ещё раз специально повторю: мой алгоритм не выдаёт именно максимально плотное размещение! Лишь некоторое приближение. Потому указанные выше цифры не являются минимальными! Скорее всего минимальные контрпримеры в 1.2-1.5 раза меньше.

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

... реально самое плотное размещение будет ещё на несколько процентов плотнее (например интервал $106$ вместо реальных $53\#$ у меня появляется лишь на $67\#$ , а интервал $926$ вместо реальных $269\#$ лишь на $359\#$ ).

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

Признаком неоптимальности могут служить например случаи уменьшения интервала при увеличении $p_r$ , чего очевидно быть не должно, но это такая особенность алгоритма размещения вычетов.

Для нахождения гарантированно минимального $p_r$ где впервые появляется некий интервал надо перебрать значительную часть от всех вариантов расстановок вычетов, а это порядка $\varphi(p_r\#)$ , что больше $10^{500}$ и абсолютно нереально. Как этот перебор оптимизировать без ухудшения плотности размещения я не знаю.

Единственное в чём я уверен что он появляется точно не дальше этого:
$p_r=1997, d=8034, 4p_{r+1}=7996, d/p_{r+1}=4.019010$ , $316367053071733..624714112505847+8034$

(Снова длинное число)

vicvolf · 23/02/12 3451

Dmitriy40 По идеи $d <4p_{r+1}$ или $d <4p_{r-2}$ . Поясню почему. Вы уже проверяли, что моя гипотеза справедлива и на интервале $(1,p^2_{r+1})$ выполняется $d(p^2_{r+1}) \leq 2p_{r-1}$ . Равенство достигается при $p_r=11$ и $d(169)=14$ . При $p_r>11$ выполняется $d(p^2_{r+1}) < 2p_{r-1}$ .

В ПСВ $p_{r-1}\#$ на интервале $(1,p^2_r)$ находятся только простые числа, поэтому при переходе к ПСВ $p_{r}\#$ никакие вычеты не удаляются и расстояния между вычетами не меняется. По моей гипотезе для него выполняется $d(p^2_{r}) \leq 2p_{r-2}$ .

А вот вне этого интервала могут находиться составные числа, которые могут удаляться, если они кратны $p_r$ . Первым таким числом является граница интервала $p^2_r$ . Следующим удаляемым вычетом будет $p_r \cdot p_{r+1}$ , далее $p_r \cdot p_{r+2}$ и.т.д.

Обратите внимание, на расстояние между удаляемыми вычетами. Так как $p_r+1$ -четно, то вычет $p_r(p_r+1)$ был удален раньше. Так что, если $p_r,p_{r+1}$ - близнецы, то минимальное расстояние между удаляемыми вычетами может быть $(p_{r+1}-p_r)p_r=2p_r>2p_{r-1}$ , т.е. достаточно большое.

Какое же максимальное расстояние между вычетами станет в ПСВ $p_{r}\#$ ? В наибольшем случае объединится максимальное расстояние $2p_{r-1}$ и расстояние немного меньше $2p_{r-1}-2$ , т.е. получим максимальное расстояние $4p_{r-1}-2$ . Таких расстояний в ПСВ $p_{r}\#$ , как минимум два, так имеются симметричные вычеты в ПСВ.

У Вас получается расстояние больше $4p_{r-1}-2$ , т.е. должны объединяться три интервала или более, что быть не может, так как как я показал, большое расстояние между удаляемыми вычетами.

Для примера возьму ПСВ $11\#$ . Оно состоит из вычетов $1,13,......,113,127,...139,149,...,2310$ . Я не выделил симметричные, но это в данном случае не важно. На интервале $(1,121)$ никакие вычеты не удалялись. Удалился вычет кратный $11 -121$ и объединились расстояния $113-121$ и $121-127$ получилось максимальное $d=14$ . Кроме того удалился вычет $11 \cdot 13=143$ и объединились расстояния $139-143$ и $143-149$ и получилось расстояние равное $10$ . Но обратите на каком они находятся расстоянии $113$ и $139$ , $139-113=26>>14$ , поэтому они никак не могут объединиться.

Dmitriy40 · 20/08/14 12075 Россия, Москва

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

Но давайте посмотрим на что делятся все те числа внутри интервала $8034$ из $1997\#$ с отношением $d/(4 p_{r-2}-2)=8034/(4\cdot1987-2)=1.011075$ :

(Много чисел!)

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

Разумеется я согласен что каждое простое объединяет не более двух интервалов, но Вы очевидно ошибаетесь с оценкой их размера.
Чисто теоретически я (пока?) не вижу запрета соседним интервалам быть $d_{max}$ и $d_{max}-2$ (или $d_{max}-4$ ) и тогда если в их общую границу попадёт следующее простое (в какой-то степени), то максимальный интервал почти удвоится за один шаг. ;-)

Конечно это очень маловероятно, но запрещено ли? Не уверен.

-- 09.04.2021, 13:42 --

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

Чисто теоретически я (пока?) не вижу запрета соседним интервалам быть $d_{max}$ и $d_{max}-2$ (или $d_{max}-4$ ) и тогда если в их общую границу попадёт следующее простое (в какой-то степени), то максимальный интервал почти удвоится за один шаг.

Мда, реально такого конечно не наблюдается, нашёл такие (для степени простого указан интервал слева от неё, справа и их сумма, лишь несколько примеров):
$\tiny{p_r=587:\;\;p_r^1:586+6=592;\;\; p_r^{26}:12+94=106}$
$\tiny{p_r=1733:\;\;p_r^1:1732+8=1740;\;\; p_r^{121}:106+50=156}$
$\tiny{p_r=3169:\;\;p_r^1:3168+12=3180;\;\; p_r^{85}:146+4=150;\;\; p_r^{299}:110+30=140}$
$\tiny{p_r=7177:\;\;p_r^1:7176+10=7186;\;\; p_r^{121}:138+52=190;\;\; p_r^{359}:122+28=150}$
Интересно есть ли запрет и насколько сильный ...

Отдельно забавно что бывают и одинаковые интервалы слева и справа, но конечно не максимальные, например:
$p_r=3347:\;\;p_r^{372}:60+60=120$
$p_r=6763:\;\;p_r^{11}:54+54=108$

vorvalm · 31/12/10 1555

Dmitriy40
Я пробовал завести начальное число для d= 10720 в wolframalfa,
но оно не проходит. Мне надо найти остаток от деления этого числа
на 2657. Спасибо.

Dmitriy40 · 20/08/14 12075 Россия, Москва

vorvalm
Пожалуйста.

Научный форум dxdy

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

Кто сейчас на конференции