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

[Yury_rsn]

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

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

В том числе подходит и интервал 2-11

Таких интервалов в ПСВ нет. Есть только интервал 1-$p_{n+1}$. Я указываю границы интервала. В данном случае 1-11.

Вы правы.
Вы указываете внешние границы интервала, а я по инерции - внутренние.
Исходя из записи {a, a+1, a+2, ... a+n}, где и число а, и число a+n делятся на какие-то простые числа из праймориала.
Удобнее так обозначать было, - чтобы не оговаривать каждый раз какие из чисел в этой записи должны делиться на простые из праймориала, а какие не должны.

[vicvolf]

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

Про доказательство же, укажите конкретно какой шаг я якобы не доказал:
1. Среди всех чисел $1\ldots p_n\#$ есть взаимно простые с $p_n\#$.
2. Максимальный интервал между ними назовём $d_n$. Он может быть не один в указанном интервале. Сами числа назовём границами, $p_{a_i} \ldots p_{b_i}, p_{b_i}-p_{a_i}=d_n$.
3. Возьмём любой из этих интервалов и посчитаем минимальные простые делители каждого из чисел внутри интервала (за исключением границ). Они все не более чем $p_n$.
4. Дополним список делителей интервала справа числом $p_{n+1}$.
5. По китайской теореме об остатках восстановим где в интервале $1\ldots p_{n+1}\#$ будет такой интервал, $p_{c_i} \ldots p_{d_i}, p_{d_i}-p_{c_i}=p_{b_i}-p_{a_i}=d_n$, что все его минимальные простые делители совпадут с нашим списком (включая и $p_{d_i}=0\pmod{p_{n+1}}$, но не включая $p_{c_i}$, которое остаётся левой границей интервала).
6. Теперь правое число $p_{d_i}$ уже не взаимно простое с $p_{n+1}\#$ (имеется общий делитель $p_{n+1}$), значит правая граница нового интервала $p_{x_i}$ (взаимно простое с $p_{n+1}\#$ число) сдвинется вправо, $p_{x_i}>p_{d_i}$, а новый интервал строго больше предыдущего $h_i=p_{x_i}-p_{c_i}>p_{d_i}-p_{c_i}=p_{b_i}-p_{a_i}=d_n$.
7. Так как брали любой из максимальных интервалов, то это выполняется для них всех. Но возможно с разными $h_i=p_{x_i}-p_{c_i}>d_n$ для каждого.
8. Максимум из $h_i$ назовём новым максимальным интервалом для $p_{n+1}\#$: $d_{n+1}=\max(h_i)=\max(p_{x_i}-p_{c_i})>d_n$.
9. Этим доказано что при переходе $n \to n+1$ он строго возрастает $d_{n+1}>d_n$.
ЧТД.
Строго доказывать пункты 5 и 6 в части что все $p_{d_i}$ и все $p_{x_i}$ строго меньше $p_{n+1}\#$ мне лень, но это очевидно возможно (хотя бы доказать что $p_{n+1}\#-1$ взаимно простое с $p_{n+1}\#$ и значит ни $p_{d_i}$ ни $p_{x_i}$ не могут сдвинуться правее него).
Строго доказывать в пункте 5 что левая граница останется на месте, т.е. $p_{c_i}\ne0\pmod{p_{n+1}}$ тоже лень, но это и неважно — если она вдруг будет сдвигаться влево (а такое возможно лишь если $d_n=0\pmod{2p_{n+1}}$), то интервал $h_i$ тем более будет больше $d_n$ и надо будет лишь в последующих формулах $p_{c_i}$ заменить на $p_{y_i}<p_{c_i}$ (а сдвинуться левее $1$ она в любом случае не сможет).

В 5 пункте не доказано, что это можно сделать. Как Вы для этого используете теорему об остатках?

Если лень, то доказывать вообще не надо! Но и не надо тогда говорить, что это тривиально.

[Dmitriy40]

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

В 5 пункте не доказано, что это можно сделать. Как Вы для этого используете теорему об остатках?

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

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

Но и не надо тогда говорить, что это тривиально.

А я повторю что оно таки тривиально, потому что фактически сводится к тавтологии: "расширяя интервал заменой границы на новое простое мы тем самым расширяем интервал". Всё остальное — издержки математической формулировки.

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

Посмотрите здесь:

Как забавно вы пользуетесь чужими аргументами против своих утверждений для поддержки аналогичных своих утверждений. Могли бы хоть ради приличия черкануть пару слов что мол "да, согласен, был не прав, ваш пример убедил" ... Без этого создаётся впечатление то ли плагиата/воровства, то ли полного непонимания.

Yury_rsn
Не обращайте внимания: и расположение интервала роли не играет, и к общему виду приводится банальной заменой конкретных цифр на буквы, и индукция при этом появится автоматом (достаточно добавить пару слов про выбор максимума среди всех новых).

[vicvolf]

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

2. Максимальный интервал между ними назовём $d_n$. Он может быть не один в указанном интервале. Сами числа назовём границами, $p_{a_i} \ldots p_{b_i}, p_{b_i}-p_{a_i}=d_n$.
3. Возьмём любой из этих интервалов и посчитаем минимальные простые делители каждого из чисел внутри интервала (за исключением границ). Они все не более чем $p_n$.
4. Дополним список делителей интервала справа числом $p_{n+1}$.
5. По китайской теореме об остатках восстановим где в интервале $1\ldots p_{n+1}\#$ будет такой интервал, $p_{c_i} \ldots p_{d_i}, p_{d_i}-p_{c_i}=p_{b_i}-p_{a_i}=d_n$, что все его минимальные простые делители совпадут с нашим списком (включая и $p_{d_i}=0\pmod{p_{n+1}}$, но не включая $p_{c_i}$, которое остаётся левой границей интервала).

Добавили в интервал справа $p_{n+1}$ в п.4, но почему он остался длиной $d_n$ в п.5?


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

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

Строго доказывать пункты 5 и 6 в части что все $p_{d_i}$ и все $p_{x_i}$ строго меньше $p_{n+1}\#$ мне лень, но это очевидно возможно (хотя бы доказать что $p_{n+1}\#-1$ взаимно простое с $p_{n+1}\#$ и значит ни $p_{d_i}$ ни $p_{x_i}$ не могут сдвинуться правее него).
Строго доказывать в пункте 5 что левая граница останется на месте, т.е. $p_{c_i}\ne0\pmod{p_{n+1}}$ тоже лень, но это и неважно — если она вдруг будет сдвигаться влево (а такое возможно лишь если $d_n=0\pmod{2p_{n+1}}$), то интервал $h_i$ тем более будет больше $d_n$ и надо будет лишь в последующих формулах $p_{c_i}$ заменить на $p_{y_i}<p_{c_i}$ (а сдвинуться левее $1$ она в любом случае не сможет).

Не надо себя больше мучить. Занимайтесь, чем нравится.

-- 04.12.2021, 19:53 --

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

? a=20569; forstep(p=a,a+22,2, print1(factor(p)[1,1],", "))
67, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 59,
? forstep(a=20569,510510-22,30030, forstep(p=a,a+22,2, print1(factor(p)[1,1],", ")); print)
67, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 59,
50599, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 223,
80629, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 80651,
41, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 110681,
140689, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 37,
79, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 170741,
367, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 200771,
230779, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 149,
260809, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 17, \\\\\\\\\\\\\\\\\\\\\\
290839, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 290861,
47, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 19,
350899, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 103,
380929, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 380951,
29, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 113,
440989, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 441011,
17, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 471041, \\\\\\\\\\\\\\\\\\\\\\
19, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 83,

Интервалы с 17 слева и справа должны повторяться каждые 17 строк, исходя из доказательства через арифметическую прогрессию. Я этого не вижу.

[Yury_rsn]

Dmitriy40
подскажите, пожалуйста, в этом тексте речь идет о программистских нюансах (рекурсивные функции), или чисто математических?

В предложении 1.5
(3) Существует перестановка ( $\pi_2, ..., \pi_n$ ) элементов { $p_2 , ..., p_n$ } и набор ( $q_2 , ..., q_n$ )такие,
что последовательность { 1, ..., m } полностью покрывается классами вычетов $q_i$ mod $\pi_i$ когда все $\pi_i$ были рекурсивно присвоены первой свободной позиции $q_i$, соответственно.

[Dmitriy40]

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

Все что тривиально, то либо не доказывается, либо доказывается очень просто в одну строчку,

Повторю:

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

А я повторю что оно таки тривиально, потому что фактически сводится к тавтологии: "расширяя интервал заменой границы на новое простое мы тем самым расширяем интервал". Всё остальное — издержки математической формулировки.

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

Добавили в интервал справа $p_{n+1}$ в п.4, но почему он остался длиной $d_n$ в п.5?

Вот почему:

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

Список минимальных простых делителей интервала легко преобразуется в список остатков начального числа (левой границы) по всем использованным простым. Это преобразование обратимо (да, и это тоже тривиально/очевидно).

Пожалуй поясню: у обоих интервалов одинаковый состав остатков по модулю простых по $p_n$ включительно, потому не изменились и минимальные простые делители всех чисел внутри интервала (но не на границах) и соответственно не изменился размер интервала (не учитывая $p_{n+1}$ на границе). Разумеется таких интервалов всего $p_{n+1}$ штук в $p_{n+1}\#$ с разными правыми границами пробегающими все значения $0\ldots p_{n+1}-1\pmod{p_{n+1}}$ и один из них обязательно будет иметь на правой границе число $p_{d_i}=0=p_{n+1}\pmod{p_{n+1}}$, именно его и используем.

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

Интервалы с 17 слева и справа должны повторяться каждые 17 строк, исходя из доказательства через арифметическую прогрессию. Я этого не вижу.

А я вижу:

(Много цифр)

? forstep(a=20569,3*510510-22,30030, forstep(p=a,a+22,2, print1(factor(p)[1,1],", ")); print)
67, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 59,
50599, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 223,
80629, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 80651,
41, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 110681,
140689, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 37,
79, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 170741,
367, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 200771,
230779, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 149,
260809, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 17,
290839, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 290861,
47, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 19,
350899, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 103,
380929, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 380951,
29, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 113,
440989, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 441011,
17, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 471041,
19, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 83,
531079, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 531101,
561109, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 23,
31, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 591161,
257, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 41,
23, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 651221,
681229, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 681251,
711259, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 211,
719, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 53,
83, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 17,
801349, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 801371,
337, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 29,
53, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 89,
891439, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 19,
577, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 921491,
89, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 101,
17, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 61,
1011559, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 47,
43, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 137,
19, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1071641,
1101649, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1101671,
59, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1131701,
197, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 43,
1191739, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1191761,
61, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1221791,
1069, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 23,
29, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 17,
173, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 757,
23, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1341911,
349, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 823,
1401949, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1401971,
397, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 1432001,
1462009, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 19,
17, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 31,
31, 3, 7, 5, 3, 13, 11, 3, 5, 7, 3, 587,

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

подскажите, пожалуйста, в этом тексте речь идет о программистских нюансах (рекурсивные функции), или чисто математических?

Нет, тут не нюансы программирования, а просто сокращенное математическое выражение: рекурсивно понимается как что на каждом шаге мы применяем один и тот же алгоритм (последовательность действий) к каждому новому полученному объекту (в данном случае списку элементов). Т.е. получили что-то, к нему снова вставляем новое простое на первую свободную позицию, получаем что-то новое и снова повторяем вставку по ровно тем же правилам. Это можно реализовать рекурсивной функцией, а можно циклом, не суть, важно что правила остаются постоянными, одними и теми же, на каждом шаге.
Иногда после такой процедуры мы сразу получаем максимальный интервал (например $1\ldots p_{n+1}$), но это редко и только для небольших примориалов, для остальных же нам придётся неким образом переставить элементы чтобы получить максимальный интервал.
Тут есть тонкость: почему перестановка вообще даёт максимальный интервал, это я не очень понимаю (что именно здесь подразумевается под перестановкой) и комментировать не буду. Точнее понятно что перестановка для максимального интервала точно будет среди этих допустимых перестановок (т.е. она существует), это легко понять по списку минимальных простых делителей которые трансформируются в список остатков по модулям и наоборот, но что они тут утверждают я похоже не до конца понимаю.

-- 04.12.2021, 22:25 --

Yury_rsn
Но это всё не суть, это никак не помогает найти нужную перестановку, это всё служебные определения, Вы в своей таблице занимаетесь тем же самым, только (возможно) в других терминах.

[Yury_rsn]

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

Тут есть тонкость: почему перестановка вообще даёт максимальный интервал, это я не очень понимаю (что именно здесь подразумевается под перестановкой) и комментировать не буду. Точнее понятно что перестановка для максимального интервала точно будет среди этих допустимых перестановок (т.е. она существует), это легко понять по списку минимальных простых делителей которые трансформируются в список остатков по модулям и наоборот, но что они тут утверждают я похоже не до конца понимаю.
Yury_rsn
Но это всё не суть, это никак не помогает найти нужную перестановку, это всё служебные определения, Вы в своей таблице занимаетесь тем же самым, только (возможно) в других терминах.

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

Пример:
Возьмем строку из файла https://arxiv.org/src/1611.03310v2/anc/moduli.txt
n=9, p_n=23, omega(n)=19, n_seq=12
1 12 *___3 5 11 3 13 17 3 7 19 3 23 5 3 11 7 3 5 13 3

А теперь рассмотрим "перестановку" из файла https://arxiv.org/src/1611.03310v2/anc/permutations.txt по тому же праймориалу
n=9, p_n=23, omega(n)=19, n_seq=12
1 12 * ___3 5 11 13 17 7 19 23

Т.е., минимальные делители каждого нечетного числа в интервале Якобсталя (длиной d=40)
3 5 11 3 13 17 3 7 19 3 23 5 3 11 7 3 5 13 3 и перестановка
3 5 11 _ 13 17 _ 7 19 _ 23

Возьмем еще вторые строки для закрепления
2 11 * ___3 5 11 3 13 17 3 7 23 3 19 5 3 11 7 3 5 13 3
2 11 * ___3 5 11 13 17 7 23 19

3 5 11 3 13 17 3 7 23 3 19 5 3 11 7 3 5 13 3
3 5 11 _ 13 17 _ 7 23 _ 19

Логика примерно понятна. Какие-то числа в "перестановках" остаются на месте, а какие-то меняются местами.
Но что это нам дает в плане первичного вычисления интервалов Якобсталя - не совсем ясно.

[Dmitriy40]

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

-- 05.12.2021, 03:25 --

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

Логика примерно понятна. Какие-то числа в "перестановках" остаются на месте, а какие-то меняются местами.

Они не местами меняются, а во второй строке удаляются/пропускаются повторы, но с сохранением порядка. Чем это помогает опять же не представляю, по моему только меньше информации становится (в первой строке она избыточна и вся может быть получена из второй строки). Возможно последовательности из второй строки проще перебирать, там все числа уникальные и соответственно перестановок ровно n! (впрочем в первой тоже, но не так наглядно) ... Но ведь получить из них сразу размер интервала весьма непросто, по моему придётся так или иначе приводить к форме первой строки ... Непонятна цель. Но до раздела 2 цели может и не быть, тут же лишь список определений и свойств для основного (второго) раздела.

[vicvolf]

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

Непонятна цель. Но до раздела 2 цели может и не быть, тут же лишь список определений и свойств для основного (второго) раздела.

Цель работы видна из результатов:
3. Результаты
Алгоритмы, описанные в разделе 2, действуют по-разному в отношении своих вычислительных возможностей.
усилие. Мы вычислили все значения функции h (n), где все задействованные простые числа
может быть представлен в виде одного байта, то есть pn 251. В этих вычислениях мы использовали
несколько алгоритмов, каждый из которых подходит по времени вычислений. Равенство соответствующих
Результаты послужили неявной проверкой правильности реализаций.
Наши данные также согласуются со всеми литературными данными для pn 227 [5].
Для каждого исследованного n мы выполнили исчерпывающий поиск для всех существующих
последовательности максимальной длины при поиске w (n). Насколько нам известно, это
никогда раньше не делалось. Мы предоставляем эти данные во вспомогательных файлах.

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

[Yury_rsn]

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

Они не местами меняются, а во второй строке удаляются/пропускаются повторы, но с сохранением порядка.

Может я вас не совсем верно понял, но мне видится, что это происходит только в данном примере (для 23#).

Рассмотрим другие примеры, с более длинными интервалами
Очень характерная ситуация с интервалом d=106 для 53#

 Возьмем сначала данные из первой строки для этого интервала:
n=16, p_n=53, omega(n)=52, n_seq=240
 1 222 * 3 7 13 3 11 5 3 37 7 3 5 23 3 43 17 3 31 29 3 19 5 3 7 47 3 5 11 3 13 7 3 17 53 3 23 5 3 11 19 3 5 13 3 7 37 3 29 31 3 41 5 3

n=16, p_n=53, omega(n)=52, n_seq=240
 1 222 * 3 7 13 11 5 37 23 43 17 31 29 19 47 53 41

И строку, например, № 49
49 192 * 3 7 13 3 11 5 3 37 7 3 5 23 3 41 43 3 31 29 3 19 5 3 7 47 3 5 11 3 13 7 3 53 17 3 23 5 3 11 19 3 5 13 3 7 37 3 29 31 3 17 5 3
49 192 * 3 7 13 11 5 37 23 41 43 31 29 19 47 53 17

Первая строка и перестановка
3 7 13 3 11 5 3 37 7 3 5 23 3 43 17 3 31 29 3 19 5 3 7 47 3 5 11 3 13 7 3 17 53 3 23 5 3 11 19 3 5 13 3 7 37 3 29 31 3 41 5 3
3 7 13 _ 11 5 _ 37 _ _ _ 23 _ 43 17 _ 31 29 _ 19 _ _ _ 47 _ _ _  _  _ _ _  _ 53 _  _ _ _  _  _ _ _  _ _ _  _ _  _  _ _ 41

Вторая строка и перестановка
3 7 13 3 11 5 3 37 7 3 5 23 3 41 43 3 31 29 3 19 5 3 7 47 3 5 11 3 13 7 3 53 17 3 23 5 3 11 19 3 5 13 3 7 37 3 29 31 3 17 5 3
3 7 13 _ 11 5 _ 37 _ _ _ 23 _ 41 43 _ 31 29 _ 19 _ _ _ 47 _ _  _ _  _ _ _ 53 17

И повторы по-разному располагаются, и порядок меняется для некоторых чисел.
Да, но некоторые числа остаются на своих местах в любой строке из 240.

Кстати, в таблицах это все смотрится намного нагляднее.
Чуть позже сегодня изображу ситуацию для d=106 с помощью таблицы.

-- 05.12.2021, 14:31 --

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

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

Получается, они использовали все три представления функции w(n) из Remark 1.4.
И использовали разные варианты ее вычислений для взаимной проверки результатов.

И значит, в том числе и идея с перестановками как-то используется.

[Yury_rsn]

Изобразил пошаговый процесс построения таблицы по заданной перестановке.
По-моему, очень наглядно.

В двух словах:
Для 53#, d=106 берем одну из перестановок в таблице Зиллера. (Например, 3 7 13 11 5 37 23 41 43 31 29 19 47 53 17)
И последовательно заполняем числами 3, 7, 13, 11, ... остающиеся после каждого шага свободные столбцы.
Первый столбец занимает число 3.
Второй - число 7.
...
Двенадцатый - число 23
...
И так далее.

На первом листе - по шагам, сверху вниз.
https://docs.google.com/spreadsheets/d/ ... sp=sharing

[Dmitriy40]

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

Может я вас не совсем верно понял, но мне видится, что это происходит только в данном примере (для 23#).

Я говорил про Ваши строки, где первая из файла moduli.txt, а вторая из permutations.txt - и вот вторая получается из первой выкидыванием повторов. Пример для 53#:
3 7 13 3 11 5 3 37 7 3 5 23 3 43 17 3 31 29 3 19 5 3 7 47 3 5 11 3 13 7 3 17 53 3 23 5 3 11 19 3 5 13 3 7 37 3 29 31 3 41 5 3
видим 3, оставляем его в строке, дальше видим 7 оставляем, дальше видим 13 оставляем, дальше видим снова 3, пропускаем, дальше видим 11 оставляем, дальше видим 5 оставляем, дальше снова 3 пропускаем, дальше 37 оставляем, дальше 7 пропускаем, дальше 3 и 5 пропускаем, дальше 23 оставляем, дальше 5 пропускаем, ...
3 7 13 _ 11 5 _ 37 _ _ _ 23 _ 43 17 _ 31 29 _ 19 _ _ _ 47 _ _ __ _ __ _ _ __ 53 _ __ _ _ __ __ _ _ __ _ _ __ _ __ __ _ 41 _ _ - записываем лишь числа без пропусков и получаем ровно строку из permutations.txt:
3 7 13 11 5 37 23 43 17 31 29 19 47 53 41

Yury_rsn
Повторю, знание "3 7 13 11 5 37 23 43 17 31 29 19 47 53 41" достаточно для восстановления любых требуемых чисел (хоть соответствующей строки из moduli.txt, хоть d, хоть местоположения соответствующего интервала). Вопрос как получать эти вот последовательности/перестановки.

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

Цель работы видна из результатов:

Непонятна цель Proposition 1.5, а не всей работы.

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

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

Вообще-то это фактически одно и то же.

vicvolf
Претензий к моему доказательству не осталось? Молчание не означает согласия, потрудитесь выразить явно.

[Yury_rsn]

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

Я говорил про Ваши строки, где первая из файла moduli.txt, а вторая из permutations.txt - и вот вторая получается из первой выкидыванием повторов.

Ага, да. Именно так.

[Yury_rsn]

Dmitriy40

Цитата:

Повторю, знание "3 7 13 11 5 37 23 43 17 31 29 19 47 53 41" достаточно для восстановления любых требуемых чисел (хоть соответствующей строки из moduli.txt, хоть d, хоть местоположения соответствующего интервала). Вопрос как получать эти вот последовательности/перестановки.

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

[vicvolf]

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

Претензий к моему доказательству не осталось?

Вы же сами написали, что лень доказывать до конца. Я и не настаиваю.