2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 42  След.
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 15:32 


01/07/19
244
StaticZero в сообщении #1472732 писал(а):
Yury_rsn, это наименьшая длина последовательностей натуральных чисел, при которой каждая из них содержит взаимно простые с произведением $n$ первых простых чисел.

Спасибо!
Т.е., в реальности это и есть максимальные интервалы между взаимно простыми.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 15:55 
Заслуженный участник
Аватара пользователя


22/06/12
2129
/dev/zero
Yury_rsn, да, окошко длины $j(n)$ ездит по числовой прямой, а в него видно всех, кого нужно.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 15:58 


31/12/10
1555
Последовательность А048670 OEIS

Эта последовательность дает максимальные разности между последовательными
простыми числами в праймориале $p_r\#.$
В каком месте праймориала находятся эти разности не указывается.
Единственной оценкой этого места может служить праймориал $p_{r-1}\#$,
т.е. праймориал рангом ниже, который входит в состав праймориала $p_r\#$
и составляет его начальную часть, в которой не может быть этих разностей.
Это довольно грубая оценка. Более точную оценку максимальной разности
между последовательными простыми числами можно получить исходя
из максимальной разности между вычетами ПСВ (приведенная система вычетов)
по модулю $M(p_r)=p_r\#$. Действительно, если в ПСВ нет какой-то
разности между вычетами, то ее не может быть и в интервале простых чисел ПСВ
$(1<p<p_{r+1}^2).$
Интересно сравнить данные последовательности А048670 и
последовательности максимальных разностей между вычетами ПСВ
по модулю $p_r\#$. До $p_r=31$ эти данные полностью совпадают. Это означает,
что вычеты ПСВ, образующие эти разности, являются простыми числами.
Но при дальнейшем увеличении модуля $M(p_r)=p_r\#$ эти данные начинают
расходиться. Привожу сравнительные данные этих последовательностей,
начиная с модуля $M(23)=23\#$ до модуля $M(97)=97\#$.

$p_r\;\;\;\;\;\;\;\;23,\;29,\;31,\;37,\;41,\;43,\;\;47,\;53,\;\;59,\;\;61,\;\;67,\;\;71,\;\;73,\;\;\;79,\;\;83,\;\;89,\;\;97...$
ПСВ$,\;\;\;\;\;40,\;46,\;58,\;64,\;74,\;90,\;\;92,\;98,\;106,118,126,140,\;144,148,166,\;172,178...$
AO48670 $\;\;\;40,\;46,\;58,\;66,\;74,\;90,100,106,118,132,152,\;174,190,200,\;216,\;234,258...$

По характеру распределения вычетов ПСВ по модулю $M(p_r)$ максимальную
разность между вычетами надо искать в виде $2p.$
Например, совершенно точно установлено, что в любой ПСВ по модулю $M(p_r)$
есть разности между последовательными вычетами, равными $2p_{r-1}$.
Знаменитая разность $127-113=14$ находится в ПСВ по модулю $11\#$.
Поэтому, нижней границей максимальной разности между вычетами ПСВ
по модулю $p_r\#$ можно считать именно $d=2p_{r-1}$, т.е.

$2p_{r-1}\leqslant d_{\max}$

А вот с верхней границей $d_{\max}$ большие проблемы.
Экспериментальные данные для достаточно больших ПСВ показывают,
что максимальная разность в них может превосходить $2p_r.$
Например, в ПСВ по модулю $43\#$ есть разность $90$, в ПСВ по модулю $83\#$
есть разность $166$, но разности $2p_{r+1}$ в ПСВ по модулю $p_r\#$ пока не найдено
и в качестве гипотезы можно считать, что

$2p_{r-1}\leqslant d_{\max}<2p_{r+1}$

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 16:30 


01/07/19
244
vorvalm в сообщении #1472754 писал(а):
Последовательность А048670 OEIS

Эта последовательность дает максимальные разности между последовательными
простыми числами в праймориале $p_r\#.$


Именно простыми, а не взаимно простыми с праймориалом?


Цитата:
..Более точную оценку максимальной разности
между последовательными простыми числами можно получить исходя
из максимальной разности между вычетами ПСВ (приведенная система вычетов)
по модулю $M(p_r)=p_r\#$. Действительно, если в ПСВ нет какой-то
разности между вычетами, то ее не может быть и в интервале простых чисел ПСВ
$(1<p<p_{r+1}^2).$
Интересно сравнить данные последовательности А048670 и
последовательности максимальных разностей между вычетами ПСВ
по модулю $p_r\#$. До $p_r=31$ эти данные полностью совпадают. Это означает,
что вычеты ПСВ, образующие эти разности, являются простыми числами.
Но при дальнейшем увеличении модуля $M(p_r)=p_r\#$ эти данные начинают
расходиться.


Подождите, но ведь из определения функции Якобсталя, которое мы сегодня как раз уточнили, следует, что она и есть интервалы между членами ПСВ?
Или я неправильно понял перевод?

Чем всё-таки отличается ПСВ и А048670 OEIS ?

-- 07.07.2020, 17:32 --

StaticZero в сообщении #1472752 писал(а):
Yury_rsn, да, окошко длины $j(n)$ ездит по числовой прямой, а в него видно всех, кого нужно.


:-) красивая визуализация!

Если можно, подскажите, чем функция Якобсталя отличается от интервалов в ПСВ ?
(см.предыдущие комменты)

-- 07.07.2020, 18:08 --

vorvalm в сообщении #1472754 писал(а):
В каком месте праймориала находятся эти разности не указывается.
Единственной оценкой этого места может служить праймориал $p_{r-1}\#$,
т.е. праймориал рангом ниже, который входит в состав праймориала $p_r\#$
и составляет его начальную часть, в которой не может быть этих разностей.

Хорошая мысль!

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 18:04 


31/12/10
1555
Yury_rsn в сообщении #1472759 писал(а):
Чем всё-таки отличается ПСВ и А048670 OEIS ?

Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.
ПСВ - приведенная система вычетов по модулю М. Если модуль ПСВ равен
праймориалу. то это означает, что вычеты ПСВ взаимно просты и не сравнимы
по модулю.
Чувствуете разницу?
Кстати, максимальные разности между последовательными простыми числами в
праймориале те же, что и в ПСВ по модулю, равному этому праймориалу. а вот
разности между последовательными вычетами ПСВ другие.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 21:28 
Заслуженный участник


20/08/14
11861
Россия, Москва
vorvalm в сообщении #1472770 писал(а):
Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.
Это не так:
Dmitriy40 в сообщении #1472690 писал(а):
Yury_rsn в сообщении #1472687 писал(а):
И по их краям образуются простые числа.
Не везде, $2183$ и $2183+18$ оба не простые. Как и $39469$ с $39469+24$, и $217127$ с $217127+26$, и т.д.
Остальные мне просто лень проверять, допускаю что и там полно не простых границ.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 21:37 


01/07/19
244
vorvalm в сообщении #1472770 писал(а):
Yury_rsn в сообщении #1472759 писал(а):
Чем всё-таки отличается ПСВ и А048670 OEIS ?

Совершенно очевидно. что АО48670 OEIS представляет максимальные разности
между последовательными простыми числами в последовательных праймориалах.
ПСВ - приведенная система вычетов по модулю М. Если модуль ПСВ равен
праймориалу. то это означает, что вычеты ПСВ взаимно просты и не сравнимы
по модулю.
Чувствуете разницу?

Если можно, на примере.
Вот фрагмент последовательности из середины ПСВ по праймориалу 7.
... 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
121, 127, 131, 137, 139, 143, 149 ...
Если я правильно понимаю, то разности 121-113 и 127-121, например, относятся к ПСВ по праймориалу 7.
А разность 127-113 - это разность между последовательными простыми в данном праймориале?
Так?

Если так, то вполне понятна фраза:
Цитата:
Кстати, максимальные разности между последовательными простыми числами в
праймориале те же, что и в ПСВ по модулю, равному этому праймориалу. а вот
разности между последовательными вычетами ПСВ другие.


Но, мне кажется, что определение функции Якобсталя говорит о том, что берутся во внимание только разности между вычетами, даже если они и не простые.
Т.е., именно 121-113 и 127-121

-- 07.07.2020, 23:11 --

Dmitriy40 сообщении #1472690 писал(а):
[Не везде, $2183$ и $2183+18$ оба не простые. Как и $39469$ с $39469+24$, и $217127$ с $217127+26$, и т.д.
Остальные мне просто лень проверять, допускаю что и там полно не простых границ.


Я, наверное, не совсем четко выразился.
Цитата:
А на диапазоне от 169 до 196 (длина 27) - максимум не превышает 22, да и то, этот максимум улетел за девять тысяч (13#: 16/1, 18/2183, 22/9439). А именно в этом месте реальные интервалы гораздо меньше. И по их краям образуются простые числа.

Имел в виду, что если максимальный отрезок, длиной 22 (функция Якобсталя для данного праймориала),
был бы расположен в пределах диапазона от 169 до 196, то на его краях обязательно были бы простые числа.

Ведь это же максимальное количество идущих подряд чисел, каждое из которых не взаимно просто с 13#
Но на отрезке вокруг квадрата 13 не может быть составных чисел, которые не делятся на 2,3,5,...11,13, но делятся на какие-то другие небольшие простые числа.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.07.2020, 22:43 


01/07/19
244
да.
правильнее было бы взять интервал 144-169, а не 169-196.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.07.2020, 12:08 


01/07/19
244
Dmitriy40 в сообщении #1472614 писал(а):
И первый интервал равен следующему простому минус 1 (это кстати легко доказать), а не удвоенному предыдущему.

Прозевал раньше это замечание.
Вы правы, спасибо.
---
Я к вопросу гипотезы Лежандра пришел совсем из другой задачи, но потом увидел, что эту идею уже раньше описал Евгений Колесников.
http://blogs.it-claim.ru/ekolesnikov/fi ... doklad.pdf

Однако у него там ошибка - он предположил, что максимальные интервалы на ПСВ по праймориалам, равны вот этому первому интервалу. (".. первый интервал равен следующему простому минус 1" ).
Мне кажется, что те закономерности, которые нашел Дмитрий
(что большие интервалы начинают появляться очень далеко, и что они постоянно возрастают при движении вправо)
- дают надежду доказать, что для отрезков, не превышающих квадрата праймориала, максимальная длина меньше, чем даже "..первый интервал, равный следующему простому минус 1"

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.07.2020, 13:32 
Заслуженный участник


20/08/14
11861
Россия, Москва
Yury_rsn в сообщении #1472858 писал(а):
- дают надежду доказать, что для отрезков, не превышающих квадрата праймориала, максимальная длина меньше, чем даже "..первый интервал, равный следующему простому минус 1"
Что Вы подразумеваете под "квадратом праймориала"? Например для $23\#$ это будет $23^2$ или $(23\#)^2$? Если второе, то это очевидно и легко доказывается (потому что все возможные длины встретятся не далее $23\#+23$ для $23\#$ и потом будут лишь повторяться), если первое то это легко проверить хоть до миллионных праймориалов (которые, праймориалы, тогда вообще ни при чём).

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.07.2020, 15:38 


01/07/19
244
Dmitriy40 в сообщении #1472868 писал(а):
Yury_rsn в сообщении #1472858 писал(а):
- дают надежду доказать, что для отрезков, не превышающих квадрата праймориала, максимальная длина меньше, чем даже "..первый интервал, равный следующему простому минус 1"
Что Вы подразумеваете под "квадратом праймориала"? Например для $23\#$ это будет $23^2$ или $(23\#)^2$? Если второе, то это очевидно и легко доказывается (потому что все возможные длины встретятся не далее $23\#+23$ для $23\#$ и потом будут лишь повторяться), если первое то это легко проверить хоть до миллионных праймориалов (которые, праймориалы, тогда вообще ни при чём).

Спасибо за уточнение. Тяжело постоянно следить за сокращенными фразами. И они постоянно норовят оказаться двусмысленными :-)

Я имел в виду первый случай - $23^2$.
Функция Якобсталя - это длина самого большого интервала между соседними взаимно простыми числами (т.е., между соседними вычетами по ПСВ данного праймориала).
Например, для 23# самый большой интервал возникает только после числа 20332471 (функция Якобсталя равна 40).

И это означает, что больше нигде, на всем протяжении ряда от 1 и до 23#, разность между соседними вычетами не превышает 40.
Хоть между 20332471 и 20332511, хоть между $22^2$ и $23^2$.
---
Но нас, в конце концов, интересует - какие максимальные интервалы между взаимно простыми с p# возможны именно на интервалах от $(p-1)^2$ до $p^2$

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение08.07.2020, 21:14 


01/07/19
244
Dmitriy40 в сообщении #1472614 писал(а):
Код:
11#: 12/1, 14/113
13#: 16/1, 18/2183, 22/9439
17#: 18/1, 22/9439, 24/39469, 26/217127
19#: 22/1, 24/1333, 34/60043 — заметьте какое интересное исключение здесь: и короче, и нет интервала 26, и интервал 24 обнаружен сильно раньше
23#: 28/1, 34/60043, 36/8302457, 40/20332471
29#: 30/1, 34/60043, 36/3543523, 40/9740461, 42/36806389, 46/417086647 — а здесь интервалы 36,40 обнаружены сильно раньше предыдущего случая
31#: 36/1, 40/2734891, 42/6077119, 48/7006073, 50/689448377, 54/3734704159, 56/26886024107, 58/125601285782 — и опять интервалы на других числах
37#: 40/1, 46/933091, 48/7006073, 50/48595307, 54/132966023, 56/2782823513, 64/4683065593, 66/8720486098464

Смотрите:
11#: 12/1, 14/113 - в районе интервала 100-121 самый большой отрезок НЕвзаимнопростых с 11# - длиной 14, а внутри самого интервала только часть, длиной 8.
Т.е., внутри интервала 100-121, как минимум, $21/8$ $\sim$ 2 простых числа.

13#: 16/1, 18/2183, 22/9439 - внутри интервала 144-169 несколько отрезков НЕвзаимнопростых с 13# - длиной по 5.
Т.е., внутри интервала 144-169, как минимум, $25/5$ $\sim$ 5 простых чисел.

И т.д.

-- 08.07.2020, 22:54 --

17#: 18/1, 22/9439, 24/39469, 26/217127 - а в реальности в районе интервала 256-289 самый большой отрезок НЕвзаимнопростых с 17# - отрезок длиной 9, а внутри самого интервала только часть, длиной 6.
Т.е., внутри интервала 256-289, как минимум, $33/6$ $\sim$ 5 простых чисел.

19#: 22/1, 24/1333, 34/60043 - а в реальности внутри интервала 324-361 самый большой отрезок НЕвзаимнопростых с 19# - отрезок длиной 9 (338 339 340 341 342 343 344 345 346).
Т.е., внутри интервала 324-361, как минимум, $37/9$ $\sim$ 4 простых чисел.
Хотя на самом деле их, конечно, больше.

...

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение17.02.2021, 14:27 


01/07/19
244
Удивительное дело, нигде в русскоязычных ресурсах не удалось найти ни одной статьи про функцию Якобсталя.
При том, что в англоязычном инете появляются работы на эту тему от самых известных авторов в самое последнее время.

Возникла идея, не знаю, приветствуется ли это на форуме, - попытаться сообща разобраться в одной из статей.
"An upper bound on Jacobsthal’s function" https://www.researchgate.net/publicatio ... s_function

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

В начале статьи есть одно неясное место.
Авторы пишут "оценки (других авторов) довольно слабые: в то время как из расчета Хагедорна имеем $h (49) = 742$, эти оценки дают $h (49) <1015$ и $h (49) <1040$ соответственно. Таким образом, мы относительно мало знаем о явном поведении $h (k)$ для k больше 49."

Но дальше они пишут свою формулу, и к ней такой комментарий:
"В этой статье мы устраняем этот пробел, используя новый вычислительный метод для вычисления явных верхних оценок $h (k)$.
Этот метод дает гораздо более строгие оценки, чем те, которые были даны Канольдом и Стивенсом; например, этот метод дает оценку $h (49)$, которая менее чем в 3 раза превышает истинное значение $h (49)$.
...
Мы использовали этот метод для вычисления верхних границ $h (k)$ для k от 50 до 10 000: для всех k в этом диапазоне мы находим $ h(k)< 0,27749612254\cdot k^2 \cdot \log(k) $
граница на сотни порядков сильнее, чем у Канольда и Стивенса в этом диапазоне."

Что это значит - "менее чем в 3 раза превышает истинное значение"?
И, действительно, при подставлении 49 в последнюю формулу получаем число, намного бОльшее, чем 742. Т.е., - 2592,996. :o

Да, а теорема красивая :-)
"Theorem 2.1. Let d and n be two coprime squarefree integers. Then for any
arithmetic sequence
$b + d, b + 2d, . . .$
there necessarily exists a corresponding sequence of consecutive integers
$cb + 1, cb + 2, . . .$
such that
$GCD(cb + x,n) = GCD(b + xd,n)$ for all x "

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение20.02.2021, 09:08 


23/01/07
3497
Новосибирск
Yury_rsn
Рассматривая интересующие Вас интервалы, надо иметь в виду то, что при переходе с одного примориала на следующий ($p_r\#$), Вы "тиражируете" эти интервалы $p_r$ раз.

 Профиль  
                  
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение22.02.2021, 17:17 


01/07/19
244
Батороев в сообщении #1505795 писал(а):
Yury_rsn
Рассматривая интересующие Вас интервалы, надо иметь в виду то, что при переходе с одного примориала на следующий ($p_r\#$), Вы "тиражируете" эти интервалы $p_r$ раз.

Тиражирование происходит, да.
Но интервалы при каждом переходе удлиняются за счет того, что новое число $p_r$ попадает в "пустую" ячейку между соседними интервалами.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 624 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 42  След.

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group