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

[Yadryara]

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

Поправил Location в 3-й строке.

Здесь мне удобней равнять по левому краю. А вот если смотреть на попутные рекорды по всему полю, то уже стараюсь равнять строго по месту. 1-я позиция находится под буквой L, а 31-я — под буквой l. Заодно видно положение полосы на поле.

Start                                                     Location                    Valids
860271072720571112089954456681650511473773778437340720921    1 1  11111111 11111111111111 24 Vl
8276466129185709384898037667333514567718482446345938       11111111111111111 1111   11    23 De
9204926595955930659029610200709650474407650679458585         1    1111111111111111111111  23 Vl
12928151557178753218526554700017805780952517953844761        1     1111111111111111111111 23 Vl
8495059548859626592773879865662858605488940747161295961      1    1111 111111111111111111 23 An
15760230758531706844376995032385338075337309353237290641  1111111111111111 111111    1    23 Vl

[Dmitriy40]

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

Только этого перебора уже давно нет в программе. Мы ведь обсуждали. Применяется короткая арифметика по 20-й степени 2-ки, а не по 15-й. Я тестировал. Оптимальна была 20-21 степень, а не 15-я.

Я его и имею в виду.
Последнее к чему пришли, это к перебору d=n%p по простым и подсчёте nf[#v-d] и как только nf==nu, так проверка isprime. Цикл по n при этом сделан через накопление готовых остатков с Mod. Медленный цикл foreach+factor с порогом 2^20 (и с 2^18) выполняется уже после этой предпроверки (фактически заменяющей factor с меньшими порогами). Во всяком случае у меня в коде именно такая версия последняя.
15-я степень удобно ложится в AVX, следующая удобная 31 (ну или любое простое меньше), но их вдвое меньше в регистрах и потому почти вдвое медленнее цикл, а уж из-за возрастания числа операций медленнее намного (ещё пропорционально количеству простых).
Чисто в принципе могу и написать ispseudoprime на асме для чисел до 6e57 (192 бита) или сразу до 1e77 (256 битов), но это куча нового непроверенного кода, 24 умножения в первом случае и 42 во втором плюс море сложений и пересылок (это всё в произведении по модулю, которое нужно для степени по модулю, которая нужна для теста Ферма на простоту).

[EUgeneUS]

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

Чисто в принципе могу и написать ispseudoprime на асме для чисел до 6e57 (192 бита) или сразу до 1e77 (256 битов), но это куча нового непроверенного кода, 24 умножения в первом случае и 42 во втором плюс море сложений и пересылок (это всё в произведении по модулю, которое нужно для степени по модулю, которая нужна для теста Ферма на простоту).

Если переписать на asm'е

а) расчет запрещенных остатков и проверку на него.
б) ispseudoprime

То это, в купе с моей идеей, которую обсуждали ранее в ЛС, может открыть возможность нахождения $D(36,14)$.
Пока для нахождения $D(36,14)$ не хватает где-то трех порядков в быстродействии, что скрипта PARI\GP, что pcoul.

Числа там будут как раз где-то 1e77. Плюс минус пять порядков

[Yadryara]

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

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

Вот там и отвечу. И код покажу.

[Dmitriy40]

Прикинул грубо, время ispseudoprime(x,1) для чисел до 6e57 (192 бита) составит порядка 20000 тактов. Для чисел до 1e77 (256 битов) аппроксимирую (код ещё не написал) до 38000 тактов и до 75000 тактов для чисел до 2e96 (320 битов).
При этом вычисление остатков по всем простым до 2^15 для каждого следующего n занимает всего 600 тактов (а до 2^20 порядка 28000 тактов). Плюс проверка если какой-то из них оказался меньше #v, но без ispseudoprime она относительно быстрая (для каждого простого, но не знаю сколько их будет из всех 3500шт).
И получается похоже что выгоднее увеличить базу простых в разы (от 2^15) чем даже однажды запустить ispseudoprime, а ведь она может запуститься почти для каждого места паттерна ...

[VAL]

Три ласточки:
159332752243058260979497958331102179248672080979743380
834813316460033014539824745147809695826098264890432346521
863537446826123518333526492128690755708677450874887040921

[EUgeneUS]

Прорекламирую использование pcoul, в качестве генератора паттернов.

0. Как ранее сообщал Хуго, в конце прошлого года были реализованы ключи:
-I - позволяет указывать паттерн (батч) в явном виде в строке запуска. Это удобно для поиска цепочек по конкретным батчам.
-a2 - дополненные вывод (по сравнению с ключом -a) в режиме генерации паттернов (батчей). Вот об этом ключе и пойдет речь ниже.

1. Ключ -a2 выводит найденные батчи в формате, отучающемся от формата для ключа -a.
а) во-первых, разделитель полей не пробел, а запятая.
б) во-вторых, если в место в батче ничего не подставляется, то там выводится "1", а не "."
в) в-третьих и главное - после батча выводится структура паттерна: LCM, и количество мест для каждого количества делителей, в которых ожидается такое количество делителей после применения батча.

2. Однако, при запуске с ключом -a2 (впрочем, как и с ключом -a), перебирались все паттерны, включая расстановки мест с большими степенями. Количество паттернов оказывалось огромным, а время расчета устремлялось куда-то в район тепловой смерти Вселенной.

3. И вот, на днях, Хуго реализовал ключ -fr, применение которого распространяет ограничения, указанные в ключах -p и -px, на простые числа, используемые в батчах.
В результате, при ограничениях вида (через ключ -px): использовать пятую степень только для простых $2,3$, а более высокие степени не использовать вообще - время генерации всех паттернов (удовлетворяющим этим ограничениям) оказалось около 6 часов (речь про D(48,23)). Что очень неплохо, и вполне приемлемо.

4.Общее количество батчей при таких ограничениях - 670-700 миллионов. Складывать эту низко концентрированную руду в файл нет ни смысла, ни возможностей. Поэтому вывод pcoul был направлен в небольшой скрипт на Питоне, который "на лету" отобрал батчи по условиям: количество простых: 2 или менее, и количество pqr: 16 или более.
Получился файл 15 Мб, 103537 строк.

5. Далее - файл в Ексель, сводная таблица, и всё известно о структуре батчей (при указанных выше ограничениях).

Вот например, полный перечень структур паттернов для нуля простых:

0-2-16-5(11)-9   456
0-2-17-4(11)-9   228
0-3-16-4(11)-243   456
0-3-16-4(11)-9   2402
0-3-17-3(11)-9   140
0-4-16-3(10)-243   658
0-4-16-3(11)-243   1140
0-4-16-3(11)-9   378
0-4-17-2(10)-243   16
0-4-17-2(11)-243   26
0-5-16-2(10)-243   324
0-5-16-2(11)-243   140

Во второй колонке - количество паттернов с такой структурой. Количество подставляемых квадратов простых не всегда соответствует наличию в паттерне $3^5$, поэтому эта информация добавлена в ID структуры.

Или вот, нашлись 4 паттерна с 19 местами pqr (и больше таких нет):

2-0-19-2(11)-243   2
2-1-19-1(10)-243   2

и т.д.

PS. Несколько настораживает нечетное количество найденных батчей. Это означает, что для какого-то (каких-то) не нашлось зеркального.
У нас электричество выключалось, но по некоторым признакам, генерация батчей успела окончиться до этого.
Нужно поразбираться с этим моментом отдельно.
PPS. Выше слова "батч" и "паттерн" используются как синонимы.

[EUgeneUS]

EUgeneUS в сообщении #1715254 писал(а):

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

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

Вот паттерн, который есть в выдаче

(Оффтоп)

2,7,2^3.3^2.19,5,2.17^2,3.11,2^2.13,1,2.3.5.7^2,1,2^5,3^5,2,5,2^2.3,7,2.11^2,3,2^3.5^2,13^2,2.3^2,17.19^2,2^2.7

А вот зеркальный к нему, которого нет в выдаче

(Оффтоп)

2^2.7,17.19^2,2.3^2,13^2,2^3.5^2,3,2.11^2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,1,2^2.13,3.11,2.17^2,5,2^3.3^2.19,7,2

Пропущенный паттерн должен быть между этими двумя строками в выдаче:

(Оффтоп)

425578688,2^2.7,1,2.3^2,13^2.19,2^3.5^2,3,2.11^2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,17^2,2^2.13,3.11,2,5,2^3.3^2,7,2.19^2,20322140996757600,2,1,0,7,0,9,1,2,1,0
425578701,2^2.7,17,2.3^2,13^2,2^3.5^2,3.19^2,2.11^2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,1,2^2.13,3.11,2.17^2,5,2^3.3^2,7,2,20322140996757600,2,1,0,7,0,9,1,2,1,0

Причина пропуска остаётся неизвестной. Склонен считать, что это какие-то глюки с конвейеризацией в Виндах. То есть строка была утеряна или при передаче stdout pcoul в stdin скрипта на Питоне, или при записи stdout скрипта на Питоне в файл.
Может какие-то чудеса, и этот паттерн несовместим по модулям.... Этот вариант выглядит маловероятным, не знаю

[Yadryara]

Если это поможет действовать согласованно и не считать, то я только за. Так что вопросы, прежние, не только к Владимиру но и к НМ. Что уже посчитано и докуда? Ведь уже почти два месяца ищут.

EUgeneUS в сообщении #1715254 писал(а):

Ключ -a2 выводит найденные батчи в формате, отучающемся от формата для ключа -a.

А зачем им отучаться от формата?

EUgeneUS в сообщении #1715254 писал(а):

Несколько настораживает нечетное количество найденных батчей.

Не заметил никаких нечётных количеств в самой правой колонке.

EUgeneUS в сообщении #1715254 писал(а):

Выше слова "батч" и "паттерн" используются как синонимы.

И напрасно. Потому что батч это скорее синоним комплекта. А поиск по лучу — синоним поиска по паттерну.
Очень похоже, что не только почти 4 года назад, но и ещё сравнительно недавно Владимир искал именно что по одному паттерну. Не хочу называть это надкусыванием. Но из 576 паттернов, по его словом было проверено около 16%.

Между тем, та смутная идея ускорения у меня оформилась получше. Тестирую.

[Yadryara]

EUgeneUS в сообщении #1715254 писал(а):

время генерации всех паттернов (удовлетворяющим этим ограничениям) оказалось около 6 часов (речь про D(48,23)).

Я решил поискать паттерны именно с 243. Считал в 5 потоков на обычном PARI (по числу возможных положений полосы). 4 потока уложились в 85 минут, а 5-й считался 135 минут.

Ровно 16 штук 0-4-17-2-10! подтверждаю. Другие меня пока не интересовали.

А зачем вы этим занялись? Зачем сообщаете инфу? Запрет не боитесь нарушить?

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

Тем более если вы в pcoul разбираетесь. Что почти за два месяца было насчитано? Какие приближения, хотя бы?

Ну вот например такую статистику Макарова показывала 12 января:

305 b10: 3^2 2.19.29^2 17^2 2^2.3.5 7^2.13 2.53^2 3.47^2 2^3.61^2 5.59^2 2.3^5 11.41^2 2^2.7 3.37^2 2.5^2 23^2 2^5.3 43^2 2.13^2 3^2.5.7 2^2.17 19^2 2.3.11^2 31^2: 25411 / 168269 (3998396.98s) [68137067961 5677870060 462514163 36418320 2797717 236469 27760 4726 898 202 50 7 2 0 1 1 0 0 1 0 0 0 0]

Как понимаю, почти 4 миллиона секунд круглосуточного счёта. Делим на 86400, получаем 47-й день счёта. А нынче уже 54-й день идёт.

Единичка на 19-м месте. Если идти подряд слева направо, считая с нуля, как уточнил Хьюго, то это означает что непрерывный valids=18. Так? А общий valids какой? Он ведь может быть и 22. И само это приближение где? Чему оно равно?

[Huz]

EUgeneUS в сообщении #1715260 писал(а):

А вот зеркальный к нему, которого нет в выдаче

(Оффтоп)

2^2.7,17.19^2,2.3^2,13^2,2^3.5^2,3,2.11^2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,1,2^2.13,3.11,2.17^2,5,2^3.3^2.19,7,2

If I run with additional modular restrictions '-m32=20 -m243=232 -m25=21 -m49=35 -m121=116' to reduce the amount of output, this entry shows up fine:

(Оффтоп)

89,2^2.7,17.19^2,2.3^2,13^2,2^3.5^2,3.11^2,2,7,2^2.3,5,2,3^5,2^5,1,2.3.5.7^2,1,2^2.11.13,3,2.17^2,5,2^3.3^2.19,7,2,20322140996757600,0,0,0,8,2,2,2,8,1,0

It might be worth piping just that line into your python script to check that it handles it correctly.

Hugo

[Dmitriy40]

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

это означает что непрерывный valids=18. Так?

Мне кажется он говорил о количестве проверок (т.е. 18 или 19 проверок мест паттерна успешны), но не об их точном порядке по местам паттерна. Тогда это не непрерывный valids и даже не просто valids, а лишь его ограничение снизу.

[EUgeneUS]

Huz
I am almost 99.(9)% sure that pcoul correctly generated and output this batch to stdout.
This is what your check confirms.

The Python script filters rows by fields of the form "t *".
And again, I’m 99.(9)% sure that this is not a filtering problem in the script.
For the reason that the missing batch is unremarkable. And the conditions on the “t *” fields will work in exactly the same way as on the adjacent lines and on its mirror twin, which was successfully processed.

I'm pretty sure the problem is passing a string from stdout pcoul to stdin of the script. It's less likely that the problem is passing a line from the script's stdout to writing to a file.

pcoul worked quickly, the script or writing to a file was slow for some reason, the buffer overflowed and the line was lost. Something like that.

-- 19.01.2026, 20:50 --

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

Ну вот например такую статистику Макарова показывала 12 января:

Тут ключевое:

305 b10:

Это означает, что pcoul закончил считать задание по конкретному паттерну, заданному в журнальном файле (но не ключом -I), и начал считать в этом же диапазоне другие, сгенерированные батчи.
НМ это понимает, но почему-то не останавливает эти задания.
Поэтому, набранная статистика относится не к этому паттерну, а который считался по "изначальному" заданию.

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

И само это приближение где? Чему оно равно?

А зачем оно?

-- 19.01.2026, 21:00 --

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

Не заметил никаких нечётных количеств в самой правой колонке.

Очевидно, не заметили, потому что их там нет.
Загадка - зачем их там искать.

[Yadryara]

EUgeneUS в сообщении #1715311 писал(а):

А зачем оно?

Очевидно. Чтобы, например, посмотреть на его valids.

Кстати, а чем коллекционирование непрерывных цепочек осмысленнее чем коллекционирование дырявых?

EUgeneUS в сообщении #1715311 писал(а):

Загадка - зачем их там искать.

Вот и мне тоже интересно. И таких загадок в теме полно.

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

[Yadryara]

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

Мне кажется он говорил о количестве проверок (т.е. 18 или 19 проверок мест паттерна успешны), но не об их точном порядке по местам паттерна. Тогда это не непрерывный valids и даже не просто valids, а лишь его ограничение снизу.

Я так понимаю, что не только снизу, но и сверху:

$18 \leqslant valids < 23$

Но Хьюго-то здесь был, почему он промолчал?

Хьюго, Вы понимаете что такое valids ?
_________________________________________

But Hugo was here, why didn't he say anything?

Hugo, do you understand what valids are?