Максимальная возможная разность между вычетами ПСВ(p\#)

[vorvalm]

Мне все-таки удалось найти эти кортежи в ПСВ по модулю $61\#$
с помощью WolframAlpha.
Правда, число их оказалось не 8, а всего 6. Это связано с тем, что $p=59$
также имеет ограничения и не может занимать кратную позицию 118.
Привожу не начальные числа этих кортежей, но центры стыков ПСВ по неполному модулю $53\#/29\cdot31$,
где эти кортежи расположены.

52 737 849 773 778 802 763 130

103 408 734 889 925 904 569 130

115 010 475 307 805 560 493 010

Они легко проверяются на WolframAlpha. Эти центры стыков совпадают с центрами кортежей.
Например, прибавляя последовательно + 1, +31, +61 получим вычеты кортежа 60, 90. 120.
То же получим в обратную сторону - 29 . -59.
Чтобы получить симметричные кортежи, надо вычесть эти стыки из $61\#$.

[vorvalm]

Ранее был рассмотрен случай прогрессии с разностью $d=30$ среди взаимно простых чисел ПСВ
при общей разности 120 (5 членов).
Такие прогрессии с разностью $d=30$ при определенных условиях могут иметь максимум 7 членов
при общей разности 180.
Попытка найти такую прогрессию в ПСВ аналогичным методом привела к интересному результату.
Ближайшая к 180 разность $2p=2\cdot 89=178$. Это означает, что надо рассматривать ПСВ
по модулю $97\#$, где такие разности есть на стыках ПСВ по модулю $83\#$.
Обозначим эту разность сокращенно с вычетами в критических точках и положение цепочек простых
чисел относительно этих вычетов.

0. . . . . .28, 30. . . . . .58, 60 . . . . . .88, 90. . . . . .118, 120. . . . . 148, 150. . . . . .178. 120
89 . . . . . . . 59. . . . . . . . 29. . . . . . . . . . . . . . . . . . . . 31. . . . . . . . . 61. . . . . . .89

По аналогии с разностью 120, нам придется перемещать цепочки простых чисел 29, 31, 59, 61, 89 которые
перекрывают вычеты 60, 120, 30, 150, 0 (178). Вычет 90 не перекрывается простыми числами модуля ПСВ.
но вычет 88 придется заменить простым числом 97.
Произвольно перемещать цепочки нельзя, т.к. их "хвосты" могут перекрыть нужные нам вычеты.
Например, цепочка 29 может занять только вычет 28, цепочка 31 может занять вычеты 148 или 178.
Цепочка 59 может занять вычеты 58 или 88. Остальные цепочки более свободны.
После перемещений проверка показала, что вычеты 0, 30, 60, 90, 120, 150 являются вычетами данной ПСВ,
но вычет 180 оказался кратен $7\cdot 13=91.$ и следующий вычет ПСВ оказался 186, т .е.
"прогрессия" получилась такая 0, 30, 60, 90, 120, 150, 186.
Привожу вариант центра стыка ПСВ, где расположена данная прогрессия:

2178450193126523435271207141135359310

Проверяется на WolframAlpha. Вычеты -89, -59, -29, +1, +31,+61, +97 являются вычетами ПСВ по модулю $97\#$
Чтобы вычет 180 оказался вычетом ПСВ, необходимо удалить цепочки 7 и 13, но это будет уже не та ПСВ.
Учитывая ограничения по перемещению цепочек простых чисел, таких прогрессий в ПСВ ($97\#$) должно быть 12,
плюс 12 симметричных.

[vicvolf]

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

Этого я посчитать не могу:

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

Ещё раз специально повторю: мой алгоритм не выдаёт именно максимально плотное размещение! Лишь некоторое приближение. Потому указанные выше цифры не являются минимальными! Скорее всего минимальные контрпримеры в 1.2-1.5 раза меньше.

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

... реально самое плотное размещение будет ещё на несколько процентов плотнее (например интервал $106$ вместо реальных $53\#$ у меня появляется лишь на $67\#$, а интервал $926$ вместо реальных $269\#$ лишь на $359\#$).

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

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

Для нахождения гарантированно минимального $p_r$ где впервые появляется некий интервал надо перебрать значительную часть от всех вариантов расстановок вычетов, а это порядка $\varphi(p_r\#)$, что больше $10^{500}$ и абсолютно нереально. Как этот перебор оптимизировать без ухудшения плотности размещения я не знаю.

Что значит алгоритм выдает некоторое приближение к максимальному плотному размещение вычетов? Это что нереальные вычеты ПСВ?

[Dmitriy40]

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

Это что нереальные вычеты ПСВ?

Как легко проверить они реальные. Но не обязательно максимальны для данного $p\#$.

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

Что значит алгоритм выдает некоторое приближение к максимальному плотному размещение вычетов?

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

[vicvolf]

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

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

Это что нереальные вычеты ПСВ?

Как легко проверить они реальные. Но не обязательно максимальны для данного $p\#$

У нас приведенная система вычетов (ПСВ) по модулю, равному праймориалу. В нее входят вычеты (взаимно простые числа по данному модулю). Расстояния между вычетами мы называем интервалами. Можно говорить о максимуме интервалов между вычетами, а не о максимуме вычетов. Я спрашиваю реальные ли у вас вычеты, т.е. взаимно простые числа по данному модулю?

[Dmitriy40]

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

Я спрашиваю реальные ли у вас вычеты, т.е. взаимно простые числа по данному модулю?

По моему это тавтология: а какие ещё они могут быть?! Если они и строятся как взаимно простые с неким числом (праймориалом, произведением простых).
И да, они не взаимно простые, они взаимно простые по модулю (с модулем).
Нет, я не понимаю Вашего вопроса: "вычет это реальный вычет или нет?".
Ну возьмите калькулятор и проверьте, например.

[vicvolf]

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

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

Это что нереальные вычеты ПСВ?

Как легко проверить они реальные. Но не обязательно максимальны для данного $p\#$.

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

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

(код на 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.

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

[Dmitriy40]

vicvolf
По прежнему не понимаю вопроса: программа разумеется другая, но gcd(p,pr) в ней тоже есть, и тоже разумеется, как иначе то?! Как вычеты могут не быть реальными?!

[vicvolf]

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

vicvolf
По прежнему не понимаю вопроса: программа разумеется другая, но gcd(p,pr) в ней тоже есть, и тоже разумеется, как иначе то?! Как вычеты могут не быть реальными?!

Хорошо, реальные. А как понимать:

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

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

Что значит алгоритм выдает некоторое приближение к максимальному плотному размещение вычетов?

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

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

Цитата:

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

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

[Dmitriy40]

vicvolf
Я уже плохо помню как именно та программа работает.
В общих чертах я описывал, она для каждого простого от 2 до заданного пытается найти смещение, дающее максимально возможный интервал между взаимно простыми с модулем. Это и есть фактически "жадный" алгоритм, использование наилучшего варианта на каждом конкретном шаге, без полного перебора всех комбинаций вариантов для всех шагов. Засада именно в этом, что оптимальность на каждом шаге вовсе не гарантирует оптимальность в целом. При переходе к следующему простому смещение сформированного интервала аккуратно пересчитывается (используя китайскую теорему об остатках, не помню зачем именно её) и снова ищется смещение уже нового простого для максимизации интервала.
И в результате перебирается лишь $p$ вариантов для каждого простого $p$ до заданного в праймориале, это квадратичная зависимость вместо факториала. Ну плюс там какие-то мелкие оптимизации ещё делал, затуманивающие код, но по плохо понятной причине улучшающие результат.

Т.е. если грубо, то один большой перебор $p!$ разбивается на много ($p$) маленьких переборов (по $p$ вариантов), каждый из который находит оптимум, но выполняя их последовательно в сумме нахожу лишь нечто кое-как близкое к оптимуму. Но и этого оказалось достаточно.