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

[vicvolf]

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

Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

А составляя цепочки разностей Вы можете определить их расположение?

[Yury_rsn]

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

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

Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

А составляя цепочки разностей Вы можете определить их расположение?

Сразу это трудно.
Примерно выглядит это так:
первое число диапазона делится на 2 и на 5,
второе - на 3,
третье на 2 и на 19, и на 29
четвертое - ...
и так до конца разности.
Идет подбор по числам, участвующим в праймориале.
Но ведь есть же еще числа бОльшие, которые в подборе не участвуют, но в реальности являются делителями каждого из чисел ряда. А от них уже зависит реальное нахождение диапазона в пределах праймориала.

-- 08.04.2021, 01:49 --

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

Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

53# _ 94 _ 106 _
59# _ 106 _ 118 _
Второй столбец - это максимумы по стыкам, а третий - максимумы Якобсталя.

Максимумы Якобсталя не так просто подбором выстраивать.
Поэтому, наверное, и не получается.

[Dmitriy40]

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

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

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

-- 08.04.2021, 01:37 --

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

Написал заново и запустил, пока считает, по $29\#$ числа правильные.

Нашлись $31\#: 58/74959204291$ и $37\#: 66/187219155593$. Первый на границе предыдущих праймориалов, второй новый и не равен разности.

-- 08.04.2021, 01:54 --

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

первое число диапазона делится на 2 и на 5,

Вы в этом уверены? Потому что если число $p+1$ (первое число внутри интервала) делится на 5, то и число $p+106$ (якобы правая граница интервала 106) тоже делится на 5 и не может быть правой границей интервала ибо обе границы должны быть взаимно простыми с $53\#$.

[Dmitriy40]

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

Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

А чем Вам не нравится интервал $(24142515499361514223 \ldots 24142515499361514223+106)$ из http://oeis.org/A048670/a048670.txt ? Он именно в $53\#$. Хотя и не наименьший, есть парный ему $(8446642977828530401 \ldots 8446642977828530401+106)$ в том же $53\#$.

[vorvalm]

Я извиняюсь за $d=106$. Нашел ошибку.
Дело в том, что я обычно составлял цепочки
не используя натуральные числа из $p\#$,
а зная начальные числа разностей поиск цепочек
не представляет больших трудностей.

[vorvalm]

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

Есть ли доказательство - "не превосходит $4p_{r+1}$"?
Или это пока только наблюдения в некоторых частных случаях?

Этот вопрос требует особого рассмотрения в отдельной дискуссионной теме.

[Yury_rsn]

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

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

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

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

Ага, буду иметь в виду.

Цитата:

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

первое число диапазона делится на 2 и на 5,

Вы в этом уверены? Потому что если число $p+1$ (первое число внутри интервала) делится на 5, то и число $p+106$ (якобы правая граница интервала 106) тоже делится на 5 и не может быть правой границей интервала ибо обе границы должны быть взаимно простыми с $53\#$.

Я, конечно, эти числа написал наугад.
Если надо - можно взять точные числа.

-- 08.04.2021, 16:32 --

Цитата:

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

Написал заново и запустил, пока считает, по $29\#$ числа правильные.

Нашлись $31\#: 58/74959204291$ и $37\#: 66/187219155593$. Первый на границе предыдущих праймориалов, второй новый и не равен разности.

Круто

А можно вас попросить вернуться к 23# ?
Там было 6 разностей ( и еще зеркальные ), величиной 40 - можно ли их найти (начальные позиции)?

[Dmitriy40]

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

А можно вас попросить вернуться к 23# ?
Там было 6 разностей ( и еще зеркальные ), величиной 40 - можно ли их найти (начальные позиции)?

Уже было:

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

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

Dmitriy40
Просьба.
Среди вычетов ПСВ по модулю $M=23\#$ есть по крайней мере
6 разностей между соседними вычетами, равными $d=40$.
Не могли бы найти первые вычеты этих разностей. Спасибо.

Не знаю почему, но нашлось больше (код на PARI/GP):

? pr=vecprod(primes([1,23]));pp=1;forstep(p=3,pr-1,2, if(gcd(p,pr)>1,next); if(p-pp==40,print1(pp,"  "));pp=p)
20332471  24686821  36068191  65767861  82370089  97689751  125403079  140722741  157324969  187024639  198406009  202760359
time = 1min, 3,868 ms.

Выведено меньшее из двух чисел.

[vicvolf]

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

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

Есть ли доказательство - "не превосходит $4p_{r+1}$"?
Или это пока только наблюдения в некоторых частных случаях?

Этот вопрос требует особого рассмотрения в отдельной дискуссионной теме.

Это довольно грубая оценка. Например, для $p_r=79$ реальное значение максимального расстояния в ПСВ $d=200$, а $4p_{r+1}=4 \cdot 83=332$.

Есть более точная гипотеза, что $d \leq 4p_{r-2}-2$. Конечно для случаев, когда реальное $d>2p_{r-1}$. Я ее проверил на сколько мог. Могу обосновать.

[vorvalm]

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

Это довольно грубая оценка. Например, для $p_r=79$ реальное значение максимального расстояния в ПСВ $d=200$, а $4p_{r+1}=4 \cdot 83=332$.

Я же привел значение $c=d_r/p_{r+1}$ для конца последовательности.
Она равно где-то около 3,5. И если ее продолжить, то $c$ в конце
концов будет равна 4. Промежуточные значения никакой роли здесь не играют.

[vicvolf]

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

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

Это довольно грубая оценка. Например, для $p_r=79$ реальное значение максимального расстояния в ПСВ $d=200$, а $4p_{r+1}=4 \cdot 83=332$.

Я же привел значение $c=d_r/p_{r+1}$ для конца последовательности.
Она равно где-то около 3,5. И если ее продолжить, то $c$ в конце
концов будет равна 4. Промежуточные значения никакой роли здесь не играют.

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

[Dmitriy40]

vorvalm
vicvolf
Вы оба ошибаетесь, отношение $d_{r}_{max}/p_{r+1}$ будет больше $4.0$, в соответствующей теме есть примеры.
Например в $2647\#$ существует интервал минимум $10660$, или в $4.012$ раз больше следующего простого. И тем более ещё больше предыдущих простых, так что ваши обоснования, vicvolf, в чём-то ошибочны. А именно, уже в $p_r=2053, d=8116, 4p_{r-2}-2=8114$ ваше условие нарушено. А начиная с $2693\#$ оно похоже нарушено всегда.

[vicvolf]

Dmitriy40 Ну во-первых большое спасибо. А во вторых:

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

я об оценке максимального расстояния между вычетами ПСВ для сравнительно небольших $p_r$.

Я все-таки приведу обоснование. Один ум хорошо, а больше - лучше

[Dmitriy40]

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

(Широкие строки!)

3#=6:
4/1
2:0  4:1

5#=30:
6/1,23
2:11  4:7  6:1

7#=210:
10/1,199
2:11  4:13  6:23  8:89  10:1

11#=2310:
12/1
14/113,2183
2:17  4:13  6:23  8:89  10:139  12:1  14:113

13#=30030:
16/1
18/2183,5749,9109
22/9439,20569
2:17  4:19  6:23  8:89  10:139  12:199  14:113  16:1  18:2183  20:0  22:9439

17#=510510:
18/1,1129,2183,5749,5989,6803,8479,9109,9353
22/9439,11329,14899,20569,27919,31489
24/39469,89867,101293,127373,171053,185923,186973,195203,207679
26/217127,293357
2:29  4:19  6:23  8:89  10:139  12:199  14:113  16:1333  18:1  20:27827  22:9439  24:39469  26:217127

19#=9699690:
22/1
24/1333,4759,14593,24257,39469,53243
34/60043,9639613
2:29  4:37  6:23  8:89  10:139  12:199  14:113  16:1831  18:1129  20:6803  22:1  24:1333  26:151061  28:323509  30:134297  32:0  34:60043

23#=223092870:
28/1,1333,52399
34/60043,134293,1471453,1884613,2335393,3118813,3363343,7106719
36/8302457,12575753,18717781,19265047
40/20332471,24686821,36068191,65767861,82370089,97689751,125403079,140722741,157324969,187024639,198406009,202760359
2:29  4:37  6:31  8:89  10:139  12:199  14:113  16:1831  18:523  20:6803  22:2311  24:4523  26:36947  28:1  30:151061  32:1683977  34:60043  36:8302457  38:29609561  40:20332471

29#=6469693230:
30/1
34/60043,134293,151057,1471453,1563349,1884613,2170327,2335393,2924443,3118813,3363343
36/3543523,3897083,3911293,4585201,6283513,7340191,8302457,8537611,9018091,9127133,9207511,9722903
40/9740461,12430219,12584731,16424209,20332471,24686821,28320781,33053569,36068191
42/36806389,83437517,102284341,120255931,137122967,175104907,261094997,314780447,399594137,408183577
46/417086647,6052606537
2:41  4:37  6:31  8:89  10:139  12:199  14:113  16:1831  18:523  20:887  22:2311  24:4523  26:6917  28:1333  30:1  32:893957  34:60043  36:3543523  38:29609561  40:9740461  42:36806389  44:955424087  46:417086647

31#=200560490130:
36/1,269473,612263,717053,975217,1046267
40/2734891,4705249
42/6077119
48/7006073,244275413,331709179,475745603
50/689448377,1547979623,3272113853,3371594987,3623074463
54/3734704159,12060385097,20314327219,20391277667,20796901067,22446418937,22894444759,23821672879,24227296279
56/26886024107,27606834257,31622505917,52069452437
58/74959204291,125601285781
2:41  4:37  6:47  8:89  10:139  12:199  14:113  16:1831  18:523  20:887  22:1129  24:4523  26:5531  28:11743  30:90407  32:600791  34:1327  36:1  38:3434819  40:2734891  42:6077119  44:65198603  46:19353493  48:7006073  50:689448377  52:18345640927  54:3734704159  56:26886024107  58:74959204291

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,285068450131,740266380323,746700738923,1299747963653,1768947603893,1782949313941,1873765918163,2440814852941,3374734747523,3478954452443,3941783682301,4046003387221,4979923281803,5546972216581,5637788820803,5651790530851,6120990171091,6674037395821,6680471754421,7135669684613,7149671394661,7233518979151
2:41  4:43  6:47  8:89  10:139  12:199  14:113  16:1831  18:523  20:887  22:1129  24:2179  26:5531  28:3271  30:90407  32:132767  34:1327  36:226027  38:881273  40:1  42:4785829  44:64574849  46:933091  48:7006073  50:48595307  52:266795539  54:132966023  56:2782823513  58:8843039599  60:13081702099  62:58985331407  64:4683065593  66:187219155593

[Yury_rsn]

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

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

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

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

Для примера рассмотрим, как выглядит большой интервал "в цепочках". (Данный вариант метода предложил - vorvalm)

23#. d=40,
Наша задача состоит в том, чтобы используя только простые числа, входящие в праймориал, вычеркнуть максимальное количество последовательных чисел.
Учитываем то, что маленькие простые числа вычеркивают несколько чисел в интервале - образуя так называемую "цепочку".
Рассмотрим на реальном примере, как это примерно выглядит.

Возьмем интервал, который начинается с 20332471. Обозначим А=20332471
По делимости на 2 и на 3 - число А+1 делится на 2, число А+2 делится на 3, А+3 - делится на 2, А+4 - НЕ кратно 2 и 3, А+5 - кратно 2 и 3, А+6 - НЕ кратно 2 и 3, и т.д.
Таким образом, по делимости на 2 и 3 у нас остаются невычеркнутые "окошки" - 4, 6, 10, 12, 16, 18, 22, 24, 28, 30, 34, 36.

Теперь рассмотрим делимость на 5.
Для пятерки существует только два варианта - или занять окошко 4, или окошко 6.
В данном случае, А+4 - кратно 5. Тогда автоматически пятерка вычеркивает окошки 24 и 34, из еще невычеркнутых.

Делимость на 7. Вернемся к ней чуть позже.

Делимость на 11.
Для одиннадцати есть только два варианта - 6 и 10.
Если выберем 6, то одиннадцать вычеркивает еще одно окошко среди оставшихся, - 28. А если выберем 10, то других вариантов не остается. С точки зрения максимизации вычеркивания, выбираем вариант 6.
К этому моменту 5(4, 24, 34), 7(.,.,.), 11(6, 28)

Для 13 остается свободным только А+10.
Получаем 13(10, 36).
К этому моменту 5(4, 24, 34), 7(.,.,.), 11(6, 28), 13(10, 36)
Т.е., у нас уже вычеркнуты 4, 6, 10, 24, 28, 34, 36.
Итого:
4, 6, 10, 12, 16, 18, 22, 24, 28, 30, 34, 36.

Очевидно, что 17, 19, 23 - не смогут вычеркнуть по два окошка.

Теперь можно вернуться к 7.
Оказывается, есть только одно положение, где 7 может вычеркнуть два еще пустых окошка - А+16. Имеем 7(16, 30).

В результате, у нас остались три пустых окна (12, 18, 22), на которых надо разместить три оставшихся простых 17, 19, 23.
Получается шесть вариантов
17(12), 19(18), 23(22)
17(18), 19(12), 23(22)
17(12), 19(22), 23(18)
17(22), 19(18), 23(12)
17(22), 19(12), 23(18)
17(18), 19(22), 23(12)
---
Как видно, расположение всех цепочек никак логически не детерминировано.
"Так получается" - в случае 23#
Чем больше праймориал, тем больше будет возникать вариаций взаимного расположения цепочек. И тем больше будет максимумов Якобсталя, отличающихся от максимумов по стыкам предыдущих праймориалов.

-- 08.04.2021, 22:20 --

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

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

Имеет ли смысл обратиться в OEIS - для уточнения их таблицы?
На форуме, кажется, кто-то присутствует из редакции.

Или там как-то специально указаны НЕ минимальные значения позиций?