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

[wrest]

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

Обсчитано паттернов. Из 3!3!5!5! то есть из $6\cdot6\cdot120\cdot120=518400$ возможных интересующих паттернов, обсчитано лишь 180 штук.

Что значит «обсчитан паттерн»?

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

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

То есть из этих 1240 найденных цепочек длиной не меньше 7, подавляющее большинство — 39-значные. Некоторые меньше.

То есть проверены все n от 0 до 10^39? Или что?

[Yadryara]

Ну вот у вас была функция, которая как раз обсчитывала один паттерн. Вы любили считать по 100 тысяч разных i, чтобы получать разные n.

В данном случае я считал по 34230 разных i, чтобы получать разные n в пределах от 0 до $10^{39}$.

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

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

То есть проверены все n от 0 до 10^39?

Да. Для каждого из 180 паттернов.

[wrest]

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

В данном случае я считал по 34230 разных i, чтобы получать разные n в пределах от 0 до $10^{39}$.

Этого я не понимаю. Откуда взялись 34230, как это понять из таблицы и как можно получить разные n от 0 до 10^39 в этих условиях? Мутно как-то.

[Yadryara]

UPD. Не туда посмотрел, не 34230, а 51090.

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

Откуда взялись 34230, как это понять из таблицы и как можно получить разные n от 0 до 10^39 в этих условиях?

Но это и необязательно понимать из таблицы. Главное что проверены все кандидаты от 0 до 10^39. Как неоднократно говорил, для заказчика удобно смотреть именно на n, то есть на итоговый результат, а не на количество проверок i.

Если n = n0 + mi, то зная шаг m, мы ведь можем посчитать сколько нужно сделать шагов, чтобы покрыть все n от 0 до 10^39 ? Конечно можем. Шаг ведь мы знаем из паттерна.

В данном случае m = 19573572700666034170605542286028800.

Значит нужно сделать, грубо говоря,

5109 шагов, чтобы проверить все n от 0 до 10^38;
51090 шагов, чтобы проверить все n от 0 до 10^39;
510900 шагов, чтобы проверить все n от 0 до 10^40;
...

[Yadryara]

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

Мутно как-то.

А я вот считаю наоборот. Когда вы говорите, что проверили 100 тысяч i, то это как раз мутно, а вот когда я говорю, что проверил все n от 0 до 1e39 — это конкретно.

На данный момент осталось ещё что-то непонятное для вас в таблице?

[wrest]

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

100 тысяч i, то это как раз мутно,

Это 10^5 проверенных цепочек.

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

Шаг ведь мы знаем из паттерна.

Но не из таблицы.

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

На данный момент осталось ещё что-то непонятное для вас в таблице?

Не знаю, посмотрю на следующую таблицу.

[Dmitriy40]

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

Это 10^5 проверенных цепочек.

Это непонятно: что называть цепочкой? Что называть её проверкой? Удвоение (утроение, ушестерение, у-30-ение) шага считать проверкой или нет? Непонятно. Выше (и в соседней теме) много раз считали то так, то эдак.

А вот когда говорится что проверены n с 0 до 10^39 - это понятно. Независимо от метода проверки, просто проверены все возможные цепочки в этом диапазоне и всё. Оптимальным способом, не оптимальным - дело другое.

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

На самом деле для разных целей можно пользоваться и тем и другим способом.
Для поиска цепочек удобнее диапазон по n. Просто по человечески удобнее. И независим от методов проверки, что безусловно плюс.
А для сравнения скоростей факторизации удобнее среднее время на одну цепочку (или цепочек в секунду) после предварительной фильтрации (которая тоже может быть очень разной). Но придётся точно обговаривать какие именно цепочки поступают на вход тестируемого этапа.
Мне метод по n нравится намного больше из-за своей универсальности (не всегда интересна скорость отдельных этапов, важнее общая скорость, а её удобнее мерить по n, а не по i с m).

[Yadryara]

Ну вот для 8-к картина изменилась. Серия 0-1 теперь уже не на 2-м, а на 3-м месте по средней скорости нахождения.

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

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

0-0- 7-1   3!2!6!6!     180   17   1e44       271       736      4085      31841
0-0- 8-0   3!2!6!7!     180   17   1e46       524       954      5299      47463
0-1- 7-0   3!2!6!7!*    180   17   1e48       448       887      4927      43647
1-0- 7-0   3!2!6!7!**   180   18   1e50       160       283      1567      49011

[Yadryara]

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

Это 10^5 проверенных цепочек.

А величина-то какая у этих цепочек? Или считаете что это несущественно?

А ведь для программиста ещё как существенно, ведь от этого алгоритм зависит, стратегия и тактика.

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

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

tau_R = [4, 4, 4, 4, 4, 4]

Ну вот видите, какая скукота. Потому что числа n маленькие и обгон ещё не состоялся: вы обычно берёте koli не больше 1e5, так что n всегда меньше 1е18, а частные ещё меньше.

Ну а если взять i больше 1e20, то все частные, видимо перевалят за 1e30, обгон состоится и тогда снова будет скукота, ибо по вашему критерию будет: tau_R = [8, 8, 8, 8, 8, 8].

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

А дальше, обычно за границей тех чисел, с которыми мы работаем, будет и tau_R = [16, 16, 16, 16, 16, 16]

А вот при каких числах будут лидировать 4-ки, при каких 8-ки, а при каких 16-ки, какие будут соотношения между ними, мы и пытались выяснить, начиная с 14-й страницы темы быстрых программ.

[wrest]

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

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

У меня как раз там всё ясно написано (ну, как мне кажется)
Смотрите, пост где вы пишете что надо предполагать:

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

СИСТЕМА #1 | n0=2014230969373 | m=4660507051200 | log10m=12.67
tau_R = [4, 4, 4, 4, 4, 4]
Проверено: 100001 | Полных: 125 | Плотность: 1.250 e-3

В таблице с результатами даны n0 и m, так что гадать как раз не надо. Даже написано что в десятичной записи m имеем 13 цифр (log10m=12.67). "Проверено 100001" (=10^5), то есть у последнего из проверенных n имеем 13+5=18 цифр в десятичной записи.
Ну и вы там пишете то же самое:

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

Потому что числа n маленькие и обгон ещё не состоялся: вы обычно берёте koli не больше 1e5, так что n всегда меньше 1е18, а частные ещё меньше.

А в тексте перед таблицей дан и сам паттерн.
Что же там надо «предполагать»?

[Yadryara]

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

Что же там надо «предполагать»?

Диапазон по n не был указан явно. Какие именно i брались, не было указано явно.

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

Проверено: 100001

Не указано явно, какие i брались, указано сколько. И я именно что предположил, что от 0 до 10000. Вы могли бы взять, например, от 990000 до 1000000, это как раз ровно 10001 штука. Или какие-то ещё.

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

у последнего из проверенных n имеем 13+5=18 цифр в десятичной записи.

На всякий случай: количество цифр в десятичной записи, это необязательно указание с точностью до порядка, потому что и 1e17 это 18-значное число и 9e17 это тоже 18-значное число.

[wrest]

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

Не указано явно, какие i брались, указано сколько. И я именно что предположил, что от 0 до 10000. Вы могли бы взять, например, от 990000 до 1000000, это как раз ровно 10001 штука. Или какие-то ещё.

А, ну это да, согласен. Надо было указать.

[Yadryara]

Ende
Оффтоп по поводу одного из участников темы удален.

9-ки и 10-ки посчитал. Серию 0-1 скоро, видимо, можно будет списать со счётов.

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

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

0-0- 8-1   4!3!6!6!     432   16   1e49       165      1557      3603       9159
0-0- 8-1   4!3!6!6!     432   17   1e49       165      1454      3364       9811
0-0- 8-1   4!3!6!6!     432   18   1e49       166      1535      3552       9347

0-0- 9-0   4!3!6!7!     432   16   1e51       209      1816      4203       9946
0-0- 9-0   4!3!6!7!     432   17   1e51       209      1703      3941      10605
0-0- 9-0   4!3!6!7!     432   18   1e51       209      1646      3809      10975
0-0- 9-0   4!3!6!7!     432   19   1e51       209      1878      4347       9616

0-1- 8-0   4!3!6!7!*    432   16   1e53       161      1412      3267       9855
0-1- 8-0   4!3!6!7!*    432   17   1e53       161      1241      2871      11217
0-1- 8-0   4!3!6!7!*    432   18   1e53       161      1278      2958      10886

1-0- 8-0   4!3!6!7!**   432   17   1e55      (162)    (1060)      736      13205*
1-0- 8-0   4!3!6!7!**  1440   18   1e55       162       961       667      14570
1-0- 8-0   4!3!6!7!**  1440   19   1e55       162       977       678      14340


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

0-0- 9-1   4!4!7!7!     288   17   1e55       (104)    (3529)     4084       2546*
0-0- 9-1   4!4!7!8!     864   18   1e55        104      3386      3918       2654
0-0- 9-1   4!4!7!7!     288   19   1e55       (104)    (3654)     4229       2459*

0-0-10-0   4!4!7!8!     288   17   1e57       (105)    (3421)     3959       2652*
0-0-10-0   4!4!7!8!     864   18   1e57        105      3196      3699       2839
0-0-10-0   4!4!7!8!     288   19   1e57       (105)    (3361)     3889       2699*

0-1- 9-0   4!4!7!8!*    288   17   1e59       (160)    (5159)     2559       2680*
0-1- 9-0   4!4!7!8!*   2016   18   1e59        160      5049      2504       2738
0-1- 9-0   4!4!7!8!*    288   19   1e59       (160)    (4957)     2459       2789*

1-0- 9-0   4!4!7!8!**   720   18   1e61       (104)    (2458)      569       3656*
1-0- 9-0   4!4!7!8!**  4320   19   1e61        104      2374       549       3786
1-0- 9-0   4!4!7!8!**   720   20   1e61       (104)    (2458)      569       3656*

* — применялась экстраполяция

[Yadryara]

С 11-ками уже дольно сильная болтанка происходит. Пока не буду показывать. Это, видимо, из-за довольно сильного увеличения частных вслед за n.

Главное что серия с одним простым пока опять выиграла по скорости нахождения:

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

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

D(192, 7)   1-0- 6-0         360   17   1e43      1464       522      1449     242526
D(192, 8)   1-0- 7-0         180   18   1e50       160       283      1567      49011
D(192, 9)   1-0- 8-0        1440   18   1e55       162       961       667      14570
D(192,10)   1-0- 9-0        4320   19   1e61       104      2374       549       3786
D(192,11)   1-0-10-0       52800   19   1e66       100      8784       166        984

Свыше 900 кортежей в сутки против 600-700 для трёх других серий.

Похоже, что надо уже вплотную заниматься 10-й фильтрацией. Занимался.
В алгоритме Полларда менял параметр с (Дмитрий вроде называл его seed). Некоторые новые разложения находились.

Решил попробовать другой алгоритм. Но вот Квен пока не смог мне написать корректно работающую функцию для ЕСМ. Упростил задачу: бросать поиск делителя если кандидат превышает $10^{12}$.

Самая короткая попытка реализации:

ecm_fast_capped(cha, max_size = 10^12, tries = 15, timeout_sec = 1) = {
  \\ B1=10000 покрывает факторы до ~10^12 с вероятностью >90%
  my(B1 = 10000);
  
  alarm(timeout_sec, return(1)); \\ Жёсткий таймаут на весь поиск
  
  for(t = 1, tries,
    my(f = ellfacteur(cha, 0, B1)); \\ Stage 1 ECM, возвращает первый найденный фактор
    if (f && f < cha,
      if (f <= max_size, return(f)); \\ Нашли маленький → возвращаем
      \\ Если фактор > max_size, пропускаем эту кривую
    );
  );
  return(1); \\ Подходящий делитель не найден
}

Или это опять надо в быстрые программы переезжать...

[VAL]

Дрофы со 134-й по 138-ю:

502113462781616164441358559282529124317907369228983131752440
662798633046787266501459021524959413081980608247014048155640
688167383630776343466565888932604207579259196732448496744440
468504024044479492376163373577143668220521032605045911963640
502487899775756907568193780790312176375973642295477540866040

Последняя интересна тем, что является корректной цепочкой D(192,14)
Среди 64-х дроф, найденных в 2022-2023 годах таких было целых 12. А в новейшей истории - это первая.

Сделаю прогноз:
D(192, 15) будет найдена в текущем месяце.