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

[Dmitriy40]

Я запускал счёт паттернов без 5-х степеней и без искомых простых в квадратах и со всеми малыми простыми в квадратах (202 паттерна по списку Хуго, начиная с b65,b66,b67,b70), как раз с -p100. До 1e30 они были проверены все, до 1e31 первые (с наименьшими номерами) 30 штук, эти считались по 66000с каждый. Потом бросил, слишком долго.

[EUgeneUS]

Dmitriy40
Спасибо!
Это ограничение на $LCM=7214407200$, их как раз 202 штуки.

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

до 1e31 первые (с наименьшими номерами) 30 штук, эти считались по 66000с каждый.

Это довольно странно.
У меня паттерн b319 посчитался за 400000 сек. c тем же ключом (-p100) от 21e31 до 200e31. То есть за время в 6 раз больше, обработался диапазон в 180 раз больше.

[Dmitriy40]

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

Это довольно странно.
У меня паттерн b319 посчитался за 400000 сек. c тем же ключом (-p100) от 21e31 до 200e31. То есть за время в 6 раз больше, обработался диапазон в 180 раз больше.

Возможно это снова вылезла проблема -g1e19, я запускал именно с таким ключом (это было ещё в начале декабря и видимо до наших с Вами обсуждений этого ключа в почте).

[EUgeneUS]

Да, возможно в этом дело.

[Huz]

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

Dmitriy40
Huz
Как по вашему мнению, насколько перспективно посчитать паттерны из "Группы А" до 200e31 (то есть до минимальной известной цепочки) с ключом -p100?
В частности, если уже такой расчет кем-то проводился, то повторно считать, нет смысла. Также приветствуются любые другие соображения.

I would have expected that with the effort expended so far, a smaller D(12,14) would have been found by now, but nothing has been found. Given that, I do not know what to expect. If it would now be reasonable to expect that no smaller value will be found, the sensible next step would be to aim for the most efficient possible systematic search across all values; if it is still reaonable to expect that a smaller value might be found, then it remains sensible to focus efforts wherever that smaller value is most likely.

Regardless, the work you are doing does not duplicate anything I have already done.

Dmitriy40
Support for separate -p limitation by powers seems to be working nicely, I just need to add some debugging options to show what it is doing and it will be ready for release.

[EUgeneUS]

Huz
Efforts were directed to finding a smaller D(12.14) in the range up to 21e31. Which is ten times smaller than the known chain.
From looking at the trends, there was a hope that such a chain could be found. But as the calculations progress, hope becomes less and less.

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

the sensible next step would be to aim for the most efficient possible systematic search across all values;

Systematic search, like searching for all existing patterns, is not possible due to the large computational costs required.

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

if it is still reaonable to expect that a smaller value might be found, then it remains sensible to focus efforts wherever that smaller value is most likely.

The probability that there is a chain ten times smaller than the known one decreases with the progress of the calculation.
However, the probability that there is a chain somewhat smaller than the known one remains.
I see the following options as the most promising:
1. Search in Group A in the range 21-200e31. This group has 10 "checked places" and has not been researched by Dimitry.
2. Search in Group Г, Д, Е in the range 21-200e31. These are groups with 11 "checked places", and $LCM < 7214407200$. They were also not explored by Dmitry, but due to the smaller LСM, the calculation time can be quite large even with the -p100 switch.

Groups Б and В also look promising, but, as far as I know, they were investigated by Dmitry (with rather small substituted primes in the squares) using his programs in the middle of last year. Therefore, their calculation with the -p100 key does not look so promising.

[Dmitriy40]

О D12n13: проверил все паттерны без неизвестных квадратов и с LCM=17304487200 и больше, новых решений не найдено.

[EUgeneUS]

Huz
Dmitriy40

По минимизации цепочки D12n14 нужна помощь или консультация.
При расчете паттернов из группы Б резко возросло время (в 5-10 раз по некоторым оценкам) по сравнению со временем для расчета паттернов групп А и В.
Подозреваю, что дело в оптимальном значение ключа -g.
Хотелось бы понять
а) какое значение ключа -g будет более близко к оптимальному? Куда его двигать?
б) почему такая разница для близких, казалаось бы паттернов.

Логи:
1. Паттерн из "группы А": $LCM = 7214407200$, количество "проверяемых мест" (после подстановки всех простых в больших степенях) - $10$. Количество подставляемых простых в больших степенях - $6$.

001 pcoul(12 14) -p300 -f13 -g10 -x70000000000000000000000000000000:140000000000000000000000000000000 -b319 *RT*
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.37^2 2^5 7.19^2 2.3^2 5.83^2 2^2 3.47^2 2.29^2 17^2: 2727 / 5307 (558.84s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.67^2 2^5 7.23^2 2.3^2 5.47^2 2^2 3.163^2 2.31^2 17^2: 161 / 249 (1116.61s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.71^2 2^5 7.29^2 2.3^2 5.41^2 2^2 3.23^2 2.31^2 17^2: 4657 / 9266 (1669.59s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.19^2 2^5 7.31^2 2.3^2 5.47^2 2^2 3.53^2 2.29^2 17^2: 11099 / 18543 (2227.76s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.113^2 2^5 7.37^2 2.3^2 5.89^2 2^2 3.53^2 2.31^2 17^2: 55 / 89 (2780.98s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.103^2 2^5 7.43^2 2.3^2 5.23^2 2^2 3.31^2 2.107^2 17^2: 147 / 293 (3328.47s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.31^2 2^5 7.47^2 2.3^2 5.191^2 2^2 3.241^2 2.97^2 17^2 (3874.34s)
305 2.7^2 13^2 2^2.3 11^2 2.5^2 3.31^2 2^5 7.61^2 2.3^2 5.19^2 2^2 3.97^2 2.29^2 17^2: 1753 / 3286 (4420.64s)

2. Паттерн из "группы В": $LCM = 7214407200$, количество "проверяемых мест" (после подстановки всех простых в больших степенях) - $11$. Количество подставляемых простых в больших степенях - $6$.

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.29^2 2.3^2 19^2 2^5 3.59^2 2.5^2 7^2 2^2.3 11.53^2 2.71^2: 86 / 1121 (598.30s)
305 17^2 2.11^2 3.13^2 2^2.7 5.433^2 2.3^2 19^2 2^5 3.43^2 2.5^2 7^2 2^2.3 11.239^2 2.149^2: 0 / 0 (1197.11s)
305 17^2 2.11^2 3.13^2 2^2.7 5.139^2 2.3^2 23^2 2^5 3.79^2 2.5^2 7^2 2^2.3 11.37^2 2.43^2: 0 / 103 (1796.50s)
305 17^2 2.11^2 3.13^2 2^2.7 5.83^2 2.3^2 23^2 2^5 3.163^2 2.5^2 7^2 2^2.3 11.173^2 2.31^2: 2 / 5 (2396.38s)
305 17^2 2.11^2 3.13^2 2^2.7 5.59^2 2.3^2 29^2 2^5 3.109^2 2.5^2 7^2 2^2.3 11.37^2 2.251^2: 5 / 5 (2995.80s)
305 17^2 2.11^2 3.13^2 2^2.7 5.479^2 2.3^2 29^2 2^5 3.439^2 2.5^2 7^2 2^2.3 11.257^2 2: 6 / 6 (3595.55s)
305 17^2 2.11^2 3.13^2 2^2.7 5.23^2 2.3^2 31^2 2^5 3.19^2 2.5^2 7^2 2^2.3 11.59^2 2.29^2: 26768 / 31244 (4194.23s)
305 17^2 2.11^2 3.13^2 2^2.7 5.47^2 2.3^2 37^2 2^5 3.167^2 2.5^2 7^2 2^2.3 11.19^2 2.43^2: 134 / 297 (4793.91s)

3. Паттерн из "группы Б" (проблемной): $LCM = 7214407200$, количество "проверяемых мест" (после подстановки всех простых в больших степенях) - $11$. Количество подставляемых простых в больших степенях - $5$

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000 -b1415 *RT*
305 3^2.5 2.29^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.61^2: 10824676 / 28089952 (585.86s)
305 3^2.5 2.31^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.37^2: 21100551 / 66815902 (1162.92s)
305 3^2.5 2.31^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.137^2: 1890119 / 4873512 (1758.64s)
305 3^2.5 2.37^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.79^2: 1166240 / 10288428 (2354.14s)
305 3^2.5 2.41^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.83^2: 240140 / 7590716 (2935.91s)
305 3^2.5 2.43^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.173^2: 196632 / 1588464 (3520.45s)
305 3^2.5 2.53^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.37^2: 22217176 / 22858697 (4108.34s)
305 3^2.5 2.61^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.41^2: 12183910 / 14053330 (4704.11s)
305 3^2.5 2.73^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.31^2: 15771664 / 17164752 (5301.47s)

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

[Dmitriy40]

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

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

Это играет только при достаточно большом -p, когда лучше пройтись линейным перебором вместо запуска ещё одного квадратичного (на миллионы или миллиарды итераций). При малых же -p (и больших -x, когда в него влезает больше тысяч итераций результирующего LCM после подстановки простых) ситуация ровно наоборот: лучше запустить лишний квадратичный (всего-то 90 итераций!), чем считать линейным в $p^2$ раз больше.
Так что замедление не удивительно, запустить-то 6-й квадратичный перебор (на жалкие 90 итераций) не получается и приходится идти линейно, а там итераций сильно больше.

Собственно -g тут и ни при чём, он никак не поможет запустить 6-й квадратичный перебор при отсутствии под него места в паттерне. Всё что он может сделать, так это по разному обрубать хвостовые вычисления, когда LCM стал уже достаточно велик (везде подставлены относительно большие простые), но вроде бы на это уходит относительно мало времени и существенно роли не сыграет.

[EUgeneUS]

Dmitriy40
Вот жеж.

Оценки времени счета с ключом -p500 на один паттерн на один поток получается от 2.5 до 5 млн. секунд, что в 6 -11 раз больше, чем для групп с 6-и квадратичными переборами.

Если снижать значение ключа -p, то до какого значения имеет смысл его снижать? С учетом того, что Вы эту группу паттернов исследовали с подстановкой небольших простых в квадратах.

[Dmitriy40]

По -p время кажется квадратично, значит для снижения времени до примерно прошлого уровня надо ставить -p200 или -p150. Думаю -p200 вполне достаточно, вряд ли будет много решений в интервале -p200...-p500, они вероятнее с малыми простыми. Насколько помню я проверял лишь -p50 (да и то далеко не полностью), это чересчур зажато.

[EUgeneUS]

Dmitriy40
Ок. Понятно. Проведем эксперименты, если с -p150 или более будет приемлемое время - посчитаем с таким ключом.

[Huz]

New version of pcoul and pcaul is now available at https://github.com/hvds/divrep/releases/tag/20230303.

Please let me know if anything is unclear about the release notes, or if you encounter any problems.

[EUgeneUS]

Huz
Dmitriy40
О влиянии ключей -p и -x на скорость расчета в pcoul.

1. Ключ -p при малых значениях оказалось влияет на скорость расчёта не квадратично, а гораздо меньше. Это печально, но объяснимо.
Примеры (все паттерны из одной группы, с одинаковыми LCM, количеством подставляемых мест с большими степенями простых и количеством проверяемых мест).

001 pcoul(12 14) -p200 -f13 -g10 -x70000000000000000000000000000000 -b1415 *RT*
305 3^2.5 2.29^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.61^2: 4918210 / 28089952 (563.25s)
...
305 3^2.5 2.23^2 37^2 2^2.3 7^2 2.5^2 3.31^2 2^5 197^2 2.3^2 5.11^2 2^2.7 3.13^2 2.67^2: 16606 / 40012 (1197895.81s)
305 3^2.5 2.23^2 41^2 2^2.3 7^2 2.5^2 3.19^2 2^5 17^2 2.3^2 5.11^2 2^2.7 3.13^2 2.37^2: 7288472 / 38197550 (1198485.31s)

001 pcoul(12 14) -p150 -f13 -g10 -x70000000000000000000000000000000 -b1415 *RT*
305 3^2.5 2.29^2 17^2 2^2.3 7^2 2.5^2 3.23^2 2^5 19^2 2.3^2 5.11^2 2^2.7 3.13^2 2.61^2: 5276278 / 28089952 (562.84s)
...
305 3^2.5 2.23^2 37^2 2^2.3 7^2 2.5^2 3.71^2 2^5 139^2 2.3^2 5.11^2 2^2.7 3.13^2 2.29^2: 977 / 81783 (1027329.25s)
305 3^2.5 2.23^2 41^2 2^2.3 7^2 2.5^2 3.19^2 2^5 17^2 2.3^2 5.11^2 2^2.7 3.13^2 2.29^2: 23964954 / 62178889 (1027899.00s)

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000 -b74 *RT*
305 2.29^2 3.13^2 2^2.7 5.11^2 2.3^2 17^2 2^5 3.23^2 2.5^2 7^2 2^2.3 19^2 2.107^2 3^2.5: 8480329 / 9129418 (599.68s)
...
305 2.113^2 3.13^2 2^2.7 5.11^2 2.3^2 37^2 2^5 3.19^2 2.5^2 7^2 2^2.3 491^2 2.23^2 3^2.5: 3350 / 6027 (1085151.91s)
305 2.29^2 3.13^2 2^2.7 5.11^2 2.3^2 41^2 2^5 3.19^2 2.5^2 7^2 2^2.3 17^2 2.59^2 3^2.5: 3162018 / 9449190 (1085751.89s)

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

2. Разбиение диапазона расчета ключом -x оказывается влияет на время расчета нелинейно и, видимо, неаддитивно. Вот это удивительно. Видимо, более оптимально считать большими диапазонами, а не маленькими. Примеры (все с одного компьютера).

001 pcoul(12 14) -p300 -f13 -g10 -x70000000000000000000000000000000 -b1624 *RT*
305 17^2 2.71^2 3.103^2 2^2.7 5.13^2 2.3^2 11^2 2^5 3.41^2 2.5^2 7.97^2 2^2.3 19^2 2.181^5 (595.72s)
...
305 149^5 2 3.179^5 2^2.7 5.13^2 2.3^2 11^2 2^5 3 2.5^2 7.107^2 2^2.3 277^2 2 (312527.09s)
367 coul(12, 14): recurse 27439842019, walk 54336829924, walkc 12099576240 (312597.95s)

001 pcoul(12 14) -p300 -f13 -g10 -x70000000000000000000000000000000:210000000000000000000000000000000 -b1624 *RT*
305 17^2 2.173^2 3.107^2 2^2.7 5.13^2 2.3^2 11^2 2^5 3.137^2 2.5^2 7.67^2 2^2.3 19^2 2.293^2 (599.94s)
...
305 131^5 2 3.29^2 2^2.7 5.13^2 2.3^2 11^2 2^5 3.269^2 2.5^2 7.139^2 2^2.3 23^2 2 (473273.88s)
367 coul(12, 14): recurse 28933862100, walk 28361114412, walkc 8627229447 (473423.84s)

Второй пример - это тот же самый паттерн, но считается диапазон в два раза больше. Вместо ожидаемых 600 - 650 тысяч секунд, время составило 473 тысячи секунд.
Это вряд ли связано с тем, что считался диапазон в бОльших числах. Так как при разбиении на диапазоны одинаковой длины и время получается примерно одинаковым

[Dmitriy40]

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

Это вряд ли связано с тем, что считался диапазон в бОльших числах. Так как при разбиении на диапазоны одинаковой длины и время получается примерно одинаковым

А я вот думаю связано именно с этим: чем больше числа, тем больше придётся делать итераций в линейном переборе и соответственно будет смещаться момент переключения с квадратичного на линейный. Проверьте сами: возьмите интервал поменьше (типа 1e31 или 1e30) в разных местах (скажем 7e31 и 28e31) и сравните время его счёта.
Ну и сравнивать незаконченные счёты не совсем корректно.

Насчёт зависимости от -p я вот делал специальные тесты: post1574922.html#p1574922
Да, неделями не ждал, брал небольшие числа/интервалы, возможно это плохо повлияло на зависимость от -p ...