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

[Dmitriy40]

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

А Вы видели какое-то подтверждение, что в программе Hugo вообще проверяются стартовые числа?

Разумеется. Разберу подробно, на примере лога b65 (с сокращениями):

001 pcoul(12 11) -f7 -g3 -x9887353188984012120346 -b65
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.13^2 2^2.7 3 2: 498175416 / 1997815051 (600.00s)
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.13^2 2^2.7 3 2: 990528495 / 1997815051 (1200.00s)
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.13^2 2^2.7 3 2: 1485767230 / 1997815051 (1800.00s)
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.13^2 2^2.7 3 2: 1976746989 / 1997815051 (2400.00s)
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.17^2 2^2.7 3 2: 474946602 / 1168272469 (3000.00s)
...
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.293^2 2^2.7 3 2: 1155214 / 3932843 (9000.00s)
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.789517357^2 2^2.7 3 2 (9600.00s)
...
305 2^2.3 7^5 2.5^2 3 2^5 11^2 2.3^2 5.11573667319^2 2^2.7 3 2 (15600.00s)

Что здесь видим. Что перебирается позиция с 5. Что LCM остальной части равен 14642258400. Что для малых простых идёт линейный перебор ещё чего-то (сравните прогресс по числам и время). Что он идёт до 1997815051, которая равна $9887353188984012120346/LCM/13^2/2$, т.е. ровно количество шагов, пополам видимо из-за требования нечётности где-то там (у нас делилось на 6 из-за учёта и тройки). Что перебираются простые примерно до 11573667319, которое в квадрате и умноженное на 5 и 13 (потому что оставшееся неизвестным простое в первой степени никак не меньше 13) даёт 8.7e21 (т.е. видимо это ещё не последнее простое, но самое последнее в лог не попало). Но начиная с простого $\sqrt{9887353188984012120346/LCM}=821743$ шаг превышает верхний предел проверки, так что для всех остальных простых до примерно 11573667319 проверяется лишь только начальное число.

Huz в сообщении #1569074 писал(а):

I recently added a command-line option to select the strategy for choosing which position to target first; the current default strategy is "pick the position for which the remaining required tau() is the greatest". Would you suggest that a better strategy would be "pick the position for which the remaining required tau() is the smallest"? Or do you think it needs more that that?

Let's compare the positions with $5p^2q$ and $p^2qr$, for the first of them it is necessary to iterate $p$ up to $\sqrt{M/5/13}$, for the second up to $\sqrt{M/13/17}$. Yes, the second is more profitable, you are right.
I was guided by the fact that in my accelerators the speed noticeably depends on the number of positions being checked (those that are $\operatorname{numdiv}(x)=$ 6), the difference is 3-5 times for each change by 1, and then it is more profitable for me to increase the number of such positions for a linear count. And while the linear count exceeds the time of the square primes count, it is more profitable for me to use the first item.

Кстати, мои оценки (и реальный запуск) выше были сильно завышенными в части перебора простого в квадрате, можно и нужно перебирать не до $\sqrt{M/5}$ как я сделал, а до $\sqrt{M/5/13}$, в $\sqrt{13}=3.6$ раза меньше, т.е. не 30-35 минут, а лишь 10 минут, а если в паттерне осталось пустое место, то и лишь до $\sqrt{M/13/17}$, в $\sqrt{13\cdot17/5}=6.65$ раз меньше, минут 5. Получаемый выигрыш от Hugo желающие пересчитают сами.

-- 06.11.2022, 11:51 --

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

Запустил расчет паттернов LCM42688800 только с 6-ю проверяемыми числами (20 шт) до $10^{21}$ в четыре потока. И уже только это потребует несколько дней

В паттерне LCM42688800-23186745-7 должна найтись известная минимальная 11-ка, если его запустить до 1e22.

[Yadryara]

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

Паттерн b101.

 . 50p 363p 32p 16807p 18p 5p^2q 4pq 3p^2q 2p^2q .

Здесь на 1-е(в нашей записи на 5-е) место Hugo ставил квадраты простых и ограничился простыми до 6.5 миллиарда? Как была определена верхняя граница?

Время счёта в один поток.

Дмитрий, новым способом: 0.1 часа.
Hugo, по методу Hugo: 3 часа.
Дмитрий, старым способом: 3 часа.
Ахиллес, по методу Hugo: 4 часа.
Паровозик, старым способом: 11 часов.

Улучшенные программы(новый способ) пока не появились. Но не торопим.

[Dmitriy40]

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

Дмитрий, новым способом: 0.7 часа.

Быстрее:

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

Кстати, мои оценки (и реальный запуск) выше были сильно завышенными в части перебора простого в квадрате, можно и нужно перебирать не до $\sqrt{M/5}$ как я сделал, а до $\sqrt{M/5/13}$, в $\sqrt{13}=3.6$ раза меньше, т.е. не 30-35 минут, а лишь 10 минут, а если в паттерне осталось пустое место, то и лишь до $\sqrt{M/13/17}$, в $\sqrt{13\cdot17/5}=6.65$ раз меньше, минут 5. Получаемый выигрыш от Hugo желающие пересчитают сами.

-- 06.11.2022, 11:56 --

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

Здесь на 1-е(в нашей записи на 5-е) место Hugo ставил квадраты простых и ограничился простыми до 6.5 миллиарда? Как была определена верхняя граница?

Я только что это пояснил, в предыдущем сообщении, вероятно Вы его не успели изучить, посмотрите.

[Yadryara]

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

Быстрее:

Поправил. Правильно? Когда увидел, не был уверен, что время в 5 минут касается именно паттерна b101.

Самыми интересными в плане скорости и оптимизаций являются именно самые медленные паттерны, то есть та самая 8-ка паттернов с базовым шагом 554400.

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

Я только что это пояснил, в предыдущем сообщении, вероятно Вы его не успели изучить, посмотрите.

Да, я не видел и проверил b101 сам. И конечно понял, что стартовые числа у Hugo проверяются, раз уж перебираются квадраты простых до столь больших значений. И Hugo знал, где установить этот потолок.

-- 06.11.2022, 12:44 --

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

превышает верхний предел проверки, так что для всех остальных простых до примерно 11573667319 проверяется лишь только начальное число.

А если взять не 11.6 ярдов, а 20 ярдов, то начальное число обязательно превысит 1е22 ?

[Dmitriy40]

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

Поправил. Правильно? Когда увидел, не был уверен, что время в 5 минут касается именно паттерна b101.

Ну, 0.1ч или 0.2ч, зависит от паттерна, есть ли там свободное место (тогда меньшее время).
И касается всех паттернов, в которых есть хотя бы одно или свободное место (что лучше), или с простым в первой степени.
Но это только время перебора простых в квадрате, кроме него для каждого будет ещё линейный перебор ускорителями (до сотен или тысяч) и в PARI (до примерно миллиона), это тоже может быть довольно долго.
Для некоторых особо долгих, с маленьким шагом/модулем и малым количеством проверяемых мест, которые даже после подстановки одного простого в квадрате будут перебираться более 10 минут, понадобится второе доступное место для второго перебора.

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

А если взять не 11.6 ярдов, а 20 ярдов, то начальное число обязательно превысит 1е22 ?

Дык посчитайте: $p=20\cdot10^9, p^2\cdot5\cdot13=2.6\cdot10^{22}$.
Перебирать в этой позиции этого паттерна надо $p<\sqrt{9887353188984012120346/5/13}=1.233415\cdot10^{10}$ (пятёрка уже стоит в паттерне, а меньше 13 оставшееся неизвестное простое в первой степени быть не может, они все расставлены).
Поправка: не начальное число превысит порог, а само число начала цепочки гарантированно превысит порог. И на начальное число тогда совершенно наплевать.

-- 06.11.2022, 13:21 --

Ночью сварганил на коленке перебор с компиляцией на лету, прошёлся по верхам наиболее вероятных цепочек, к утру нашлись 37 десяток (минимальная на 5.3e18), но не нашлась известная минимальная 11-ка (хотя должна была!), оказалось как обычно лажанулся и немного не то компилил (первый перебор был правильным, а второй чаще всего исключал решения), нашёл глюк, исправил, перезапустил и среди первых 7-ми десяток нашёл ещё 5 новых. Девятки не считал, а восьмёрки и в лог не выводил.
Это не доказательство минимальности так как проверяю не все допустимые простые, зато каждый паттерн проверяется минут 5-10 и должен найти большинство длинных цепочек. Оценка для однократного перебора таких паттернов по прежнему даёт величину 120ч (в которых время 5 минут на перебор квадратов простых теряется) на каждый. Оценку для двухкратного перебора не делал.

-- 06.11.2022, 13:24 --

EUgeneUS, Yadryara
Думаю надо прекращать счёт выложенными SSE ускорителями, это слишком долго. Лучше считать программой Hugo, раз она вроде как уже есть под винду.
Когда (и если) доделаю компиляцию на лету, тогда и посмотрим.

[Yadryara]

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

Ночью сварганил на коленке перебор с компиляцией на лету, прошёлся по верхам наиболее вероятных цепочек, к утру нашлись 37 десяток (минимальная на 5.3e18),

Круто!! Уверен, имеются в виду именно непрерывные десятки. Покажите же хоть парочку красавиц!

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

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

Логично, ведь рекордная 11-ка может найтись.

-- 06.11.2022, 13:31 --

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

EUgeneUS, Yadryara
Думаю надо прекращать счёт выложенными SSE ускорителями, это слишком долго. Лучше считать программой Hugo, раз она вроде как уже есть под винду.

Так я уже прекратил. А программа Hugo вроде как только для 64-х разрядов.

[Dmitriy40]

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

Покажите же хоть парочку красавиц!

Пара меньших, пара вокруг 1e22 и наибольшая:
5313166666681560345: 24, 32, 6, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, valids=10, maxlen=10
171817841126312059545: 48, 96, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 8, valids=10, maxlen=10
...
8999513244521873059545: 96, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 32, 64, 32, valids=10, maxlen=10
10018217194832888520345:128, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 64, 32, 12, valids=11, maxlen=10
...
12180271618156886923545: 32, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 64, 16, 4, valids=10, maxlen=10
Несколько последних больше 1e22 так как ускорители ночью считали с фиксированным шагом и последний кусок нередко вылетал за верхний предел. Утром и это поправил, больше таких не будет.

[EUgeneUS]

Всего на сути отвлекся, а тут уже столько нового
Пока отвечу на старые вопросы:

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

Прошу Дмитрия и Евгения тоже замерить скорость для этого паттерна.

LCM14642258400-2398005945-4: end, time: 149.651s

Это до $10^{20}$

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

В каком блоге смотреть скорость Ахиллеса, надеюсь знаете...

нет, не знаю

-- 06.11.2022, 14:39 --

Сейчас у меня считаются паттерны:

/*            42688800,            41409945*/ v=[    45,     2,     1,    12,    49,    50,   363,    32,     1,    18,     5,    28,     3,     2,     1]; z=[6,2,1,6,3,6,6,6,1,6,2,0,0,0,0]; n=6; pp=Mod(41409945,42688800);\\@LCM42688800-41409945-8
/*            42688800,            39638745*/ v=[    45,    98,     1,    12,     1,    50,     3,    32,   847,    18,     5,     4,     3,     2,     1]; z=[0,6,1,6,1,6,2,6,6,6,2,3,0,0,0]; n=6; pp=Mod(39638745,42688800);\\@LCM42688800-39638745-7
/*            42688800,            38709945*/ v=[    45,    22,     1,    12,     1,    50,   147,    32,     1,    18,     5,     4,   363,    14,     1]; z=[0,0,1,6,1,6,6,6,1,6,2,3,6,0,0]; n=6; pp=Mod(38709945,42688800);\\@LCM42688800-38709945-6
/*            42688800,            34442041*/ v=[     1,     2,     3,    28,   605,    18,     1,    32,     3,    50,    49,    12,     1,     2,    45]; z=[0,0,0,0,6,6,1,6,2,6,3,6,1,2,6]; n=6; pp=Mod(34442041,42688800);\\@LCM42688800-34442041-4
/*            42688800,            30086041*/ v=[     1,    14,     3,     4,   605,    18,     1,    32,   147,    50,     1,    12,     1,     2,    45]; z=[0,0,2,3,6,6,1,6,6,6,1,6,1,0,0]; n=6; pp=Mod(30086041,42688800);\\@LCM42688800-30086041-6
/*            42688800,            29157241*/ v=[     1,     2,     3,     4,     5,    18,     7,    32,   363,    50,     1,    12,     1,    98,    45]; z=[0,0,0,3,2,6,2,6,6,6,1,6,1,6,0]; n=6; pp=Mod(29157241,42688800);\\@LCM42688800-29157241-5
/*            42688800,            23858041*/ v=[     1,     2,    33,    28,     5,    18,     1,    32,     3,    50,    49,    12,     1,   242,    45]; z=[0,0,0,6,2,6,1,6,2,6,3,6,1,6,0]; n=6; pp=Mod(23858041,42688800);\\@LCM42688800-23858041-5
/*            42688800,            23858041*/ v=[     1,     2,    33,    28,     5,    18,     1,    32,     3,    50,    49,    12,     1,   242,    45]; z=[0,0,0,0,2,6,1,6,2,6,3,6,1,6,6]; n=6; pp=Mod(23858041,42688800);\\@LCM42688800-23858041-4
/*            42688800,            23186745*/ v=[    45,   242,     1,    12,     1,    50,   147,    32,     1,    18,     5,     4,    33,    14,     1]; z=[0,6,1,6,1,6,6,6,1,6,2,3,0,0,0]; n=6; pp=Mod(23186745,42688800);\\@LCM42688800-23186745-7
/*            42688800,            23057145*/ v=[    45,    98,     1,    12,     1,    50,     3,    32,     7,    18,   605,     4,     3,     2,     1]; z=[0,6,1,6,1,6,2,6,2,6,6,3,0,0,0]; n=6; pp=Mod(23057145,42688800);\\@LCM42688800-23057145-7
/*            42688800,            19631641*/ v=[     1,     2,     3,     4,   605,    18,     7,    32,     3,    50,     1,    12,     1,    98,    45]; z=[0,0,0,3,6,6,2,6,2,6,1,6,1,6,0]; n=6; pp=Mod(19631641,42688800);\\@LCM42688800-19631641-5
/*            42688800,            19502041*/ v=[     1,    14,    33,     4,     5,    18,     1,    32,   147,    50,     1,    12,     1,   242,    45]; z=[0,0,0,3,2,6,1,6,6,6,1,6,1,6,0]; n=6; pp=Mod(19502041,42688800);\\@LCM42688800-19502041-5
/*            42688800,            18830745*/ v=[    45,   242,     1,    12,    49,    50,     3,    32,     1,    18,     5,    28,    33,     2,     1]; z=[6,6,1,6,3,6,2,6,1,6,2,0,0,0,0]; n=6; pp=Mod(18830745,42688800);\\@LCM42688800-18830745-8
/*            42688800,            18830745*/ v=[    45,   242,     1,    12,    49,    50,     3,    32,     1,    18,     5,    28,    33,     2,     1]; z=[0,6,1,6,3,6,2,6,1,6,2,6,0,0,0]; n=6; pp=Mod(18830745,42688800);\\@LCM42688800-18830745-7
/*            42688800,            13531545*/ v=[    45,    98,     1,    12,     1,    50,   363,    32,     7,    18,     5,     4,     3,     2,     1]; z=[0,6,1,6,1,6,6,6,2,6,2,3,0,0,0]; n=6; pp=Mod(13531545,42688800);\\@LCM42688800-13531545-7
/*            42688800,            12602745*/ v=[    45,     2,     1,    12,     1,    50,   147,    32,     1,    18,   605,     4,     3,    14,     1]; z=[0,0,1,6,1,6,6,6,1,6,6,3,2,0,0]; n=6; pp=Mod(12602745,42688800);\\@LCM42688800-12602745-6
/*            42688800,             8246745*/ v=[    45,     2,     1,    12,    49,    50,     3,    32,     1,    18,   605,    28,     3,     2,     1]; z=[6,2,1,6,3,6,2,6,1,6,6,0,0,0,0]; n=6; pp=Mod(8246745,42688800);\\@LCM42688800-8246745-8
/*            42688800,             3978841*/ v=[     1,    14,   363,     4,     5,    18,     1,    32,   147,    50,     1,    12,     1,    22,    45]; z=[0,0,6,3,2,6,1,6,6,6,1,6,1,0,0]; n=6; pp=Mod(3978841,42688800);\\@LCM42688800-3978841-6
/*            42688800,             3050041*/ v=[     1,     2,     3,     4,     5,    18,   847,    32,     3,    50,     1,    12,     1,    98,    45]; z=[0,0,0,3,2,6,6,6,2,6,1,6,1,6,0]; n=6; pp=Mod(3050041,42688800);\\@LCM42688800-3050041-5
/*            42688800,             1278841*/ v=[     1,     2,     3,    28,     5,    18,     1,    32,   363,    50,    49,    12,     1,     2,    45]; z=[0,0,0,0,2,6,1,6,6,6,3,6,1,2,6]; n=6; pp=Mod(1278841,42688800);\\@LCM42688800-1278841-4

В четыре потока от $0$ до $1 \cdot 10^{20}$
И ещё в четыре потока $1 \cdot 10^{20}$ до $2 \cdot 10^{20}$
За сутки просчиталось два паттерна (на первом компе, на втором запускал позже), считается третий.
Кстати, почему-то не происходит перебор всех заданных паттернов на каждом шаге (step), а каждый паттерн считается до конца заданного диапазона.

Находится много вариантов с 8-мю числами. Уже по 300с лишнем килобайт логи Так что вероятность найти 11-ку выглядит вполне большой.
10-ки находятся, в том числе и непрерывные. Их пока мало, но думаю, как только их (непрерывных десяток) количество приблизится к нескольким десяткам, то следуют ждать 11-ку
UPD: непрерывных десяток нашлась пока всего одна

-- 06.11.2022, 14:53 --

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

Думаю надо прекращать счёт выложенными SSE ускорителями, это слишком долго. Лучше считать программой Hugo, раз она вроде как уже есть под винду.
Когда (и если) доделаю компиляцию на лету, тогда и посмотрим.

Было было бы интересно посмотреть на замеры скорости программы Hugo для разных LCM и для разного количества проверяемых чисел.

[Huz]

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

Нет, в данном примере, стартовое число $31545$.

$31545+554400\cdot5841870351291= 3238732922755761945$

Здесь стартовое число конечно крошечное. $31545$ намного меньше чем $297387e13$.

Но ведь бывают и стартовые числа из интервала

$297387e13$ — $988735e16$ ?

I will guess that this calculates the value $a + bc$, where $(a, b)$ were found by the Chinese Remainder Theorem (CRT). Then if the user requested checks in the range minimum $v_n$ to maximum $v_x$ (where $v_n$ is usually 0), my program will check values of $c$ ranging from $\lceil (v_n - a)/b \rceil$ to $\lfloor (v_x - a)/b \rfloor$.

In practice, we are looking at a set of 11 numbers at the same time, and many values of $c$ do not need to be considered. In your example, I assume that $31545+554400\cdot 5841870351291= a+bc$ has had an allocation of $3^2$. But when $c \equiv 2 \pmod{3}$, we will have $3^3 \mid a + bc$ which contradicts the allocation. So we can skip this value of $c$ for all 11 numbers.

-- 06.11.2022, 13:59 --

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

т.е. ровно количество шагов, пополам видимо из-за требования нечётности где-то там

Yes: I artificially multiply the modulus for the Chinese Remainder Theorem by 2. If I do not do this, then in the position $2^5 p$ we will find $2 \mid p$.

-- 06.11.2022, 14:02 --

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

Let's compare the positions with $5p^2q$ and $p^2qr$, for the first of them it is necessary to iterate $p$ up to $\sqrt{M/5/13}$, for the second up to $\sqrt{M/13/17}$. Yes, the second is more profitable, you are right.

I didn't fully understand that. But I will try adding a simple new strategy, and do some comparisons.

[Huz]

Huz в сообщении #1569115 писал(а):

Dmitriy40 в сообщении #1569096 wrote:

Цитата:

Let's compare the positions with $5p^2q$ and $p^2qr$, for the first of them it is necessary to iterate $p$ up to $\sqrt{M/5/13}$, for the second up to $\sqrt{M/13/17}$. Yes, the second is more profitable, you are right.

I didn't fully understand that. But I will try adding a simple new strategy, and do some comparisons.

Ah, now I understand.

I tested it on a known pattern with a reduced maximum. '-j0' is the old strategy, '-j2' is the new strategy.

maximum 10^19:
-j0: recurse 11744180, walkc 1977155 (64.93s)
-j2: recurse 414, walkc 87999094 (60.35s)

maximum 10^20:
-j0: recurse 34911054, walkc 19771428 (215.13s)
-j2: recurse 62382956, walkc 19767845 (384.50s)

In the test to $10^{19}$, the new strategy decided not to recurse into this level at all, and ended up being slightly faster. When the limit is raised to $10^{20}$ it no longer does that, and it ends up taking nearly twice as long - it tests slightly fewer values (the "walkc" count shown), and (because of the extra prime) tests them faster, but the time is dominated by the extra work in recursion so it takes nearly twice as long overall.

[EUgeneUS]

Я запустил код уважаемого Хуго под Windows (спасибо Наталье за компиляцию).
На данный момент лог такой:

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850
305 3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 769807960 / 2371109213 (599.99s)
305 3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 1488205618 / 2371109213 (1199.98s)
305 3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 17^2 2.3^2 5: 2207596090 / 2371109213 (1799.98s)
305 3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 19^2 2.3^2 5: 594417594 / 1898201004 (2399.99s)
001 recover pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b1850
305 3^2.5 2 13^2 2^2.3 7^2 2.5^2 3.11^2 2^5 19^2 2.3^2 5: 1313362380 / 1898201004 (2999.99s)

Как-то можно оценить время, которое будет считаться данный паттерн до конца?

[Huz]

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

Как-то можно оценить время, которое будет считаться данный паттерн до конца?

It is difficult to estimate just from theory, particularly so early.

You will see that it is now allocating $13^2$ (in the third position) and first $17^2$ and then $19^2$ in the ninth position. Extrapolating from the timings, it has taken about 1933s to deal with $17^2$ in the ninth position. Letting $x = 9887353188984012120346$, a very rough estimate to complete all prime squares in the ninth position is $1933 \sum_{p: p \in \mathbb{P}, 17 \le p \le \sqrt{x/323}}{ p^{-2} }$ seconds. When that is complete it will allocate $p^5$ in the ninth position (which should complete very quickly) and then $p^{11}$ (which will be instant). Then it will replace $13^2$ in the third position with $17^2$, and repeat the process.

At a certain point, the allocation in the third position will be high enough that it will not need to recurse deeper, so it will no longer have an additional allocation in the ninth position. If the "gain" (the value of the "-g" option) is set correctly, it should switch at the point that recursing or not recursing take roughly the same time.

One way to estimate is to compare with one that completed before. I have one here (b1627) in which the log starts like this:

305 2 11^2 2^2.3 13^2 2.5^2 3.7^2 2^5 17^2 2.3^2 5 2^2: 572495341 / 2371109213 (600.00s)
305 2 11^2 2^2.3 13^2 2.5^2 3.7^2 2^5 17^2 2.3^2 5 2^2: 1134375603 / 2371109213 (1200.00s)
305 2 11^2 2^2.3 13^2 2.5^2 3.7^2 2^5 17^2 2.3^2 5 2^2: 1703962125 / 2371109213 (1800.00s)
305 2 11^2 2^2.3 13^2 2.5^2 3.7^2 2^5 17^2 2.3^2 5 2^2: 2263291783 / 2371109213 (2400.00s)
305 2 11^2 2^2.3 13^2 2.5^2 3.7^2 2^5 19^2 2.3^2 5 2^2: 455841314 / 1898201004 (3000.00s)

That one completed in a total of 236691.34s (65.7 hours), and the extract above suggests the first part over $17^2$ took 2514s. So if the two are similar enough to compare, your pattern may take approximately $236691.34s \cdot 1933/2514$, or about 50.5 hours total.

[EUgeneUS]

Huz
Thank you very much.
I will try to count this pattern to the end. But this will not be a continuous count.

-- 06.11.2022, 21:35 --

FYI. Calculating the same pattern using Dmitry's technique gives speed $2.5 \cdot 10^{20}$ in about 60000 sec. But this is on a different computer, so the comparison is only approximate.

[EUgeneUS]

Huz
Please tell me, is it possible to run your code so that when it starts with patterns for a chain of length 11, it outputs to the log found continuous chains of length from 8 to 11?

This is needed to process overlapping patterns.
The idea is this: run your code (for the overlapping pattern) to find chains of length from 8 (9, 10) to 11. There will be a lot of them, tens, maybe hundreds per pattern.
And then these chains are additionally checked to see if they grow to 11.

[Yadryara]

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

Самыми интересными в плане скорости и оптимизаций являются именно самые медленные паттерны, то есть та самая 8-ка паттернов с базовым шагом 554400.

Эти 8 паттернов из серии 554400-3. А я всё-таки часов 16 считал один паттерн из серии 554400-4. То есть всё же более перспективный, чем паттерны с 3 проверяемыми местами. Так что единственная непрерывная 7-ка на крошечном отрезке в 37е16 из 692000е16 даже несколько выше моих ожиданий.

Таким темпом Паровозику пришлось бы считать паттерн b085 никак не меньше 40 лет.

А самые перспективные паттерны содержат не 3 и не 4, а 7 проверяемых мест. Таких всего 80 штук из 1044.

Dmitriy40, сколько таких паттернов-7 Вы уже полностью проверили и сколько 10-к(обычных и непрерывных) нашлось?

Под обычными 10-ками я имею в виду именно 10 из 11 подряд, а не 10 из 15-ти.