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

[VAL]

Очередная стайка:

588173729068398663517057984923122898070777243035470538651640
208084583619625395508269241313948936178599101160661217179640
72977502298372125308936997157311630685467656307035792590840

[wrest]

У меня вопрос по паттерностроению. Вот мы стараемся набить паттерн "необязательными" числами поменьше. А почему? Ведь дальше, при просеивании, мы делим получившиеся в результате числа цепочек на "внедрённые" нами через КТО заранее известные множители. Так что их величина нам никак не мешает...

[Yadryara]

wrest в сообщении #1724475 писал(а):

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

Вроде совсем недавно писал: для уменьшения шага.

Вы начальные, скажем 6 страниц темы, всё-таки прочитали?

[wrest]

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

Вы начальные, скажем 6 страниц темы, всё-таки прочитали?

Вероятно, да.

-- добавлено через 1 минуту --

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

Вроде совсем недавно писал: для уменьшения шага.

А зачем уменьшать шаг?

[Yadryara]

Чтобы количество проверок на определённый интервал было максимальным. При прочих равных чем больше попыток найти цепочку в одном и том же интервале, тем больше вероятность её таки найти.

[wrest]

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

При прочих равных чем больше попыток найти цепочку в одном и том же интервале,

В интервале чего?
Мы формируем числа вида $P\cdot R$, где $P$ - произведение чисел из "паттерна", $R$ - произведение "случайных" чисел. Нас, при проверке, интересует только количество делителей в $R$, которое обозначали t_R.

[Yadryara]

wrest в сообщении #1724484 писал(а):

В интервале чего?

Ну как чего? Натурального ряда. Я же его постоянно указываю в статистике:

6-поточный счёт

   Серия    Произв.      Обсч.   2^   n от    Найдено     Время   Милсек/   Скорость
            простые      патт.        0 до   D(192,12)   секунд   паттерн   корт/сут

0-0-11-1   5!3!7!A!     21180    19   1e68         105    94713      4472         96
0-0-12-0   5!3!7!B!              19   1e70
...
1-0-11-0   5!3!7!B!**  251980    20   1e74         107   110021       437         84

Сейчас вот считаю серию 0-0-12-0. Интервал от 0 до 1e70. Характерная длина чисел — 70-значные. Их намного больше.

И кстати только что обнаружил любопытный прецедент, которого давно ждал. Я искал 12-ки, но на всякий случай проверял по всему полю. И вот нашлась 70-значная не просто 12-ка, но и 13-ка. То есть на соседнем с полосой паттерна месте как бы сами собой собрались 192 делителя:

3881611711157569542427565654057320842321904423390192428232795177056245 1111111111111   1   1   1   16

[wrest]

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

Характерная длина чисел — 70-значные.

Ok, но 6-7 знаков мы туда вставили сами, мы их знаем. Остаётся около 64.

-- добавлено через 1 минуту --

Dmitriy40
Почему бы не делать такие паттерны, что t_R=2 ? Их ведь проверять легче всего. Никакой факторизации, только проверка на простоту

[Yadryara]

wrest в сообщении #1724492 писал(а):

Ok, но 6-7 знаков мы туда вставили сами, мы их знаем. Остаётся около 64.

Как недавно было посчитано для 74-значных n, средняя длина частных меньше 66. Можно и для этих паттернов посчитать, но полагаю что в среднем тоже около 8 знаков теряется. Может чуть меньше теряется. Но главное что ещё разброс неслабый, вы же видели списки частных, то есть не 6-7 знаков теряется и не 7-8, а где-то 4-12.

wrest в сообщении #1724492 писал(а):

Почему бы не делать такие паттерны, что t_R=2 ? Их ведь проверять легче всего. Никакой факторизации,

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

Вот, кстати, на начальных страницах темы Дмитрий был не уверен почему надо брать именно 11 простых, а не 12-15. Почитайте, это недалеко от начала. Могу ссылки поискать.

[wrest]

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

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

Вопросы о личностях игнорирую.

[Yadryara]

wrest, а я не игнорирую.

D(12,15) не самая сложная цепочка. Почему нужно расставить все простые в квадратах до 37 включительно и искать 11 простых?

Потому что если заменить 37 на 41, то шаг вырастет почти на 23%.
И что? А то, что проверок на тот же интервал будет пропорционально меньше.

Ну и ладно, не найдём, так поищем повыше, среди бо́льших чисел. Да, там простых поменьше, но ведь не сильно же убывает их количество.

Сильно, потому что их надо найти аж 11 штук. Вероятность надо возводить в 11-ю степень.

[wrest]

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

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

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

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

Сильно, потому что их надо найти аж 11 штук. Вероятность надо возводить в 11-ю степень.

Ну это эмоциональные оценки, а как это будет влиять на вероятность нахождения цепочки не на единицу цепочки, а на единицу времени?

[EUgeneUS]

wrest в сообщении #1724475 писал(а):

У меня вопрос по паттерностроению. Вот мы стараемся набить паттерн "необязательными" числами поменьше. А почему? Ведь дальше, при просеивании, мы делим получившиеся в результате числа цепочек на "внедрённые" нами через КТО заранее известные множители. Так что их величина нам никак не мешает...

Пусть ищем $D(12,15)$
И в какой-то позиции у нас появилось $p^2 q$, мы его хотим превратить в $p$ путем подстановки в эту позицию малого необязательного простого в квадрате.
Подставляем $37^2$ (пусть это первое свободное простое).
Остаток от деления на числа в паттерне в этой позиции не изменится. А в остальных 14-и он вырастет в $37^2$.
Тогда вероятность, что остальные 14 позиций будут верными уменьшится в $\ln (37^2)^{14} \approx 100$ раз. Но это окупается увеличением вероятности при переходе от $p^2 q \to p$.

Теперь заменяем $37^2 \to 41^2$.
Вероятность уменьшится в $\ln (\frac{41^2}{37^2})^{14} \approx 2.9$ раза. А это уменьшение вероятности уже ничем не окупается.
Выше речь про вероятности найти цепочку за одну проверку.

-- добавлено через 10 минут --

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

1. Зафиксируем максимальную величину чисел в цепочке.
2. И будем искать до неё для каждой расстановки необязательных простых.
3. Тогда, если увеличиваем подставляемые необязательные простые в квадратах, у нас числа всё равно ограничены, и вероятность не падает. Но для таких расстановок уменьшается количество итераций.

Например в $D(12,15)$ подставляем 6 квадратов необязательных простых (от 17 до 37).
Но можем на эти места подставлять не 6 наименьших свободных, а 12 (например), тогда уменьшение количества итераторов (при подстановки больших квадратов) будет несколько компенсировано огромным ($C^6_{12}$) количеством подстановок.

Я так пробовал улучшить известную цепочку на 24 делителя. Но не сработала эта метода - улучшенная в 1.5 раза цепочка не нашлась

[wrest]

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

Остаток от деления на числа в паттерне в этой позиции не изменится. А в остальных 14-и он вырастет в $37^2$.
Тогда вероятность, что остальные 14 позиций будут верными уменьшится в $\ln (37^2)^{14} \approx 100$ раз.

Мой вопрос был -- а если скорость нашей проверки цепочек, при этом, увеличится в 200 раз?
Для того, чтобы понять попалось нам pq или pqr, надо найти какой-нибудь множитель и проверить его и/или остаток на простоту. А для того, чтобы понять попалось ли нам простое, надо только проверить его на простоту.

Так вот, в той небольшой движухе где я немного прикоснулся к реальному поиску D(48,21) постфактум, оказалось что при всех алгоритмических улучшениях и оптимизациях которые пришли в голову, нужно делать примерно 1,1 проверок на простоту на каждую цепочку. На миллион цепочек -- миллион с небольшим проверок. И это при том, что делалось ещё и пробное деление на малые простые (в среднем кажется 8 на число, т.е. 160 на цепочку), ну и другие операции, типа подсчёта делителей и т.п. И несколько (на миллион) цепочек доходили до полной факторизации, что заметно (не сильно, но почувствовать можно) замедляло процесс.

[Dmitriy40]

wrest в сообщении #1724492 писал(а):

Почему бы не делать такие паттерны, что t_R=2 ? Их ведь проверять легче всего. Никакой факторизации, только проверка на простоту

Так и делается для больших чисел, 150+ знаков, факторизация которых слишком долгая.
Но ценой является резкое уменьшение проверяемых вариантов - ведь на каждом месте вместо $\pi(\sqrt{n})$ простых (для варианта pq) мы проверяем лишь одно конкретное.
Плюс разложение p где-то втрое/вчетверо менее вероятно чем разложение pq (и тем более pqr). Т.е. тоже придётся проверять больше.
Плюс увеличивается шаг, а значит или уменьшается количество кандидатов в заданном интервале (и соответственно вероятность найти решение) или числа становятся заметно больше и падает частота простых (и тоже соответственно вероятность найти решение).
А для длинных цепочек всё ещё возводится в степень длины и получается совсем тухло.
В итоге, пока факторизация хоть как-то работает, выгоднее искать цепочки с pqr, ну или хоть pq, но не p.

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


Вы же сами можете проверить: возьмите любой паттерн где находятся несколько десятков цепочек за разумное время, расставьте там дополнительные простые чтобы в каждом месте стало $t_R=2$, а после проверки на простые до 2^20 (если попалось - цепочка сразу не подходит, это быстрее чем ispseudoprime) сразу делайте ispseudoprime от частного. И сравните сколько цепочек будет находиться за то же время.