Пентадекатлон мечты

[Yadryara]

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

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

Ну это-то понятно. Поэтому и нужен будет один экзешник на много паттернов.

Может по этой же причине и нет нужды вникать в тонкости проверки. А может и есть. Вот если взять прогу VAL в конце 1-й странице, так там видно, что шаг в 6 раз больше чем у Вас, но первая проверка делается для стартовой точки ещё до первой прибавки шага. Вы то же самое видите?

[Dmitriy40]

Yadryara в сообщении #1562634 писал(а):

Вы то же самое видите?

Повторю, увеличение шага у VAL в 6 раз я считаю фильтрацией и ради универсальности унёс в ускорители ещё в апреле. Из-за этого ещё было плохо понятно как их собственно сравнивать, по интервалу чисел или по количеству проверок, которое в 6 раз меньше.

Но Вы недопонимаете работу ускорителей: если массив bb[] не пуст, то ускоритель проверяет не каждый индекс в заказанном ему интервале, а лишь каждый 6-й, потому что 2 и 3 добавляются в bb[] всегда (для данного класса паттернов так как имеют лишь по одному допустимому варианту) и соответственно из 6-ти подряд индексов допустимым является максимум один (но для каждого паттерна свой). А если Вы добавляете в bb[] ещё и свои значения (ради увеличения скорости работы ускорителя), то ускоритель использует уже не 6-ти кратный шаг, а ещё больше (для примера выше он 9102/780=11.669), но лишь в среднем, конкретные значения шага между проверяемыми индексами могут быть кратно больше если какой-то следующий (-ие) индекс недопустим, список проверяемых индексов (по модулю блока, который равен произведению простых из строки "Decycle:" в файле .inc, повторяющей реальное содержимое bb[]) указан в .inc по метке offsets.
Так что программа VAL идёт с шестикратным шагом, ускоритель же идёт по заказанному ему интервалу индексов с переменным шагом (но всегда не менее шестикратного, для данного класса паттернов).
С какой именно точки ускоритель начинает проверку - дело тонкое, но точно не далее размера одного блока от заказанного начала вниз, т.е. в самом наихудшем случае проверит почти один лишний блок. И в конце может проверить почти один лишний блок. Для блоков порядка тысячи индексов это в сумме менее 0.1% от заказанного интервала (в миллионы индексов), т.е. слёзы. Пока ускорители вызываются для миллионов индексов не вижу никакого смысла в этом разбираться (объяснить то могу, но зачем запутывать, там ведь ещё и инициализация есть во много раз дольше проверки пары блоков).

-- 13.08.2022, 17:23 --

Yadryara
Принятый мной шаг, не ушестерённый, удобен тем что получается прямо из китайской теоремы об остатках, прямо по паттерну. Независимо сколько вариантов остатков допустимо по каждому из простых, это только в этом классе паттернов шаг можно ушестерить, а в других нельзя. А в каких-то ещё не изученных могут быть и шаги скажем в 30 раз больше (по модулю 5 тоже лишь один допустимый вариант). Всё это названо фильтрацией и унесено из PARI в ускоритель, PARI работает с нормальным шагом от КТО, он прекрасно виден в файлах .pat в pp=Mod(), любое его увеличение отдано на откуп ускорителю (как и что там проверяет ускоритель программе на PARI вообще дела нет, она заказала проверить такой-то интервал индексов и всё, хоть с 6-ти кратным шагом, хоть с 26-ти кратным, уж как сможет каждый конкретный ускоритель, так пусть и проверяет).

[Yadryara]

Dmitriy40
VAL

Я задаю вопрос вам двоим.

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

Но Вы недопонимаете работу ускорителей:

Разумеется. Именно поэтому я и хочу пока что сосредоточиться на проге VAL с 1-й страницы. Поскольку мы(по крайней мере трое) понимаем как она работает.

Обозначим через $z37$ число, на которое будет заменено подквадратное число $37$.

Вот здесь используется $37$:

&& ispseudoprime((n+7)/4107)

При $z37=37$, стартовая точка $p1 = 5028162941065848674776261$

Чему будет равна $p1$, если $z37=1680013$ ? Тогда та же строчка будет

&& ispseudoprime((n+7)/8467331040507)

Чему будет равна $p1$, если $z37=4200013$ ?

В обоих случаях шаг уже превышает $5401e33$.

И наконец важнейший вопрос.

Существует ли такое значение $z37$, начиная с которого можно будет уверенно сказать, что $p1a$ превысит $5401e33$ ??

[Dmitriy40]

Yadryara в сообщении #1562639 писал(а):

При $z37=37$, стартовая точка $p1 = 5028162941065848674776261$

Уже тут ошибка, начальное число не должно быть больше шага строкой выше. Т.е. кто-то (VAL, кто же ещё) уже проверил p1-m и решил что оно не подходит. Я не собираюсь делать какие-то лишние проверки, для того есть переборная PARI программа и ускорители.

Yadryara в сообщении #1562639 писал(а):

В обоих случаях шаг уже превышает 5401e33.

Вы забываете что это лишь для данного конкретного паттерна из 46080. Для других паттернов начальная точка при ровно такой же замене $z37$ может и не превысить 5401e33. Я же выше показал пример с заменой 37 на 4096667, там натурально одно из чисел в цепочке имеет это простое в квадрате и все числа цепочки при этом меньше 5401e33.

Yadryara в сообщении #1562639 писал(а):

Существует ли такое значение $z37$, начиная с которого можно будет уверенно сказать, что $p1$ превысит 5401e33 ??

О! Я недооценил сложность вопроса. Считал только величину шага (при этом допустимы любые начальные значения), а вот начальное значение из виду упустил, ничего не мешает ему быть и меньше 5401e33 даже при достаточно большом шаге. Во всяком случае это простое не больше чем $\sqrt{5401\cdot10^{33}/37/41}\approx6\cdot10^{16}$ (иначе $pq$ будет иметь простое меньше 37, а они все заняты, и такое вовсе не исключено, вон в 14-ке 182212015721072444191301392660439641 одно из мест содержит 23 в первой степени, хотя 23 в квадрате заменено на другое простое, а оно вернулось уже в $pq$ место). Учитывая нелинейность КТО не готов оценить какие именно простые окажутся недопустимыми, надо вспоминать формулу восстановления остатка по модулю и проверять все 46080/6=7680 варианта начальных значений.
Т.е. даже оценка в сотни тысяч вариантов для каждой замены слишком занижена.

Если не ошибся, то существуют вот такие паттерны с заменой 37 на p37 с начальным числом менее 5.4e36:
v=[45,253517044545040322,169,12,49,50,1587,32,121,18,4805,28,2523,578,361]; pp=Mod(881350997235128829523053869900928345, 40790395777905825015093007202974416967200); p37=356031631;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,1001764351548313369]; pp=Mod(3480381030093155129643061394269795545, 322363843024315492299807230063304052288800); p37=1000881787;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,4058245830176986561]; pp=Mod(2605086024458990853727800249201765945, 1305927606358992343185211153947653154247200); p37=2014508831;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,9009452846817153721]; pp=Mod(446522713845601440864126679272463545, 2899206623551194348658847927868669226279200); p37=3001575061;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,16217346175838003641]; pp=Mod(25290217001329937263841385448457145, 5218678453489261957837669690003678599463200); p37=4027076629;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,25040117351118556129]; pp=Mod(1009956400318978398113296970920178745, 8057811646631668800780662428320877865440800); p37=5004010127;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,82913562858707103121]; pp=Mod(22152511181586201019851436863633945, 26681259640213809634990662063741258865159200); p37=9105688489;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,258296432986146162721]; pp=Mod(765032436093768493763402251760558745, 83118780028649182183873359294602324043079200); p37=16071603311;
v=[45,98,169,12,121,50,867,32,2527,18,2645,4,2523,1922,421045601001225858529]; pp=Mod(3410023184201641402717999982273328345, 135490824581105817410687273674823431229920800); p37=20519395727;
Вполне вероятно оценку простого можно и ещё поднять.

[Yadryara]

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

Уже тут ошибка, начальное число не должно быть больше шага строкой выше.

Вроде как не должно, да. А чья это ошибка? VAL ?

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

О! Я недооценил сложность вопроса.

Вот именно что О!

Yadryara в сообщении #1561720 писал(а):

Рекордная 12-ка попасться не может, ибо рекорд Hugo меньше шага.

И никто ведь мне не сказал: "Антоха, ну и что что меньше шага? Самая первая проверка-то делается ещё до первого шага!"

Да, одна-единственная проверка, крошечная, ничтожная вероятность успеха, но не нулевая.

Так что я сам нашёл это слабое место. Проблема представляется более серьёзной чем сотни тысяч подклассов для обсчёта.

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

Yadryara в сообщении #1562639 писал(а):

Существует ли такое значение $z37$, начиная с которого можно будет уверенно сказать, что $p1$ превысит 5401e33 ??

Вы не заметили, я поправил:

Yadryara в сообщении #1562639 писал(а):

И наконец важнейший вопрос.

Существует ли такое значение $z37$, начиная с которого можно будет уверенно сказать, что $p1a$ превысит $5401e33$ ??

$p1a$, а не $p1$, где $a=722$. Но это вряд ли существенно изменит ситуацию.

[Yadryara]

Крупный шрифт мой.

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

Yadryara в сообщении #1562639 писал(а):

В обоих случаях шаг уже превышает 5401e33.

Вы забываете что это лишь для данного конкретного паттерна из 46080. Для других паттернов начальная точка при ровно такой же замене $z37$ может и не превысить 5401e33.

Нет, не забываю. В этом посте я много говорил о начальной точке. Но в процитированном выше фрагменте речь идёт именно о шаге.

Вы согласны, что шаг в обоих случаях уже превышает 5401e33 ?

Вопросы именно к VAL.

Почему $p1$ больше $m$ ?

Какие соотношения между $p1$ и $m$ в других прогах для 12-ти делителей?

[Dmitriy40]

Yadryara в сообщении #1562675 писал(а):

Вы согласны, что шаг в обоих случаях уже превышает 5401e33 ?

С чем тут можно соглашаться или не соглашаться если достаточно $m$ умножить на $722$, поделить на $37^2$ и умножить на $z37^2$?
Вот только в ускорителях не используется ушестерение шага, потому данный вопрос мне малоинтересен.
Но даже пусть, ОК, для простых до 1.68млн все 46080 ускорителей будут иметь первую проверяемую (не начальную!) точку менее 5401e33 (при пустом bb[]!), а для простых от 1.68млн до 4.1млн уже не все (а начальную - по прежнему все, именно это я и считал), ну и что. А выше 4.1млн уже и начальная точка не у всех будет меньше 5401e33.
Т.е. для укорителей надо различать начальную точку (первое число в pp=Mod()) и первую проверяемую точку (которая вообще говоря может быть раз в 30 больше шага (второго числа там же)). И шаг для ускорителей это просто $\operatorname{LCM}()$ чисел из паттерна, без всяких махинаций (в хорошем смысле) с ушестерением или с делением на $722$. Все махинации скрыты внутри ускорителя и снаружи не видны и никакой путаницы не вызывают. И первая проверяемая точка снаружи тоже не видна, это дело ускорителя где начать проверку, для работы вполне достаточно начальной точки (которая всегда меньше шага просто по определению остатка по модулю). Понимаете, это более единообразное и универсальное (и логичное) поведение, чем в программе VAL.

[VAL]

Со всеми вопросами, кроме одного, уже разобрались:
Начальное значение $p1$ может быть малым и для очень больших значений $z37$.
А вот шаг, действительно превысит указанную границу, начиная с некого обозримого $z37$.

Почему $p1$ может превышать $m$? Вопрос, конечно, интересный?
Еще в начале ветки мы обсуждали, что в формировании $m$ участвуют числа 64 и 27, чтобы интересующие нас числа в цепочке делились соответственно на 32 и 9, но не на 64 и 27. Отсутствие избыточной делимости (на 125, 343...) обеспечивается дополнительными фильтрами, а с двойкой и тройкой можно разобраться сразу, поскольку в каждом классе по модулям 64 и 27 может лежать только одно подходящее значение начального числа цепочки.

При написании maple-программы, которая генерировала $a, m, p1$ и упомянутые фильтры для каждого из тысяч паттернов (понятно, что это делалось не руками), я все правильно учел для тройки, А для двойки соврал (там по ходу формирования многожды что-то умножается и делится на 2): иготовое $m$ делится на 32, но не 64 (при этом $p1$ вычисляется про правильному модулю $2m$).
Так что, мои программки работали значительно медленнее, чем могли бы. Они проверяли в 2 раза больше цепочек, чем следует.
Скорость падала, конечно, не в два раза а меньше, поскольку лишние цепочки отсекались на достаточно ранней стадии. Но, разумеется, правильнее было их вовсе не проверять.

Это касается моих программ без ускорителей. Не знаю, продублировал ли мой глюк Дмитрий или его $m$ как положено кратно 64? (Пока я набирал этот текст, Дмитрий, кажется, уже ответил.)

[Yadryara]

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

Понимаете, это более единообразное и универсальное (и логичное) поведение, чем в программе VAL.

Совершенно не сомневаюсь.

Но я на данный момент хочу досконально разобраться именно в программах VAL.

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

первое число в pp=Mod()

Если Вам нетрудно, скопируйте сюда строчку из ви-файла для паттерна S9-36-125364.

У меня под рукой нет, а я хочу перепроверить.

А вот уже ответ от VAL есть, обдумаю.

[Dmitriy40]

Yadryara в сообщении #1562686 писал(а):

Если Вам нетрудно, скопируйте сюда строчку из ви-файла для паттерна S9-36-125364.

v=[289,722,2883,4,2645,18,847,32,4107,50,841,12,169,98,45]; pp=Mod(106022957662445288229350041, 440538835723387181869888800);
Вы можете легко снова сгенерить все 46080 паттернов поправив r=[] в M12mods1.gp и запустив его, дело нескольких минут, компилировать их нет необходимости, достаточно же списка в M12mods1.patterns.

VAL в сообщении #1562685 писал(а):

Не знаю, продублировал ли мой глюк Дмитрий или его $m$ как положено кратно 64?

У меня все эти вещи получаются автоматом, при компиляции ускорителей: Yadryara, в файле Yadryara6.gen.gp в строке 18 команда if(n<2, bb=Set(concat(bb,m)); - если допустим лишь один остаток по модулю какого-то простого, то это простое насильно добавляется в bb[] и по нему цикл будет развёрнут и реально проверяться будут лишь индексы с допустимым остатком. Для паттернов M12 и 2 и 3 как раз подпадают под это условие и насильно добавляются в bb[] (убедиться можно по строке "Decycle:" в .inc файле или в готовом .exe, повторяющей эффективное содержимое bb[]), что эффективно уменьшает количество проверок в 6 раз (что эквивалентно увеличению шага в 6 раз в программе VAL). Снова подчеркну, это делается в самих ускорителях (в момент их компиляции), внешняя переборная PARI программа об этих тонкостях ничего не знает и работает в обычном шаге из pp, что бы как бы там ни разворачивалось или исключалось или ускорялось, просто ускорители работают вшестеро быстрее вот и всё.

-- 14.08.2022, 11:32 --

Yadryara

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

Я тут посчитал немного, до границы 5401e33, комплекты 234, 482, 540, 664, 872, 1104, 1188, 1905, 1911, 1937, 1941, можете все их помечать проверенными.

Ещё посчитал, комплекты 1453, 1644, 1744, 1808, 1818, 1828, 1841, 1853 тоже проверены до границы 5401e33. Ничего интересно не нашлось.

Раз Вы с Demis переключились на начальные комплекты, а в больших у меня ничего не находится, посчитаю 4xx комплекты (в порядке возрастания), их 20 штук, но они будут считаться вчетверо медленнее (наверное).
Кстати наблюдается конфликт имён для двух 484 комплектов (оба с двумя заменами), пока назвал их 484a (меньший) и 484b (больший), различие менее 0.04%.

[VAL]

Подумалось, неужели я прозевал, что шаг получается в 2 раза меньше, чем надо?! Не может быть! Я же задумывался над этим вопросом.

Проверил. Нет. Шаг ($m$) правильный. Просто само $a$ четно и обеспечивает недостающую степень двойки.
Так что, лишних проверок мои программы не делали. А вот одно возможное значение равное $p1-m$ для тех случаев, когда $p1>m$, похоже, пропускали (хотя тут надо аккуратнее разобраться).
Вероятность пропустить при этом нужную цепочку практически нулевая. Но теоретически...

[Yadryara]

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

v=[289,722,2883,4,2645,18,847,32,4107,50,841,12,169,98,45]; pp=Mod(106022957662445288229350041, 440538835723387181869888800);

Спасибо. Да, это тот самый паттерн с первой страницы, НО

Не совпадают стартовые точки! То есть у Дмитрия стартовая точка примерно 0.24 шага, а у Владимира, даже если m удвоить — 0.69 шага.

Надо же, ошибка в проге с 1-й страницы обнаруживается только на 111-й. И разбирательство ещё не закончено. Почему стартовые точки не совпадают, даже если шаг выравнять ??

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

Т.е. для укорителей надо различать начальную точку (первое число в pp=Mod()) и первую проверяемую точку (которая вообще говоря может быть раз в 30 больше шага (второго числа там же)).

Так и вот и интересует важнейший вопрос:

Было ли хоть раз такое, что начальная точка была одновременно и первой проверяемой ??

Хорошо бы, чтобы это было невозможно.

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

Раз Вы с Demis переключились на начальные комплекты, а в больших у меня ничего не находится, посчитаю 4xx комплекты (в порядке возрастания), их 20 штук, но они будут считаться вчетверо медленнее (наверное).

Очень рад, прокомментирую позже.

-- 14.08.2022, 12:28 --

VAL в сообщении #1562694 писал(а):

А вот одно возможное значение равное $p1-m$ для тех случаев, когда $p1>m$, похоже, пропускали (хотя тут надо аккуратнее разобраться).

Кстати $\dfrac{p1-m}m\approx 0.37$ тоже не равно $0.24$.

[Dmitriy40]

Yadryara в сообщении #1562698 писал(а):

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

В принципе я бы не хотел отвечать за VAL по его программе, но ...
У меня начальная точка 106022957662445288229350041, но посмотрев в файл .inc увидим что первый (и единственный если массив bb[] оставить пустым) проверяемый индекс по модулю 6 будет равен 2 (метка offsets). Соответственно ускоритель будет проверять следующие числа начала цепочек: $106022957662445288229350041 + 440538835723387181869888800 \cdot (2 + 6 i)$, $i \ge 0$. И для $i=1$ (вторая проверяемая ускорителем цепочка) второе число в цепочке после деления на $722$ даст ровно $p1$. Вуаля.
С пропуском $i=0$ пусть VAL разбирается сам.

[VAL]

$M(324)\ge 9$

(Оффтоп)

11987833242642429195806393217004822869728012763803425935301971852981629210346067205785519236019449104330304516318912890621

[Dmitriy40]

Yadryara в сообщении #1562698 писал(а):

Так и вот и интересует важнейший вопрос:
Было ли хоть раз такое, что начальная точка была одновременно и первой проверяемой ??

Специально это не смотрел (таблица offsets видна только в .inc файле, больше нигде), но прямая проверка показала что по крайней мере для исходного комплекта вполне может, например для таких паттернов индексы делятся на 6, т.е. первая проверяемая точка будет именно указанной начальной:
v=[45,578,169,12,49,50,363,32,361,18,2645,28,2523,1922,1369];pp=Mod(349709259425533001455891545,440538835723387181869888800);!N2-31-123456
v=[45,98,169,12,121,50,867,32,2527,18,4805,4,2523,2738,529];pp=Mod(359058244870193391784421145,440538835723387181869888800);!N9-21-125463
v=[45,98,169,12,121,50,867,32,2527,18,6845,4,2883,1682,529];pp=Mod(18686015701948094545205145,440538835723387181869888800);!N9-21-126543
v=[45,98,169,12,121,50,867,32,3703,18,1805,4,2523,2738,961];pp=Mod(295296487251144359854833945,440538835723387181869888800);!N9-21-132465
v=[45,98,169,12,121,50,867,32,3703,18,1805,4,2883,1682,1369];pp=Mod(358199375440262831936621145,440538835723387181869888800);!N9-21-132546
v=[45,98,169,12,121,50,867,32,3703,18,4205,4,1083,2738,961];pp=Mod(198056130542282832370310745,440538835723387181869888800);!N9-21-134265
v=[45,98,169,12,121,50,867,32,3703,18,4205,4,4107,722,961];pp=Mod(10701281698288656049334745,440538835723387181869888800);!N9-21-134625
...
v=[45,98,289,12,121,50,507,32,3703,18,1805,4,2883,1682,1369];pp=Mod(239840811889920156715051545,440538835723387181869888800);!N9-23-132546
v=[45,98,289,12,121,50,1083,32,1183,18,4205,4,1587,1922,1369];pp=Mod(244847183930181964353120345,440538835723387181869888800);!N9-24-124356
...
В общем их много, 7765 из 46080 для исходного комплекта.
Начальная точка может исключиться по какому-то другому простому, такое вполне возможно, но зависит в том числе от содержимого bb[]. В частности если потребовать делимость индекса только на простые 2..13, то из 7765 паттернов останется 4554 штук, а по простым 2..37 подходят 3547 штук, т.е. всё равно дофига.

Для других комплектов и сами паттерны другие, и их количество немного отличается (например 7672 вместо 7765).