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

[wrest]

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

Смотрите какая статистика по фактически и предсказанию, для интервала 1e5 начиная с:

Да, убедительно.

[EUgeneUS]

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

Чего голову-то морочить?

В третий раз повторяю - идите к чёрту.

-- 18.04.2026, 20:41 --

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

Хорошо. Но странно, что мы видим не случайные флуктуации, а плавное изменение.

Ничего странного.
Где-то в начале "скакануло" значение, а потом со сбором статистики влияние этого скачка плавно уменьшается.

[wrest]

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

1. Либо Вам нужно\хочется разобраться, как строятся паттерны.
Тогда лучше это сделать "руками", хотя бы несколько раз.

Ну что ж. На примере 24 делителей, выяснилось что внедрять делители в паттерн надо так, чтобы не хватало (ожидалось) pq (4 делителя) или pqr (8 делителей) Тогда шедевральные паттерны и попрут косяками.
Попутно пришлось постичь расстановку мелких простых (которые меньше или равны длине цепочки).
Максимум по одному месту это для 24 делителей частота попадания 36% Тогда "идеальный" паттерн будет давать около (0,36)^6~200 цепочек на 100 000. Возможен ли такой паттерн? Это вопрос, однако.
Наблюдаемые частоты были такие (по остаточному numdiv, т.е. которое должно возникнуть случайно):
t_R=2 -> частота ~6% t_R=3 частота 1,5% t_R=4 частота ~30% (но разброс от 17 до 36) t_R=6 -> частота ~1,5% t_R=8 частота 26% Поэтому всё, кроме t_R=4 и t_R=8 выкидываем в топку.
Полагаю, это будет справедливым и для другого количества желаемых делителей. Но это не точно.

[Yadryara]

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

На примере 24 делителей, выяснилось что внедрять делители в паттерн надо так, чтобы не хватало (ожидалось) pq (4 делителя) или pqr (8 делителей)

Я тоже не всегда понимаю когда вы шутите, а когда говорите серьёзно.

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

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

В первой колонке примерное значение разлагаемых чисел, во второй — количество чисел из миллиона, не имеющих простых делителей меньше чем 67. А дальше как раз доли 2, 4, 8 и 16 делителей, для которых самые популярные сборки p, pq, pqr и pqrs соответственно.

(Таблица)

10^       1e6         2       4       8      16

   8   131593       413     492      92       0
   9   131596       364     495     133       4
  10   131591       330     487     169      11
  11   131587       299     479     198      21
  12   131575       277     464     222      33
  13   131586       253     457     242      44
  14   131610       236     442     257      57
  15   131577       220     431     273      68
  16   131611       206     419     283      80
  17   131604       193     407     293      91
  18   131579       182     397     301     101
  19   131593       174     387     304     111
  20   131590       166     375     310     120
  21   131597       157     366     315     128
  22   131580       151     355     318     138
  23   131588       144     349     319     143
  24   131572       138     341     322     151
  25   131573       135     329     323     159
  26   131583       127     325     323     165
  27   131581       123     319     324     170
  28   131573       118     311     324     176
  29   131597       115     306     323     180
  30   131592       110     299     325     185
  31   131587       108     293     322     191
  32   131593       104     287     321     196
  33   131580       101     282     322     198
  34   131571        96     278     319     202
  35   131600        94     272     319     205
  36   131596        92     266     321     207
  37   131589        89     262     319     212
  38   131601        88     258     316     213
  39   131582        86     254     314     216
  40   131600        83     250     312     218
  41   131593        80     244     315     219
  42   131577        77     244     312     224
  43   131565        77     236     309     227
  44   131564        74     234     307     228
  45   131590        73     232     305     230
  46   131585        72     229     302     231
  47   131595        72     223     301     233
  48   131571        68     221     300     236
  49   131576        68     220     298     235
  50   131574        67     217     296     236
  51   131585        65     213     295     240
  52   131581        64     210     295     238
  53   131608        61     207     294     241
  54   131575        62     204     292     241
  55   131598        59     201     290     244
  56   131585        59     198     291     242
  57   131578        58     196     288     245
  58   131606        57     195     284     244
  59   131590        55     191     285     247

Как видим, примерно на высоте 1e27 8 делителей совершают обгон 4 делителей и дальше уже не уступают первое место. Но позже уступят.

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

Вот поэтому упрощенная стратегия обычно сводится к максимизации pqr. Обратили внимание, что у меня огромное количество именно pqr в сериях?

Ну вот например из последней статистики:

Серия            2^      Комплектов       Счёт     Найдено      Время   Сред. скорость
                          посчитано    от 0 до    D(96,11)     секунд   D(96,11)/сутки

0-0-11-0-0-5!    15      3! * 7! 24       1e41         161      11418             1218
0-0-11-0-0-5!    16      3! * 7! 24       1e41         161      10276             1354
0-0-11-0-0-5!    17      3! * 7! 24       1e41         161      10533             1321
0-0-11-0-0-5!    18      3! * 7! 24       1e41         161      10565             1317

Видите? Запись 0-0-11-0-0 в первой колонке означает что количество p — 0, pq — 0, pqr — 11, pqrs — 0, pqrst — 0.

Но... не всё так просто. Напомню, что пока серия 1-0-10-0-0 заметно выигрывает.

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

Возможен ли такой паттерн? Это вопрос, однако.

Вот поэтому, чтобы ответить на него, я вам и предлагал попросту перебрать все варианты с помощью вложенных циклов.

[EUgeneUS]

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

t_R=2 -> частота ~6% t_R=3 частота 1,5% t_R=4 частота ~30% (но разброс от 17 до 36) t_R=6 -> частота ~1,5% t_R=8 частота 26% Поэтому всё, кроме t_R=4 и t_R=8 выкидываем в топку.
Полагаю, это будет справедливым и для другого количества желаемых делителей. Но это не точно.

К сожалению, это не является справедливым для другого количества желаемых делителей и даже для более длинных цепочек с тем же количеством делителей.

1. $t_R=3$, означает ожидаемое число $p^2$. Вероятность его для больших чисел будет ещё меньше (сильно меньше) и оно всегда "выкидывается в топку", это действительно так.
Хотя могут быть нюансы

2. $t_R=6$, означает ожидаемое число $pq^2$. Вероятность его для больших чисел будет ещё меньше (сильно меньше), но оно не всегда "выкидывается в топку". Так как его можно "исправить" - добавить в паттерн в это место квадрат небольшого необязательного простого и получить ожидаемое число $p$.
Этот приём (подстановка необязательных простых в квадратах или в других нужных степенях) используется повсеместно, ибо квадратов обязательных простых (которые меньше длины цепочки) как правило не хватает, чтобы расставить нужное количество квадратов во все позиции паттерна.

3. К сожалению, для многих цепочек нельзя "выкинуть в топку" $t_R=2$.

Вопросы для самоконтроля и окончательного постижения дзена.
1. Почему паттерн, обеспечивающий максимальную вероятность, не всегда обеспечивает минимальное время расчета?
2. Почему в некоторых случаях в паттерн выгодно добавлять $3^5$ или даже $3^8$, хотя это и необязательно? А вот $5^5$ и $5^8$ добавлять невыгодно (почему?).

[Yadryara]

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

2. Почему в некоторых случаях в паттерн выгодно добавлять $3^5$ или даже $3^8$, хотя это и необязательно? А вот $5^5$ и $5^8$ добавлять невыгодно (почему?).

Опять человеку голову морочите.

wresta интересовали цепочки длиной 20 — 30. То есть те, для которых количество делителей 24, 48 или 96.

Так что выбор может быть не между $3^5$ или $3^8$, а между $3^2$ или $3^5$ или $3^{11}$.

и не между $5^5$ или $5^8$, а между $5^2$ или $5^5$ или $5^{11}$

Ну и конечно между $2^5$ или $2^{11}$.

[EUgeneUS]

42
72

[wrest]

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

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

Да, это следующий уровень соображений. Пока не знаю. Но знаю что на том где тренировался я, основной потребитель времени при отсеве цепочек - проверка на простоту. Получалось примерно по одной на цепочку.
То есть при равных вероятностях, надо брать паттерны, склонные к переполнению делителями, т.к. переполнение легче детектировать чем недобор.

[EUgeneUS]

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

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

Нет.
1. Проверка числа на простоту выполняется сильно (на порядки) быстрее, чем факторизация.
Поэтому, например, цепочка в паттерне с одним ожидаемым простым может (но не обязана ) найтись заметно быстрее, чем в паттерне без простых. Хотя вероятность на одну проверку цепочек будет больше в паттерне без простых.

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

А что по второму вопросу, про степени?

[Yadryara]

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

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

Посчитал не шибко высоко для первого свободного простого 53 — 71. Отклонения от показанной статистики незначительные. Чем больше первое свободное простое, тем позже происходит обгон 8-ю делителями 4-х делителей:

first
free
prime    10^       1e6         2       4       8      16

   53     25    138684       128     319     323     168
   59     25    136068       130     323     323     164
   61     26    133774       125     322     323     168
   67     27    131581       123     319     324     170
   71     27    129629       125     321     323     168

[wrest]

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

1. Проверка числа на простоту выполняется сильно (на порядки) быстрее, чем факторизация.

Тут есть нюансы. В последних достижениях по алгоритмам проверки цепочек, сперва идёт очень эффективная проверка по табличным простым до 2^12..2^24 (подбирается экспериментально). Эффективная для длинных цепочек, т.к. проверяется сразу вся цепочка, по остатку от деления первого числа в цепочке на проверяемое простое. И эффективная потому что там почти нет длинной арифметики. И вот на этом этапе в среднем цепочка бракуется на первом-втором десятке простых. Но через этот фильтр проходят цепочки с недоборами, и там уже возможна факторизация относитльно больших чтобы понять, что там засело pq или pqr. До факторизации доходит что-то около 2..5 чисел на миллион.

-- 20.04.2026, 09:16 --

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

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

А это не так-то и легко, потому что "тяжелые" методы типа MPQS и ECM не ищут делители по возрастанию.
Ну и чтобы вовремя остановиться, надо (в случае pari/gp) подлезать в глубины движка факторизации, ччто пока что не принесло заметных успехов (ддвижок справляется лучше если его не трогать изнутри).

[Yadryara]

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

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

И вы регулярно в этом убеждаетесь, когда ищете цепочки? Стандартная проверка по предпростым, как выше отметил wrest, заканчивается в районе $2^{20}$, что обычно на много-много порядков меньше чем корень из частного, пусть даже это частное от частного.

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

В последних достижениях по алгоритмам проверки цепочек, сперва идёт очень эффективная проверка по табличным простым до 2^12..2^24 (подбирается экспериментально).

Давайте всё-таки уточню. Это не сперва, это обычно 4-я фильтрация. А если паттерн с одним простым, то 6-я.

[wrest]

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

Давайте всё-таки уточню. Это не сперва, это обычно 4-я фильтрация.

Это у вас 4-я. А у меня "сперва" (если отключить "терапевтику", в которой я всё ещё не уверен на 100%).

[VAL]

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

703447476160619959255599255377931888872808502039663703144440
342995966295284004706550940532228368621500497053251391694840
430595019761663843251163393969582183358459671135034025371640

[EUgeneUS]

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

Это у вас 4-я. А у меня "сперва" (если отключить "терапевтику", в которой я всё ещё не уверен на 100%).

Как Вы могли такое напсать!?
Это же только у Yadryara правильная нумерация и правильная терминология.
Остальные должны извиниться и принять.

Что-то его несёт в последнее время.
Вот из сегодняшнего:

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

wresta интересовали цепочки длиной 20 — 30. То есть те, для которых количество делителей 24, 48 или 96.

Исходя из какой телепатии, он решил, что Вас интересуют только эти цепочки - мне неведомо. Также мне неведомо, почему это мне должно быть ведомо.
И наконец, для $k=72$ (и кучи других), применимы восьмые степени, а ограничение сверху на длину цепочки более 20, для 72 делителей - 31.
То есть его вот это "То есть те" - это чушь собачья.

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