Максимальные интервалы между взаимно простыми числами : Математика (общие вопросы) - Страница 21 fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 42  След.
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение07.04.2021, 21:54 


23/02/12
3380
vorvalm в сообщении #1513337 писал(а):
Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

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

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


01/07/19
244
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 _
Второй столбец - это максимумы по стыкам, а третий - максимумы Якобсталя.

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

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


20/08/14
11896
Россия, Москва
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\#$.

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


20/08/14
11896
Россия, Москва
vorvalm в сообщении #1513337 писал(а):
Составляя цепочки к разным разностям, я нахожусь в недоумении
в отношении разности $d=106$
У меня получается эта разность не в $53\#$, а в $59\#$ ? ?

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

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


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

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


31/12/10
1555
Yury_rsn в сообщении #1513043 писал(а):
Есть ли доказательство - "не превосходит $4p_{r+1}$"?
Или это пока только наблюдения в некоторых частных случаях?

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

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


01/07/19
244
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 - можно ли их найти (начальные позиции)?

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


20/08/14
11896
Россия, Москва
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.
Выведено меньшее из двух чисел.

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


23/02/12
3380
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}$. Я ее проверил на сколько мог. Могу обосновать.

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


31/12/10
1555
vicvolf в сообщении #1513461 писал(а):
Это довольно грубая оценка. Например, для $p_r=79$ реальное значение максимального расстояния в ПСВ $d=200$, а $4p_{r+1}=4 \cdot 83=332$.

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

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


23/02/12
3380
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$.

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


20/08/14
11896
Россия, Москва
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\#$ оно похоже нарушено всегда.

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


23/02/12
3380
Dmitriy40 Ну во-первых большое спасибо. А во вторых:
vicvolf в сообщении #1513476 писал(а):
я об оценке максимального расстояния между вычетами ПСВ для сравнительно небольших $p_r$.
Я все-таки приведу обоснование. Один ум хорошо, а больше - лучше :-)

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


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

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


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


01/07/19
244
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 - для уточнения их таблицы?
На форуме, кажется, кто-то присутствует из редакции.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 624 ]  На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 42  След.

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



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

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


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

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