2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 26, 27, 28, 29, 30, 31, 32 ... 42  След.
 
 Re: Максимальные интервалы между взаимно простыми числами
Сообщение31.05.2021, 00:44 


01/07/19
244
Dmitriy40 в сообщении #1520564 писал(а):
Только не забывайте что A,B должны быть нечётными, чтобы между ними можно было идти с шагом 2. Ну и в pr надо будет другое число подставить если будете считать другие примориалы.

Ага, понятно.
Спасибо.

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


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


Можно уточнить, пожалуйста.
Там у вас под тегом выписаны некоторые интервалы для разных праймориалов и для разной длины d.
Возьмем для 37#

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

Меня интересует количество интервалов в зависимости от их длины.
К примеру, для d=48 - 2 шт.,
или для d=54 - 11шт.,
или для d=66 - 24 шт.

Можно уточнить - это ведь найдены не все возможные интервалы для соответствующих d?
Если не все, то по какому принципу они отобраны?

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


01/07/19
244
Yury_rsn в сообщении #1522401 писал(а):
[quote="Dmitriy40 в [url=http://dxdy.ru/post1513500.html#p1513500] найдены ведь не все возможные интервалы для соответствующих d?

64/4683065593,151152153883


Для d=64 есть, как минимум, 24 интервала:
4683065593 635250212803 1107537818593 1177627778533 1228492952893 1505651894953 2294391886993 2437219822243 2729461782253 3283411078153 3661398297763 4058610302953 4098805818313 4133685903553 4542101050693 4651853043043 4686733128283 5570782274263 5715414351853 6544349859253 6940126310323 6976441949683 7229923948453 7269585980863

И еще 24 - "зеркальных" к ним.

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


20/08/14
11002
Россия, Москва
Выводились позиции текущего максимума.

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


01/07/19
244
Вопрос по поводу количества максимальных интервалов в праймориалах.

В статье ".. concepts for the computation of Jacobsthal’s function", авторы Mario Ziller and John F. Morack, есть такая фраза:

"An initial illustration of the results is outlined in figure 1. We graph the values
of h(n) and the number of sequences of length w(n). This number considerably varies in a non-obvious manner."

Гугл-переводчик:
"Первоначальная иллюстрация результатов представлена ​​на рисунке 1. Мы графически отображаем значения h (n) и количество последовательностей длины w (n). Это число значительно различается неочевидным образом."
---
И там дальше дана табличка, где приведены данные, которые нам Дмитрий вычислял - про количество интервалов, длины d, для каждого праймориала.
Только мы тогда дошли лишь до 37#. А там вычислено гораздо дальше.

Эта статья упоминается на http://oeis.org/A048670 - последняя ссылка перед разделом FORMULA.
Прямая ссылка - https://arxiv.org/abs/1611.03310

Таблица в статье находится на 23 странице, в разделе 3.1 Calculated data
Последний столбец - n_seq

Интересуют эти числа (если это они) - количество максимальных интервалов (Якобсталя) для каждого праймориала.
Вопрос - есть какой-то алгоритм их вычисления, или они найдены с помощью простого перебора ?

В oeis этих чисел (n_seq) - нет.

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


20/08/14
11002
Россия, Москва
Разве не вся статья как они считали в том числе и эти числа?

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


01/07/19
244
Увы, с английским напряжно. А тем более английский математический.

Если можно, подскажите, в каком разделе описан расчет по этим числам.

И если совсем нетрудно, плиз, подскажите - это и есть те самые числа, которые меня интересуют? - количество интервалов длины d для каждого праймориала?

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


20/08/14
11002
Россия, Москва
Я не вникал, там по моему все разделы как раз про расчёт, ну разве что кроме 2.5 про распараллеливание. Хотя кажется там весь раздел 2 про оптимизацию простого перебора.
То или не то не знаю, они считали количество количество интервалов максимальной длины $\omega(n)$. $d$ это или не $d$ — Вам решать.

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


01/07/19
244
Dmitriy40 в сообщении #1537448 писал(а):
Я не вникал, там по моему все разделы как раз про расчёт, ну разве что кроме 2.5 про распараллеливание. Хотя кажется там весь раздел 2 про оптимизацию простого перебора.
То или не то не знаю, они считали количество количество интервалов максимальной длины $\omega(n)$. $d$ это или не $d$ — Вам решать.

Ок Предположим, что это они и есть.
Тогда пойдем дальше.
Я рассчитал по данным Гербича таблицы цепочек до n=40. Т.е., до 173#.

    Напомню:
    Цепочки - это термин из поста vorvalm - post1511021.html#p1511021
    Таблица цепочек - описано в post1517466.html#p1517466

    Цепочка - это два и больше чисел в одной строке таблиц.
    Если в строке встречается только одно число - будем называть это "свободной единицей"
    Согласно идеи vorvalm (post1511021.html#p1511021), количество интервалов для данного праймориала зависит от числа свободных единиц.

В post1517825.html#p1517825 было показано, что возможно в пределах одного праймориала существование нескольких вариантов расположения цепочек.
Для 37# имеются два несовпадающих варианта.

Поскольку у Гербича в https://oeis.org/A048670/a048670.txt указаны только по одному представителю для каждого праймориала, проверить напрямую - сколько существует разных интервалов в праймориале мы не можем.
Но с помощью таблицы из вышеприведенной статьи, есть возможность сделать предположения на сей счет.

Вот данные из статьи:

n _ pn _ h(n) _ n_seq

2 _ 3 _ 4 _ 1
3 _ 5 _ 6 _ 2
4 _ 7 _ 10 _ 2
5 _ 11 _ 14 _ 2
6 _ 13 _ 22 _ 2
7 _ 17 _ 26 _ 2
8 _ 19 _ 34 _ 2
9 _ 23 _ 40 _ 12
10 _ 29 _ 46 _ 2
11 _ 31 _ 58 _ 2
12 _ 37 _ 66 _ 24
13 _ 41 _ 74 _ 2
14 _ 43 _ 90 _ 48
15 _ 47 _ 100 _ 24
16 _ 53 _ 106 _ 240
17 _ 59 _ 118 _ 60
18 _ 61 _ 132 _ 12
19 _ 67 _ 152 _ 144
20 _ 71 _ 174 _ 52
21 _ 73 _ 190 _ 24
22 _ 79 _ 200 _ 144
23 _ 83 _ 216 _ 16
24 _ 89 _ 234 _ 16
25 _ 97 _ 258 _ 4
26 _ 101 _ 264 _ 40
27 _ 103 _ 282 _ 4
28 _ 107 _ 300 _ 24
29 _ 109 _ 312 _ 204
30 _ 113 _ 330 _ 48
31 _ 127 _ 354 _ 2
32 _ 131 _ 378 _ 2
33 _ 137 _ 388 _ 8
34 _ 139 _ 414 _ 22
35 _ 149 _ 432 _ 4
36 _ 151 _ 450 _ 18
37 _ 157 _ 476 _ 4
38 _ 163 _ 492 _ 28
39 _ 167 _ 510 _ 4
40 _ 173 _ 538 _ 4

-- 02.11.2021, 23:30 --

Как известно, интервалы на границах праймориалов - симметричны.
Например, post1518061.html#p1518061 (верхняя таблица).
Поэтому для них "прямые" и зеркальные интервалы совпадают.
Две свободные единицы соответствуют двум максимальным интервалам на одном праймориале.

Все остальные интервалы не симметричны. И если в таком интервале имеются две свободные единицы, то кроме двух прямых, имеются обязательно два зеркальных интервала.

Если три свободные единицы - то будет "три факториал" прямых, и столько же зеркальных. Итого - 12 штук.
Как например, для 23#

Для 37# - картина другая. Есть два разных варианта расположения цепочек, и в обоих случаях, имеются по три свободные единицы.
Таким образом, всего для 37# существует 24 интервала, длиной 66

-- 02.11.2021, 23:37 --

А теперь добавим две колонки в таблицу, вычисленные по данным Гербича.

n _ pn _ h(n) _ n_seq _ _ Св.ед _ nseq__

3 _ 5 _ 6 _ 2 _ _ 2 _ 2
4 _ 7 _ 10 _ 2 _ _ 2 _ 2
5 _ 11 _ 14 _ 2 _ _ 2 _ 2
6 _ 13 _ 22 _ 2 _ _ 2 _ 2
7 _ 17 _ 26 _ 2 _ _ 2 _ 2
8 _ 19 _ 34 _ 2 _ _ 2 _ 2
9 _ 23 _ 40 _ 12 _ _ 3 _ 12
10 _ 29 _ 46 _ 2 _ _ 2 _ 2
11 _ 31 _ 58 _ 2 _ _ 2 _ 2
12 _ 37 _ 66 _ 24 _ _ 3+3 _ 24
13 _ 41 _ 74 _ 2 _ _ 2 _ 2
14 _ 43 _ 90 _ 48 _ _ 4 _ 48
15 _ 47 _ 100 _ 24 _ _ 3 _ 12
16 _ 53 _ 106 _ 240 _ _ 4 _ 48
17 _ 59 _ 118 _ 60 _ _ 3 _ 12
18 _ 61 _ 132 _ 12 _ _ 3 _ 12
19 _ 67 _ 152 _ 144 _ _ 3 _ 12
20 _ 71 _ 174 _ 52 _ _ 4 _ 48
21 _ 73 _ 190 _ 24 _ _ 3 _ 12
22 _ 79 _ 200 _ 144 _ _ 3 _ 12
23 _ 83 _ 216 _ 16 _ _ 3 _ 12
24 _ 89 _ 234 _ 16 _ _ 3 _ 12
25 _ 97 _ 258 _ 4 _ _ 2 _ 4
26 _ 101 _ 264 _ 40 _ _ 2 _ 4
27 _ 103 _ 282 _ 4 _ _ 0 _ 2
28 _ 107 _ 300 _ 24 _ _ 2 _ 4
29 _ 109 _ 312 _ 204 _ _ 3 _ 12
30 _ 113 _ 330 _ 48 _ _ 3 _ 12
31 _ 127 _ 354 _ 2 _ _ 1 _ 2
32 _ 131 _ 378 _ 2 _ _ 1 _ 2
33 _ 137 _ 388 _ 8 _ _ 2 _ 4
34 _ 139 _ 414 _ 22 _ _ 2 _ 4
35 _ 149 _ 432 _ 4 _ _ 2 _ 4
36 _ 151 _ 450 _ 18 _ _ 1 _ 2
37 _ 157 _ 476 _ 4 _ _ 1 _ 2
38 _ 163 _ 492 _ 28 _ _ 1 _ 2
39 _ 167 _ 510 _ 4 _ _ 2 _ 4
40 _ 173 _ 538 _ 4 _ _ 1 _ 2

-- 02.11.2021, 23:45 --

Рассмотрим несколько примеров.

Строка
14 _ 43 _ 90 _ 48 _ _ 4 _ 48

n=14
p=43 (43#)
d=90
И по таблице Циллера общее количество интервалов длиной 90 на этом праймориале равно 48.

Теперь смотрим на таблицу цепочек post1518138.html#p1518138 и видим, что в данном случае имеются 4 свободных единицы.
Следовательно, общее количество интервалов тоже равно 48.
"4 факториал" умножить на 2.

Значит, в случае 43# существует только один вариант расположения цепочек

-- 02.11.2021, 23:54 --

Рассматривая дальнейшие строки мы видим и случаи, когда совпадают посчитанные Циллером количества интервалом, с расчетными значениями, исходя из количества свободных единиц.

Но в то же время, встречаются и такие случаи, когда расчет по свободным единицам дает меньшее количество интервалов, чем в таблице Циллера.

Следовательно, можно выдвинуть гипотезу, что в тех случаях должны еще существовать интервалы, в которых цепочки расположены по-другому.
Например, как в случае 37#

12 _ 37 _ 66 _ 24 _ _ 3+3 _ 24

См. post1518128.html#p1518128

-- 02.11.2021, 23:58 --

Я чуть-чуть приведу в порядок таблицы цепочек в файле электронных таблиц, и пришлю ссылку.
(если кому будет интересно)

Честно говоря, зрелище завораживающее само по себе.

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


01/07/19
244
https://docs.google.com/spreadsheets/d/ ... sp=sharing

Таблицы по каждому праймориалу с n=12 до n=40 расположены на отдельных листах файла электронных таблиц

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


01/07/19
244
Судя по этим данным, "разветвление" цепочек должно возникнуть для праймориалов простых чисел 47, 53, 59, 67, 71, 73, 79, 83, 89, 101, 103, 107, 109, 113, 137, 139, 151, 157, 163, 173.

Но даже для случая 37#, d=66 - видно, что трудно найти закономерность, почему именно так расположились цепочки, что в одном, что в другом случае.

Как могут быть смещены цепочки для других предполагаемых разветвлений трудно предположить.
Слишком много возможных комбинаций. Надо бы создать программу для перебора в этих таблицах, чтобы проверить гипотезу о разветвлениях

Интересно в этой связи обратить внимание, как расположены "свободные единицы" - в каких строках.
Ведь до 43#, d=90 возникли только два несимметричных разновидности (не на границах праймориалов) интервалов - 23#, d=40 и 37#, d=66. В каждом из этих двух случаев, свободными оставались последние три строчки. Т.е., строки 17, 19, 23 и 29, 31, 37, соответственно.
Но для 43#, d=90 - эта закономерность уже нарушилась. В этом случае, кроме трех последних чисел 37, 41, 43, свободным оказалось и число 29. А число 31 занимает в строке цепочку из двух чисел.

Интересно в этой связи обратить внимание, как расположены "свободные единицы" - в каких строках.
Ведь до 43#, d=90 возникли только два несимметричных разновидности (не на границах праймориалов) интервалов - 23#, d=40 и 37#, d=66. В каждом из этих двух случаев, свободными оставались последние три строчки. Т.е., строки 17, 19, 23 и 29, 31, 37, соответственно.
Но для 43#, d=90 - эта закономерность уже нарушилась. В этом случае, кроме трех последних чисел 37, 41, 43, свободным оказалось и число 29. А число 31 занимает в строке цепочку из двух чисел.

Дальше,
для n=15, 47#, d=100 - свободные единицы в 3 последних строках
для n=16, 53#, d=106 - свободные единицы в 4 последних строках
для n=17, 59#, d=118 - свободные единицы в 3 последних строках
для n=18, 61#, d=132 - свободные единицы в 3 последних строках
для n=19, 67#, d=152 - свободные единицы в 3 последних строках
для n=20, 71#, d=174 - свободные единицы опять в 4 последних строках

А вот для n=21, 73#, d=190 - начинаются изменения. Свободные единицы возникают в 3 неожиданных строках - 53, 67, 71.
И в дальнейшем, в следующих праймориалах, единицы тоже возникают без всякой видимой закономерности.
Вплоть до n=27, 103#, d=282 - там единиц нет вовсе! В каждой строке есть цепочка.

И в конце опять повторю:
"Как могут быть смещены цепочки для других предполагаемых разветвлений трудно предположить.
Слишком много возможных комбинаций. Надо бы создать программу для перебора в этих таблицах, чтобы проверить гипотезу о разветвлениях"

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


01/07/19
244
Сорри, увидел сейчас, что два раза повторились абзацы в середине последнего коммента. Но исправить уже не могу.
-
Такое чувство, что в этих возможных "разветвлениях" есть ключ к загадке интервалов Якобсталя.
Где бы найти данные - аналог таблицы Гербича - с начальными числами всех интервалов?
Чтобы можно было построить таблицы цепочек для поиска разветвлений.

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


01/07/19
244
Я всё пытался вспомнить, что мне напоминает эта задача - расставить числа по строкам, чтобы при этом выполнились некоторые условия по столбцам.

Так это ж очень похоже на судоку:
https://sudoku.com/

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


01/07/19
244
https://docs.google.com/spreadsheets/d/ ... sp=sharing

Предлагаю поэкспериментировать в одной из таблиц. Я ее отдельно вынес - по ссылке выше.
n=15, 47#, d=100
Надо скопировать себе в аккаунт, тогда таблица будет доступна для редактирования.

В столбце D, от D4 до D16, находятся числа (оранжевого цвета), с помощью которых можно сдвигать числа в строках.
Например, если в ячейке D4 (строка для p=5) поставить число 1, то пятерки в этой строке займут такие позиции: 1, 8, 11, 18, 21, ... Номера позиций находятся в строке 1, и тоже выделены оранжевым цветом.
Если в этой же ячейке поставить теперь любое из чисел 8, 11, 18, 21, ..., то расположение пятерок не изменится. Они останутся на месте.
Если же мы поставим число 2, то пятерки сместятся - 2, 5, 12, 15, ...

Следовательно, возможно лишь пять различных расположений в строке 5.
Но для наших целей (построение интервала Якобсталя d=100) на самом деле возможно только 4 расположения. Поскольку есть обязательное условие - позиция под номером 33 должна быть обязательно НЕ занятой. Эту позицию пятерка займет, если в ячейку D4 подставить номер 3 (или 10, 13, 20, 23, 30, 33, ...)

Таким же образом можно смещать "движки логарифмической линейки" и в остальных строках. Число нетривиальных смещений равно p-1.

Число в ячейке C2 показывает количество "пустых столбцов" на интервале. Формула подсчитывает количество нулей (пустых столбцов) в строке 3.
Если удалось построить интервал Якобсталя, то в этой ячейке должен появиться нуль.

В столбце A, от A4 до A16, подсчитывается количество соответствующих простых чисел в пределах интервала. Например, в строке пять может быть или 6 или 7 чисел, в зависимости от выбранного расположения движка.

Функция в ячейке A1 - подсчитывает количество свободных единиц в таблице. Т.е., сколько раз встречается число 1 в диапазоне от A4 до A16.

Таким образом, задачу можно сформулировать так:
Найти новый набор чисел в диапазоне D4 - D16, с помощью которого удастся получить 0 в ячейке C2.

Естественно, при условии, что этот новый набор будет нетривиальным - хотя бы в одной из строк "движок" будет смещен относительно той позиции, которая сейчас там задана. (Также, тривиальным будет тот набор, где свободные единицы просто поменяются местами между собой)

И при условии, что столбец под номером 33 будет пустым. Т.е., число в ячейке AN3 будет равно нулю.

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


09/05/12
25179
 !  Yury_rsn, умерьте немного активность, пожалуйста. Не надо превращать тему в блог, дождитесь какой-нибудь реакции от собеседников.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 624 ]  На страницу Пред.  1 ... 26, 27, 28, 29, 30, 31, 32 ... 42  След.

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



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

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


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

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