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

[Dmitriy40]

EUgeneUS, Yadryara
Так, вот тест: https://dropmefiles.com/NfHVx
Скачать все 7 файлов, (распаковать и) положить в одну папку, запустить PARI, в нём командой \r T2.gp запустить тест, он займет пару минут, на экран (и в файл лога T2.txt) выведет 6 результатов, PARI не закроется, процитируйте их сюда please.

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

Так что лучше заранее добавить в самом наче каждой программки нечто вроде

Лучше: default(parisize,110*10^6);

[VAL]

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

Лучше: default(parisize,110*10^6);

А чем лучше? Это я не спорю. Это я интересуюсь.
Allocatemem помогал, например, при поиске цепочки чисел по 116 делителей. Без него там все сразу вылетало.

[Dmitriy40]

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

А чем лучше?

Если делать в начале, то в общем ничем не лучше, пишут что вообще синонимы. Просто мне изменять параметры как-то более логично (и единообразно), allocatemem же напоминает скорее выделение памяти под конкретный объект, чем под общий стек.

[Dmitriy40]

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

Я так прикидываю цепочки ALL (т.е. все 10 простых) будут где-то одна на 10-20 миллионов,

Похоже ошибся, за 100млн попыток пока ни одной цепочки нет.
И весьма сильно ошибся, более точная оценка даёт одну цепочку ALL на 5-20млрд попыток, это мне до недели счёта, на одну цепочку ALL. Какой-то неурожайный вариант паттернов.

[VAL]

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

И весьма сильно ошибся, более точная оценка даёт одну цепочку ALL на 5-20млрд попыток, это мне до недели счёта, на одну цепочку ALL. Какой-то неурожайный вариант паттернов.

У меня оценка более... пессимистичная: 10 простых будут встречаться примерно раз на полтора триллиона.
Думаю, дело не в конкретном варианте.
Все же 6 простых одновременно, которые были необходимы для цепочки из 13 чисел, и 10 простых - это две большие разницы!
Конечно, для цепочки из 15 чисел по 12 делителей и вовсе нужна была простота 11 чисел. Но там числа были менее 40 знаков, а здесь - порядка 80.
В общем, моя начальная гипотеза, что 15 чисел по 36 делителей нам не потянуть, похоже, подтверждается. Сейчас набросаю паттерн на 14 и попробую оценить.

-- 27 апр 2022, 01:00 --

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

Сейчас набросаю паттерн на 14 и попробую оценить.

Похоже, для 14 чисел 8-ю проверками на простоту не обойтись. А для 9-и задача тоже выглядит неподъемной.
13 чисел по 36 делителей нашлось как-то легко и быстро. И я полагал, что 14 как-нибудь осилим. Но сейчас не верю.

[Dmitriy40]

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

У меня оценка более... пессимистичная: 10 простых будут встречаться примерно раз на полтора триллиона.

Я прикинул так: подсчитал реальные вероятности по всем 10-ти местам появиться простому, по всем 120-ти паттернам в каждой группе, где-то около 2.5e86, по 100 итераций на каждый паттерн, получил нечто подобное: L01: [308,491,0,506,0,433,565,0,488,520,563,0,519,537,0], [0,0,370,0,435,0,0,211,0,0,0,426,0,0,391] - отдельно по 10-ти проверяемым местам и по 5-ти непроверяемым, это сколько раз получилось 36 делителей в каждом месте, потом оценил вероятность как $(480/12000)^{-10}/5760\approx17\cdot10^9$ (взял некую "среднюю"). Можно и поточнее, $(500/12000)^{-9}(300/12000)^{-1}/5760\approx26.5\cdot10^9$.

Кстати странно что первое число заметно реже встречается, это не глюк, так во всех группах. Второе и шестое тоже несколько реже остальных, но не настолько сильно. $2^8$ тоже выбивается из общей картины, но там сомнительнее, полную факторизацию не проводил.

Да, выходит 15-ка нам не светит, до неё порядка $10^{17}$ шагов по всем паттернам (если непроверяемые места такие же редкие), типа 200 тысяч лет счёта в один поток.

[EUgeneUS]

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

Так, вот тест:

результат:

v7-16k: N=29151, 15.507s (2.199s in PARI) per round 0e86.
v11-16k: N=29151, 9.875s (2.856s in PARI) per round 0e86.
v101-16k: N=29151, 17.082s (2.247s in PARI) per round 0e86.
v303-16k: N=29151, 11.762s (2.902s in PARI) per round 0e86.
v7-32k: N=14722, 22.339s (1.123s in PARI) per round 0e86.
v101-32k: N=14722, 24.289s (1.311s in PARI) per round 0e86.

ниже аналогичный результат, но при запущенных 4-х потоках PARI:

v7-16k: N=29151, 37.113s (3.760s in PARI) per round 0e86.
v11-16k: N=29151, 19.578s (3.745s in PARI) per round 0e86.
v101-16k: N=29151, 39.655s (3.729s in PARI) per round 0e86.
v303-16k: N=29151, 25.662s (3.728s in PARI) per round 0e86.
v7-32k: N=14722, 70.855s (1.856s in PARI) per round 0e86.
v101-32k: N=14722, 74.865s (1.858s in PARI) per round 0e86.

[Yadryara]

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

EUgeneUS, Yadryara
Так, вот тест: https://dropmefiles.com/NfHVx
Скачать все 7 файлов, (распаковать и) положить в одну папку, запустить PARI, в нём командой \r T2.gp запустить тест, он займет пару минут, на экран (и в файл лога T2.txt) выведет 6 результатов, PARI не закроется, процитируйте их сюда please.

Сейчас уже не надо?

Ну а я жду ответы на вопросы про КМК. Также интересно Ваше мнение, как переделать проги с подквадратного 41 на 43.

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

Такую задачу надо изначально ставить по другому и оптимизировать не перебор каждого паттерна в глубину, а ускорять перебор всего множества паттернов. Это практически полное переписывание программы.

Здесь Вы правы насчёт перебора всего множества паттернов. Если имелись в виду именно различные подклассы патернов. Думаю начать пока с перехода к 92160 паттернам на низинах. Аллокэйтмем мне приходилось брать пока $2^{23}$.

[EUgeneUS]

VAL
Это же не единственная возможная система паттернов?
Может быть попробовать альтернативную?

[VAL]

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

VAL
Это же не единственная возможная система паттернов?
Может быть попробовать альтернативную?

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

-- 27 апр 2022, 12:07 --

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

Да, выходит 15-ка нам не светит, до неё порядка $10^{17}$ шагов по всем паттернам (если непроверяемые места такие же редкие), типа 200 тысяч лет счёта в один поток.

Нет, в остальных позициях вероятности набрести на требуемое разложение значительно выше. Так что, за 40 тысяч лет должны управиться

-- 27 апр 2022, 12:16 --

Любопытно, что искать 13 чисел по 36 делителей ненамного сложнее, чем 12 (что и подтвердилось).
И там, и там оптимальная система паттернов требует 6 подтверждений простоты одновременно.
А вот переход с 13 на 14 (не говоря уже о 15) значительно усложняет задачу.
Причина проста, как и число 13
А вот 14 заведомо добавляет две проверки на простоту (в систему добавляются по числу, кратному 2 и 7). А учетом того, что числа кратные 2, 3 и 5 не удается расставить оптимально, добавляется еще одна проверка на простоту.

[EUgeneUS]

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

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

Если разрешить искать хотя бы один квадрат большого простого числа, то для цепочки из 14 чисел у меня получилась такая раскладка:
$p^2$ - 1штука
$p$ - 7 штук
$pq$ - 6 штук.
При этом используются квадраты 16-ти (а не 21) заданных простых чисел больше $7$.
Всё это должно бы значительно снизить разрядность чисел, и увеличить вероятности... Вот только не знаю, насколько поломает благостную картину квадрат большого простого.

[Dmitriy40]

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

Сейчас уже не надо?

Ну, если считать M36n15 не будем (или не будете), то и не надо.

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

Ну а я жду ответы на вопросы про КМК.

Я посчитал их риторическими и неактуальными. Например в M36n13 уже присутствует $3^8$ вместо квадрата и получается уже они были не КМК. Фактически КМК (если ещё не обращать внимание на исключение с двойкой) остались в силе лишь для M12n15/14, а ими похоже занимаетесь только Вы.

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

Также интересно Ваше мнение, как переделать проги с подквадратного 41 на 43.

Заменить 7 на 8 в r=Set([]), плюс оставить bb=[5,37]. Сам не пробовал, но новых подводных камней не вижу.

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

Здесь Вы правы насчёт перебора всего множества паттернов. Если имелись в виду именно различные подклассы патернов.

Тут имелось в виду разное, но как минимум — перебор вариантов с перестановками простых в квадратах между непроверяемыми местами, что вообще никак не влияет на программу кроме единственного числа $n_0$ из $n=n_0+km$, т.е. только на начальную инициализацию таблицы save_xmm (которую можно раздублировать нужное количество раз вместе с кодом её модификации и проверки и оптимизировать именно не проверку её в глубину, а проверку разных её вариантов, но как и говорил это почти полное переписывание кода). В принципе перестановка других простых (11 и 13) тоже вроде не влияет ровно настолько же, но тут не 100% уверен, надо подумать, да они (эти перестановки) и сильно менее регулярны, что всегда проблема для программиста.

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

Думаю начать пока с перехода к 92160 паттернам на низинах. Аллокэйтмем мне приходилось брать пока $2^{23}$.

Этого простите не понял. Если просто объединить два разных класса паттернов в один список, то это легко (просто увеличить M12mods1.patterns и всё, я же говорил что главное получить список паттернов, дальше за исключением некоторых моментов всё просто), но вот PARI программы перебора придётся внимательно проверить чтобы там нигде не было явного указания на величину шага/модуля pp.mod, а он обязательно брался из файлов .v/.pat для каждого паттерна. Сейчас, для новых поисков, у меня так и есть (даже маску проверяемых чисел z[] формирую сразу в M12mods1.patterns), но как было тогда и чем сейчас пользуетесь Вы я не уверен.

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

результат:

Спасибо, ожидаемо. Выходит у Вас кэш не настолько маленький или не так сильно влияет, как было на других программах у Yadryara.
Правда теперь уже не знаю будем ли считать M36n15 в таком варианте ...
У меня за почти сутки счёта и 1.6млрд шагов по всем 5760 паттернам (т.е. почти 10трлн попыток) так и не нашлось ни одной ALL цепочки, логи совершенно пусты, даже выкладывать/показывать нечего.

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

Вот только не знаю, насколько поломает благостную картину квадрат большого простого.

Портит, и сильно: квадрат резко ограничивает допустимость подстановки других простых (в квадратах), но это как бы даже и благо, но вот что с ростом чисел большие простые в квадрате встречаются всё реже и реже (сильно реже обычных простых), это беда. Т.е. линейный перебор 7-ми простых даже с очень большим шагом тут помогает мало, в 99% не извлекается даже корень, не говоря уже об простоте числа под ним. А моя программа сейчас не умеет проверять извлечение корня, значит практически все найденные ею кандидаты будут ошибочными и в PARI отбросятся, впустую заняв время на проверку.
Выходом был бы перебор именно по $p^2$, тем более что вероятно там допустимо очень далеко не любое $p$, как и делал VAL например в случае c 30-ю делителями, но как тут присобачить ускорители неясно, они слишком заточены на линейный перебор, попытка заставить перебирать по квадрату (что в принципе возможно) съест всё ускорение. А перебирать триллионы $p^2$ в чистом PARI ... перспективно, но надо подумать как (какой системе модулей должно отвечать $p$, я с этим не до конца разобрался).

-- 27.04.2022, 16:21 --

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

Аллокэйтмем мне приходилось брать пока $2^{23}$.

Это забыл прокомментировать (из-за малопонятности что здесь такого). Память нужна для размещения списка паттернов (тем более они с полными путями) и для размещения списка найденных кандидатов из моей программы (его размер и добавляется к N). Первое фиксировано (пока пути не меняются) и легко оценивается, второе легко регулируется величиной интервала 227e6 или 23e6, передаваемого моей программе для проверки вторым параметром.
Плюс нет никакой опасности зарезервировать хоть на порядок больше памяти чем реально потребуется: винда незадействованную память оставит сугубо виртуальной и физически размещать ни в RAM ни в файле подкачки не будет. Пока туда не произойдёт физической записи (т.е. она станет используемой). Потому обычно можно запросить хоть гигабайт-полтора (а на x64 винде и терабайты и петабайты). Правда есть засада: бывает при выделении памяти пользовательская программа (в данном случае сам PARI, не винда) её инициализирует (и не нулями), что переводит её в статус используемой и физически представленной в RAM и/или файле подкачки (я даже в каких-то рекомендациях встречал инициализировать выделенную память сразу чтобы избежать тормозов в произвольном месте потом). Как действует PARI я не знаю. Но никаких трудностей с выделением сотен мегабайт не замечал, потому выделяю с большим запасом и не парюсь.
Единственный непонятный момент связан с parisizemax: у меня если его сильно задрать и память реально потребуется, то закрываться программа по завершении счёта может аж минуты (что бесит), видимо высвобождение занятой памяти в PARI весьма глючно/тормознуто. С parisize такой проблемы нет и потому я предпочитаю увеличивать его (даже если память и не потребуется, винда сама разберётся).

[EUgeneUS]

Некоторые соображения по паттернам с квадратом для 14-36. Если что не так - поправьте, пожалуйста.
1. Проблемы следующие:
1.1.
а) Если брать $2^8$ не строго по середине (не в 7 или 8 позиции для 14 и не в 8 позиции для 15-ки), то вылезает $2^3$. Разложение такое есть, но оно содержит только куб и два квадрата: $N=p_1^3 p_2^2 p_2^2$, простого в первой степени нет.
б) Если брать $2^8$ по середине (в 7 или 8 позиции для 14 и в 8 позиции для 15-ки), то "раскладка" получается неоптимальной и приходится искать 10 простых и только пять $pq$.
1.2. Для 36 делителей (в отличие от 12) в разложении добавляется дополнительный квадрат простого. В результате проблема (1.1) для 15-12 оказалась преодолимой, но для 15(14)-36 порядок чисел улетает в далекие дали, что резко снижает вероятность нахождения простых. Беда.

2. Пути решения.
2.1. Оптимизация паттернов без квадрата большого простого исчерпана (для 15-36 - точно, для 14-36 скорее всего).
2.2. Добавляем квадрат большого простого. Он ситуацию ухудшает и в целом очень сильно. Оценим:
а) вероятность, что число является квадратом: $P_1 \approx \frac{1}{2n}$.
б) вероятность, что число является квадратом простого, при условии, что оно - квадрат: $P_2 \approx \frac{1}{\ln(\sqrt{n})} = \frac{2}{\ln(n)}$.
в) итого, вероятность, что число является квадратом простого $P_{p^2} \approx \frac{1}{n \ln(n)}$
Вот это $\frac{1}{n}$ убьёт любую степень логарифма с ростом разрядности.
г) Однако, количество больших простых уменьшается. Количество "средних" простых, которые будут входить в квадратах уменьшается. А это снизит разрядность числа.
д) А значит $\frac{1}{n}$ убьёт степень логарифма (которая соответствует поиску по паттернам без квадрата) не сразу, а только с ростом разрядности.
е) Хорошо бы оценить, когда это произойдёт. Если это произойдет где-то в районе 40 и больше десятичных разрядов, то попробовать поискать с квадратом - есть смысл.

-- 27.04.2022, 17:50 --

3. Некоторые мысли по проверке

а) В первую очередь нужно проверять квадрат (но не, что квадрат простого). Насколько понимаю, проверка быстрая, даст хорошую фильтрацию.
б) Далее нужно проверять $p$ и $pq$, то есть как проверяли "обычно".
в) И только в последнюю очередь проверяем, что квадрат простого.

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

-- 27.04.2022, 17:56 --

вот тут:


две раскладки, которые у меня получились с квадратом. Первая получше. Вторая примечательна тем, что число с квадратом простого стоит с краю.
Квадраты простых больше 7 не расставлял, а только обозначил, где они должны быть.

[Dmitriy40]

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

б) Если брать $2^8$ по середине (в 7 или 8 позиции для 14 и в 8 позиции для 15-ки), то "раскладка" получается неоптимальной и приходится искать 10 простых и только пять $pq$.

Это не так, есть минимум два разных (без зеркальностей) варианта расстановки для 9-ти проверяемых чисел в 14-ке:
$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 1-й и 10-й, остальные достаточно произвольно (только чтобы не было 11 и 13 без квадрата);
$2^8$ в 8-й позиции, $5^2$ в 10-й, $7^2$ в первой, $3^2$ в 6-й, остальные тоже произвольно.
Во втором случае нужно не 9 пар простых в квадратах, а лишь 8, зато одиночных 5 вместо 2 и потому в первом 97 не нужно и шаг/модуль получается меньше, 4.56e73 вместо 1.43e77 для второго.

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

б) Далее нужно проверять $p$ и $pq$, то есть как проверяли "обычно".

Проверяли сначала все $p$, и лишь если совпали, то все $pq$.
Проверить на извлекаемость квадрата очень быстро, на простоту тоже быстро (хотя и медленнее), а вот на разложимость в $pq$ очень медленно.
Учитывая как редко под квадратом будет простое выгоднее проверять сначала что квадрат, потом что под ним простое, потом все $p$, потом все $pq$ (эти может даже в некотором порядке если на статистику плевать и лишь ищем цепочки).

-- 27.04.2022, 18:45 --

EUgeneUS
$5^8$ и тем более $7^8$ лишь увеличивает шаг/модуль, выгоднее снизить степень до квадрата и добавить лишнее простое в квадрате: $5^6>101^2, 7^6>103^2$. Правда при этом сильно увеличивается и общее количество вариантов паттернов, но на полный перебор по всем низинам мы давно забили, он абсолютно нереален.

[EUgeneUS]

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

Это не так, есть минимум два разных (без зеркальностей) варианта расстановки для 9-ти проверяемых чисел в 14-ке:

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

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

Учитывая как редко под квадратом будет простое выгоднее проверять сначала что квадрат, потом что под ним простое, потом все $p$, потом все $pq$ (эти может даже в некотором порядке если на статистику плевать и лишь ищем цепочки).

Нужно учесть, что если знаем, что квадрат, то проверять на простое (которое в квадрате) нужно число, которое почти в половину порядков меньше, чем другие проверяемые простые. А значит у него вероятность быть простым примерно в два раза больше, чем у других больших простых. Поэтому последовательность проверки видится такой:
1. Проверяем квадрат.
2. Проверяем все большие $p$
3. Проверяем, что квадрат - простого (если, конечно, его проверка на простоту не будет в два раза быстрее больших простых, но это вряд ли)
4. Проверяем $pq$

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

$5^8$ и тем более $7^8$ лишь увеличивает шаг/модуль, выгоднее снизить степень до квадрата и добавить лишнее простое в квадрате: $5^6>101^2, 7^6>103^2$.

Тут согласен.

-- 27.04.2022, 19:34 --

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

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

Всё равно, рост количества паттернов - это хорошо.
Так как большее количество кандидатов проверяется в "низинах", где вероятность, что число простое - больше.
До определенного предела, конечно, связанного с тем, что под каждый вариант паттерна нужно компилировать свой ускоритель, и рано или поздно это становится нереальным.