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

[EUgeneUS]

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

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

Тут ситуация простая и в целом нормальная.
Но сначала определим несколько терминов.
1. "Условия вывода в лог". "По умолчанию" $valids \geqslant 8$. IMHO, так и было у Демиса.
2. "Зона перекрытия" - позиции, общие для некой группы паттернов, (группы тут не обязательно, как мы объединяли).

Так вот какая-то цепочка ("находка") попадет в лог всех паттернов группы, если:
1. Либо условия вывода в лог выполнились в зоне перекрытия.
2. Либо "побочные" валидные позиции возникли вне зоны перекрытия для всех паттернов группы.

В противном случае, а именно: "побочные" валидные позиции возникли вне зоны перекрытия не для всех паттернов группы (например, для одного), тогда совсем не обязательно, что условия вывода в лог этой цепочки выполнятся для всех паттернов группы.

[Dmitriy40]

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

[EUgeneUS]

У меня закончился счет 16 паттернов с $LCM=14642258400$ программой Хуго:
Вот пример типового лога

001 pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b2157
001 recover pcoul(12 11) -f11 -g3 -x9887353188984012120346 -b2157
305 11^2 2 3 2^2.7 5 2.3^2 13^2 2^5 3 2.5^2 7^5: 253925557 / 1997815051 (599.99s)
....
305 11^2 2 3 2^2.7 5 2.3^2 6328318363^2 2^5 3 2.5^2 7^5 (26399.99s)
367 coul(12, 11): recurse 310063074, walk 310067127, walkc 7585808541 (26742.11s)

Как видно,
а) тут шел перебор квадрата одного простого.
б) время счета для данного LCM заметно больше, чем по логам Демиса, который считал программами Dmitriy40

Но это предыдущая версия.

А вот новая версия программы Хуго для того же LCM устраивает перебор двух простых. Завтра посмотрим, как это отразится на времени счета.

[Huz]

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

Yes, next_prime() is usually slow regardless of the bits. I'm not sure how exactly you have it. But the primes should not be searched for by getting the next one, but by Sieve of Eratosthenes, which for primes up to 6.7e9 work for less than 10s-30s and require less than 100K bytes of memory. Code in a variety of programming languages is freely available on the web (including wiki), especially for such small numbers (numbers up to 1e10 is small for this task).

I have not looked in detail at the next_prime() code, but I believe it is sieving in batches.

Changing my code so that it tracks the prime index $i$ as well as (or instead of) the prime $p_i$ would be a fairly large operation, but should be possible. I think that would be necessary to take full advantage of a separately prepared array of primes. But I want to preserve the capability of my program to solve the wider range of problems, not just $D(12,11)$, so I would need to think carefully how scalable such an approach would be.

A smaller but fully scalable change might be to allocate a prime iterator for each recursion level, and let that decide whether to use fixed array lookup.

-- 08.11.2022, 17:59 --

Here is some example code, and some timings.

# test 1
    while (p < target) {
        sum += p;
        p = next_prime(p);
    }

# target: sum (time)
1000000: 37550402023 (0.04s)
10000000: 3203324994356 (2.23s)
100000000: 279209790387276 (24.01s)
1000000000: 24739512092254535 (240.84s)
10000000000: (not attempted)

# test 2
    PRIME_ITERATOR(iter);
    while (p < target) {
        sum += p;
        p = prime_iterator_next(&iter);
    }
    prime_iterator_destroy(&iter);

# target: sum (time)
1000000: 37550402023 (0.00s)
10000000: 3203324994356 (0.01s)
100000000: 279209790387276 (0.13s)
1000000000: 24739512092254535 (1.44s)
10000000000: 2220822432581729238 (15.99s)

I will try to put this into pcoul over the next day, and see what effect that has on real timings: I do not know without trying it how many of those "4 minutes-per-billion" iterations it is actually doing. (I hope to add functionality to reset those iterators, so I do not have to repeatedly create and destroy them.)

[Dmitriy40]

Huz
Test #2 - very good.
And it doesn't require big changes in the code, you only need one iterator per recursive level and the time to create and delete it is minimal.
But even 240s is not 2800s, please still do a CRT test, it's interesting.

-- 08.11.2022, 21:46 --

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

А вот новая версия программы Хуго для того же LCM устраивает перебор двух простых. Завтра посмотрим, как это отразится на времени счета.

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

[Huz]

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

Test #2 - very good.
And it doesn't require big changes in the code, you only need one iterator per recursive level and the time to create and delete it is minimal.

Yes, it was easier than expected. (It does a stupid free() immediately followed by malloc() of the same size, but I can't easily remove that; hopefully the malloc implementation will just give the same block back each time.)

It gives a decent boost on full $D(12,9)$ calculation (but 10%, not 9x):

% ./pcoul-next -x15724736975643 -f7 -g3 12 9
367 coul(12, 9): recurse 45978945, walk 46008023, walkc 195399131 (202.95s)
% ./pcoul-iter -x15724736975643 -f7 -g3 12 9
367 coul(12, 9): recurse 45978945, walk 46008023, walkc 195399131 (181.39s)

Identical counters give me some confidence that it is doing the right thing in this case, but I need to do more checks to make sure I only change the current prime in one place.

Цитата:

But even 240s is not 2800s, please still do a CRT test, it's interesting.

It is less obvious how to construct a CRT test that is valid, but I'll try that tomorrow.

[Dmitriy40]

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

It is less obvious how to construct a CRT test that is valid, but I'll try that tomorrow.

It's just brazen to put the first prime not 13, but 10^7 (this is guaranteeing that all less will not check). Well, or skip all the primes less than 10^7 without any calculations. This is one additional "if(p<10^7) {goto next}" in the right place of the code. Second "if" need to skip checking result of CRT - to not delete code. That's all.
However, perhaps everything is not so simple, you know better.

[Yadryara]

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

1.         554400  —   66 штук
2.        3880800  —  142 штуки
3.        6098400  —  180 штук
4.       42688800  —  226 штук
5.     1331114400  —   66 штук; 2 done
6.     8116970400  —   58 штук
7.    14642258400  —  152 штуки; 31 done
8.    56818792800  —   96 штук ; done
9. 19488845930400  —   58 штук ; done

Ну то есть Софокл ежедневно обсчитывает по 10-11 паттернов с шагом 14642258400 в 2-х потоках.

[Yadryara]

Не думал, что сегодня поступят новости, но раз поступили, то вот сводка по данным на сегодня.

1.         554400  —   66 штук
2.        3880800  —  142 штуки
3.        6098400  —  180 штук
4.       42688800  —  226 штук
5.     1331114400  —   66 штук; 2 done
6.     8116970400  —   58 штук
7.    14642258400  —  152 штуки; 47 done
8.    56818792800  —   96 штук ; done
9. 19488845930400  —   58 штук ; done

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

Ну то есть Софокл ежедневно обсчитывает по 10-11 паттернов с шагом 14642258400 в 2-х потоках.

А за последние сутки обсчитал 16 паттернов с этим же шагом. Во 2-м потоке осталось обсчитать 14 таких паттернов. В 3-м — 91.

[Dmitriy40]

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

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

Проверил, пока что досчитал до двухкратного ускорения перебора больших простых (которые дают или одно начальное число на проверку или не дают вообще) за счёт гарантированного снижения верхнего предела докуда их нужно перебирать. Идея вот в чём. Чтобы уменьшить верхний порог для $p<\sqrt{M/qr}$ при переборе в формуле $p^2qr$ надо убедиться что начиная с некоторого достаточно большого $p$ вообще нет решений для любых возможных комбинаций $qr$. В частности, код Hugo перебирает $p$ начиная с пустых мест в паттерне, для которых можно принять $q>r>11 \to q=17,r=13, qr=221$, т.е. перебирать $p$ надо до $\sqrt{M/221}$, что для $M=10^{22}$ составляет 6.727e9 (что и видно в логах его программы, учитывая что $M$ у него чуточку меньше). Если подставлять не в пустое место, то $q>11, r=\{2,3,5,7,11\}$ и перебирать простые может понадобиться вплоть до $p<\sqrt{M/13/2}$, что для $M=10^{22}$ составляет почти 2e10. Но можно взять и прямо проверить что для например $qr<1112$ нет длинных решений для любых паттернов и любых $p<\sqrt{M/qr}$, ведь разных $qr$ не так уж и много, это не произвольное число, а всегда произведение двух различных простых, причём одно из них (я беру $q$, причём $q>r$) не меньше $13$ (меньшие уже все размещены). Вот я и перебрал все такие $p<2\cdot10^{10}$ и все варианты $qr<1112$ без привязки к паттернам вообще (потребовал лишь наличия числа $32x$ и правильных 5-ти чисел вокруг, это соблюдается для любых цепочек длиной 10+), просто числа $32x\approx p^2qr$ (на чистом PARI, без дополнительных программ с недоказанной надёжностью), самое длинное что нашёл:

3*29*126506773^2:1392344834493997017: 20, 12,  8,192,  8, 12, 12, 12, 12, 12, 12, 12,  8, 48,  4,  valids=8, maxlen=7
2*17*869483983^2:25704081487580505817:  4,  4,  8, 12, 12, 12, 12, 12, 12, 12,  8,192,  4, 32, 20,  valids=7, maxlen=7
3*19*12201437869^2:8485879906050833886169: 16, 32, 32, 12, 12, 12, 12, 12, 12, 12,  4, 48,  8,128, 12,  valids=8, maxlen=7
3*331*336983233^2:112762795427870362969:  8, 64, 32, 12, 12, 12, 12, 12, 12, 12, 16,192,  4,  4, 96,  valids=7, maxlen=7
3*283*1292920201^2:1419224606584644460441:  4,  8,  4, 24, 64, 12, 12, 12, 12, 12, 12, 12,  8, 32, 48,  valids=7, maxlen=7

И теперь в поиске решений по любым паттернам длиной 11 можно перебирать $p$ лишь до $\sqrt{10^{22}/1112}$ (уже независимо от того в какое место паттерна подставляем $p^2$), что составляет почти ровно 3e9 ($qr$ так и выбиралось, для круглой цифры), более чем вдвое меньше используемой Hugo величины 6.727e9 (и почти в 7 раз меньше 2e10). И что самое прекрасное, этот порог действует не просто на все паттерны, но и на все переборы простых в них, не только на первый/верхний! А раз ускоряются все переборы больших простых, которые как раз страшно и тормозят пока что у Hugo, то и запускать переборы можно чаще и для чуть больших простых, что даст и дополнительный выигрыш в скорости.
Мне даст, предлагать реализовать это Hugo даже не буду (потому и пишу только на русском), он выше ясно высказался за универсальность в пику скорости, ну, это тоже правильный подход.

[EUgeneUS]

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

А почему нет, собственно?
Малые $qr$ до нескольких тысяч можно проверить отдельно ("унивесальным софтом" но с заданными в параметрах длиной цепочки и количеством делителей). А потом подавать это ограничение в опять же унниверсальный софт через параметры.

Но Хуго виднее, конечно.

-- 09.11.2022, 12:50 --

Yadryara
Для информации.
Мы немного переграли с Хуго выделение паттернов для счета у меня.
Буду брать паттерны из диапазона b1836-b2166.
(Замахнул не глядя 4-ре наихудших паттерна из 8-ми )

Вчера посчиталась первая партия из 16 паттернов с $LCM = 14642258400$. Время счета каждого 8-8.5 часов.
Время счета на одном компьтере очень слабо отличалось от паттерна к паттерну. Больше время зависело от компа (один чуть быстрее, другой чуть медленнее).
Надеюсь, сегодня вечером или к завтрашнему утру досчитаются оставшиеся 25 паттернов с этим LCM в этом диапазоне.

Есть и хорошие новости. Связался с Артемом (RTM), он согласился подключиться к нашему счету.

[Yadryara]

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

(потребовал лишь наличия числа $32x$ и правильных 5-ти чисел вокруг, это соблюдается для любых цепочек длиной 10+),

А точнее, что за 5 правильных чисел и где именно вокруг?

Я спрашиваю не потому что не знаю, а для проверки.

[Yadryara]

Краткая биекция вида DH ($Dmitriy \to Hugo$). Первые 5 шагов из 9.

(Оффтоп)

LCM554400-31545-4   b85
LCM554400-74169-4   b204
LCM554400-74745-4   b115
LCM554400-74745-5   b613
LCM554400-74745-6   b1158
LCM554400-81049-8   b1952
LCM554400-102969-6   b1194
LCM554400-119641-4   b34
LCM554400-119641-5   b514
LCM554400-119641-6   b1009
LCM554400-119641-7   b1515
LCM554400-119641-8   b2084
LCM554400-125145-6   b1151
LCM554400-126841-8   b2127
LCM554400-145849-8   b1907
LCM554400-149017-8   b2055
LCM554400-153369-4   b166
LCM554400-153369-5   b642
LCM554400-153369-6   b1198
LCM554400-170937-4   b302
LCM554400-174969-4   b208
LCM554400-175545-4   b111
LCM554400-175545-5   b609
LCM554400-175545-6   b1154
LCM554400-181849-8   b1944
LCM554400-228217-8   b2017
LCM554400-246649-8   b1911
LCM554400-249817-6   b989
LCM554400-249817-7   b1497
LCM554400-249817-8   b2060
LCM554400-270841-4   b39
LCM554400-270841-5   b519
LCM554400-270841-6   b1014
LCM554400-283545-6   b1108
LCM554400-283545-7   b1619
LCM554400-283545-8   b1867
LCM554400-304569-4   b171
LCM554400-304569-5   b647
LCM554400-304569-6   b1203
LCM554400-307737-4   b250
LCM554400-326169-4   b214
LCM554400-372537-4   b298
LCM554400-378841-6   b1045
LCM554400-378841-7   b1545
LCM554400-378841-8   b2136
LCM554400-379417-8   b2023
LCM554400-383449-8   b1942
LCM554400-401017-6   b994
LCM554400-401017-7   b1502
LCM554400-401017-8   b2065
LCM554400-405369-4   b176
LCM554400-408537-4   b254
LCM554400-427545-4   b120
LCM554400-429241-6   b1049
LCM554400-434745-4   b78
LCM554400-434745-5   b585
LCM554400-434745-6   b1113
LCM554400-434745-7   b1624
LCM554400-434745-8   b1872
LCM554400-451417-6   b997
LCM554400-473337-4   b293
LCM554400-479641-6   b1039
LCM554400-479641-7   b1539
LCM554400-479641-8   b2130
LCM554400-480217-8   b2027
LCM554400-522841-8   b2078
LCM3880800-102649-8   b1957
LCM3880800-125145-7   b1589
LCM3880800-125145-8   b1838
LCM3880800-174969-4   b183
LCM3880800-206041-8   b2089
LCM3880800-220441-4   b17
LCM3880800-220441-5   b539
LCM3880800-220441-6   b1074
LCM3880800-220441-7   b1559
LCM3880800-220441-8   b2156
LCM3880800-250137-4   b267
LCM3880800-254745-6   b1121
LCM3880800-254745-7   b1632
LCM3880800-254745-8   b1880
LCM3880800-300217-6   b967
LCM3880800-300217-7   b1479
LCM3880800-300217-8   b2036
LCM3880800-372537-4   b275
LCM3880800-405369-4   b151
LCM3880800-558841-8   b2092
LCM3880800-681241-8   b2102
LCM3880800-700249-8   b1969
LCM3880800-710937-4   b223
LCM3880800-725337-4   b279
LCM3880800-729945-4   b88
LCM3880800-729945-5   b592
LCM3880800-729945-6   b1133
LCM3880800-837945-6   b1089
LCM3880800-837945-7   b1600
LCM3880800-837945-8   b1848
LCM3880800-880569-4   b189
LCM3880800-883417-8   b1995
LCM3880800-911641-8   b2095
LCM3880800-933241-4   b46
LCM3880800-933241-5   b559
LCM3880800-1005817-6   b974
LCM3880800-1034041-6   b1016
LCM3880800-1034041-7   b1520
LCM3880800-1034041-8   b2105
LCM3880800-1038649-8   b1922
LCM3880800-1183545-7   b1596
LCM3880800-1205145-4   b123
LCM3880800-1313145-6   b1118
LCM3880800-1313145-7   b1629
LCM3880800-1313145-8   b1877
LCM3880800-1358617-6   b966
LCM3880800-1358617-7   b1478
LCM3880800-1358617-8   b2035
LCM3880800-1386841-6   b1018
LCM3880800-1386841-7   b1522
LCM3880800-1386841-8   b2107
LCM3880800-1416537-4   b229
LCM3880800-1509241-5   b521
LCM3880800-1509241-6   b1056
LCM3880800-1513849-8   b1960
LCM3880800-1543545-4   b55
LCM3880800-1543545-5   b568
LCM3880800-1543545-6   b1094
LCM3880800-1543545-7   b1605
LCM3880800-1543545-8   b1853
LCM3880800-1589017-8   b2002
LCM3880800-1631641-8   b2148
LCM3880800-1661337-4   b257
LCM3880800-1744249-8   b1928
LCM3880800-1788345-6   b1130
LCM3880800-1816569-4   b141
LCM3880800-1816569-5   b623
LCM3880800-1816569-6   b1173
LCM3880800-1862041-4   b3
LCM3880800-1862041-5   b525
LCM3880800-1862041-6   b1060
LCM3880800-2018745-6   b1124
LCM3880800-2018745-7   b1635
LCM3880800-2018745-8   b1883
LCM3880800-2064217-6   b971
LCM3880800-2064217-7   b1483
LCM3880800-2064217-8   b2040
LCM3880800-2092441-6   b1026
LCM3880800-2136537-4   b270
LCM3880800-2219449-8   b1965
LCM3880800-2249145-4   b62
LCM3880800-2291769-4   b179
LCM3880800-2337241-4   b15
LCM3880800-2337241-5   b537
LCM3880800-2337241-6   b1072
LCM3880800-2337241-7   b1557
LCM3880800-2337241-8   b2154
LCM3880800-2366937-4   b262
LCM3880800-2371545-6   b1126
LCM3880800-2371545-7   b1637
LCM3880800-2464249-8   b1973
LCM3880800-2493945-4   b90
LCM3880800-2493945-5   b594
LCM3880800-2493945-6   b1135
LCM3880800-2522169-4   b146
LCM3880800-2522169-5   b628
LCM3880800-2522169-6   b1178
LCM3880800-2567641-4   b10
LCM3880800-2567641-5   b532
LCM3880800-2567641-6   b1067
LCM3880800-2675641-8   b2099
LCM3880800-2697241-5   b553
LCM3880800-2842137-4   b274
LCM3880800-2846745-4   b92
LCM3880800-2846745-5   b596
LCM3880800-2846745-6   b1137
LCM3880800-2874969-6   b1169
LCM3880800-2947545-7   b1592
LCM3880800-2947545-8   b1841
LCM3880800-2969145-4   b127
LCM3880800-2997369-4   b184
LCM3880800-3000217-8   b1992
LCM3880800-3042841-4   b20
LCM3880800-3042841-5   b542
LCM3880800-3042841-6   b1077
LCM3880800-3150841-6   b1022
LCM3880800-3150841-7   b1526
LCM3880800-3150841-8   b2111
LCM3880800-3155449-8   b1919
LCM3880800-3169849-8   b1978
LCM3880800-3180537-4   b233
LCM3880800-3199545-4   b97
LCM3880800-3321945-4   b128
LCM3880800-3475417-8   b2030
LCM3880800-3508249-8   b1921
LCM3880800-3580569-4   b143
LCM3880800-3580569-5   b625
LCM3880800-3580569-6   b1175
LCM3880800-3626041-4   b6
LCM3880800-3626041-5   b528
LCM3880800-3626041-6   b1063
LCM3880800-3630649-8   b1955
LCM3880800-3660345-4   b51
LCM3880800-3660345-5   b564
LCM3880800-3660345-6   b1090
LCM3880800-3660345-7   b1601
LCM3880800-3660345-8   b1849
LCM3880800-3674745-4   b133
LCM3880800-3705817-8   b1998
LCM3880800-3755641-4   b50
LCM3880800-3755641-5   b563
LCM3880800-3778137-4   b263
LCM6098400-74169-4   b202
LCM6098400-102969-6   b1192
LCM6098400-297049-8   b1912
LCM6098400-377145-4   b116
LCM6098400-377145-5   b614
LCM6098400-377145-6   b1159
LCM6098400-378841-6   b1043
LCM6098400-378841-7   b1543
LCM6098400-378841-8   b2134
LCM6098400-383449-8   b1940
LCM6098400-434745-4   b76
LCM6098400-434745-5   b583
LCM6098400-434745-6   b1111
LCM6098400-434745-7   b1622
LCM6098400-434745-8   b1870
LCM6098400-522841-8   b2076
LCM6098400-535545-7   b1616
LCM6098400-535545-8   b1864
LCM6098400-574137-4   b296
LCM6098400-830169-4   b210
LCM6098400-854617-6   b990
LCM6098400-854617-7   b1498
LCM6098400-854617-8   b2061
LCM6098400-858969-4   b169
LCM6098400-858969-5   b645
LCM6098400-858969-6   b1201
LCM6098400-883417-8   b2020
LCM6098400-930969-4   b205
LCM6098400-1139449-8   b1948
LCM6098400-1233945-4   b117
LCM6098400-1233945-5   b615
LCM6098400-1254649-8   b1905
LCM6098400-1278841-4   b35
LCM6098400-1278841-5   b515
LCM6098400-1278841-6   b1010
LCM6098400-1278841-7   b1516
LCM6098400-1278841-8   b2085
LCM6098400-1334745-4   b112
LCM6098400-1334745-5   b610
LCM6098400-1334745-6   b1155
LCM6098400-1336441-6   b1040
LCM6098400-1336441-7   b1540
LCM6098400-1336441-8   b2131
LCM6098400-1379641-7   b1510
LCM6098400-1379641-8   b2079
LCM6098400-1392345-6   b1106
LCM6098400-1392345-7   b1617
LCM6098400-1392345-8   b1865
LCM6098400-1416537-4   b248
LCM6098400-1686969-4   b211
LCM6098400-1812217-8   b2053
LCM6098400-1816569-4   b164
LCM6098400-1816569-5   b640
LCM6098400-1816569-6   b1196
LCM6098400-1996249-8   b1949
LCM6098400-2010649-8   b1914
LCM6098400-2090745-4   b118
LCM6098400-2092441-6   b1047
LCM6098400-2097049-8   b1943
LCM6098400-2148345-4   b79
LCM6098400-2148345-5   b586
LCM6098400-2148345-6   b1114
LCM6098400-2148345-7   b1625
LCM6098400-2148345-8   b1873
LCM6098400-2236441-6   b1005
LCM6098400-2236441-7   b1511
LCM6098400-2236441-8   b2080
LCM6098400-2287737-4   b297
LCM6098400-2374137-4   b244
LCM6098400-2543769-4   b212
LCM6098400-2572569-4   b172
LCM6098400-2572569-5   b648
LCM6098400-2572569-6   b1204
LCM6098400-2597017-8   b2021
LCM6098400-2669017-7   b1493
LCM6098400-2669017-8   b2056
LCM6098400-2673369-4   b167
LCM6098400-2673369-5   b643
LCM6098400-2673369-6   b1199
LCM6098400-2853049-8   b1950
LCM6098400-2867449-8   b1915
LCM6098400-2968249-8   b1908
LCM6098400-2992441-4   b36
LCM6098400-2992441-5   b516
LCM6098400-2992441-6   b1011
LCM6098400-2992441-7   b1517
LCM6098400-2992441-8   b2086
LCM6098400-3048345-4   b113
LCM6098400-3048345-5   b611
LCM6098400-3048345-6   b1156
LCM6098400-3050041-6   b1041
LCM6098400-3050041-7   b1541
LCM6098400-3050041-8   b2132
LCM6098400-3105945-4   b74
LCM6098400-3105945-5   b581
LCM6098400-3105945-6   b1109
LCM6098400-3105945-7   b1620
LCM6098400-3105945-8   b1868
LCM6098400-3130137-4   b251
LCM6098400-3230937-4   b245
LCM6098400-3245337-4   b291
LCM6098400-3425017-6   b991
LCM6098400-3425017-7   b1499
LCM6098400-3425017-8   b2062
LCM6098400-3429369-4   b173
LCM6098400-3429369-5   b649
LCM6098400-3501369-4   b206
LCM6098400-3525817-6   b986
LCM6098400-3525817-7   b1494
LCM6098400-3525817-8   b2057
LCM6098400-3554617-8   b2015
LCM6098400-3724249-8   b1916
LCM6098400-3810649-8   b1945
LCM6098400-3861945-4   b80
LCM6098400-3861945-5   b587
LCM6098400-3861945-6   b1115
LCM6098400-3950041-4   b31
LCM6098400-3950041-5   b511
LCM6098400-3950041-6   b1006
LCM6098400-3950041-7   b1512
LCM6098400-3950041-8   b2081
LCM6098400-4001337-4   b299
LCM6098400-4005945-6   b1149
LCM6098400-4007641-8   b2125
LCM6098400-4087737-4   b246
LCM6098400-4102137-4   b294
LCM6098400-4281817-6   b992
LCM6098400-4281817-7   b1500
LCM6098400-4281817-8   b2063
LCM6098400-4286169-4   b174
LCM6098400-4411417-8   b2018
LCM6098400-4681849-8   b1909
LCM6098400-4706041-4   b37
LCM6098400-4706041-5   b517
LCM6098400-4706041-6   b1012
LCM6098400-4718745-4   b81
LCM6098400-4718745-5   b588
LCM6098400-4761945-4   b114
LCM6098400-4761945-5   b612
LCM6098400-4761945-6   b1157
LCM6098400-4763641-6   b1042
LCM6098400-4763641-7   b1542
LCM6098400-4763641-8   b2133
LCM6098400-4819545-4   b75
LCM6098400-4819545-5   b582
LCM6098400-4819545-6   b1110
LCM6098400-4819545-7   b1621
LCM6098400-4819545-8   b1869
LCM6098400-4843737-4   b252
LCM6098400-4864441-7   b1537
LCM6098400-4864441-8   b2128
LCM6098400-4958937-4   b295
LCM6098400-5167417-8   b2024
LCM6098400-5214969-4   b209
LCM6098400-5239417-6   b987
LCM6098400-5239417-7   b1495
LCM6098400-5239417-8   b2058
LCM6098400-5243769-4   b168
LCM6098400-5243769-5   b644
LCM6098400-5243769-6   b1200
LCM6098400-5268217-8   b2019
LCM6098400-5524249-8   b1947
LCM6098400-5562841-4   b40
LCM6098400-5562841-5   b520
LCM6098400-5575545-4   b83
LCM6098400-5663641-4   b32
LCM6098400-5663641-5   b512
LCM6098400-5663641-6   b1007
LCM6098400-5663641-7   b1513
LCM6098400-5663641-8   b2082
LCM6098400-5714937-4   b300
LCM6098400-5719545-4   b109
LCM6098400-5719545-5   b607
LCM6098400-5719545-6   b1152
LCM6098400-5721241-6   b1038
LCM6098400-5721241-7   b1538
LCM6098400-5721241-8   b2129
LCM6098400-5801337-4   b247
LCM6098400-5995417-6   b995
LCM6098400-6024217-8   b2025
LCM42688800-377145-4   b93
LCM42688800-377145-5   b597
LCM42688800-377145-6   b1138
LCM42688800-602937-4   b259
LCM42688800-1278841-4   b16
LCM42688800-1278841-5   b538
LCM42688800-1278841-6   b1073
LCM42688800-1278841-7   b1558
LCM42688800-1278841-8   b2155
LCM42688800-1416537-4   b227
LCM42688800-1816569-4   b139
LCM42688800-1816569-5   b621
LCM42688800-1816569-6   b1171
LCM42688800-2092441-6   b1024
LCM42688800-2097049-8   b1920
LCM42688800-3050041-4   b42
LCM42688800-3050041-5   b555
LCM42688800-3978841-6   b1055
LCM42688800-4005945-7   b1587
LCM42688800-4005945-8   b1836
LCM42688800-4286169-4   b149
LCM42688800-4411417-8   b1993
LCM42688800-4718745-4   b58
LCM42688800-4718745-5   b571
LCM42688800-4733145-4   b129
LCM42688800-4792441-8   b2093
LCM42688800-4958937-4   b272
LCM42688800-5239417-6   b964
LCM42688800-5239417-7   b1476
LCM42688800-5239417-8   b2033
LCM42688800-6172569-4   b177
LCM42688800-6448441-4   b8
LCM42688800-6448441-5   b530
LCM42688800-6448441-6   b1065
LCM42688800-6453049-8   b1956
LCM42688800-7433145-4   b89
LCM42688800-7433145-5   b593
LCM42688800-7433145-6   b1134
LCM42688800-8094649-8   b1925
LCM42688800-8109049-8   b1976
LCM42688800-8246745-4   b56
LCM42688800-8246745-5   b569
LCM42688800-8246745-6   b1095
LCM42688800-8246745-7   b1606
LCM42688800-8246745-8   b1854
LCM42688800-8334841-6   b1068
LCM42688800-8334841-7   b1553
LCM42688800-8334841-8   b2150
LCM42688800-8642169-4   b187
LCM42688800-8767417-7   b1474
LCM42688800-8767417-8   b2031
LCM42688800-10128537-4   b260
LCM42688800-10804441-4   b18
LCM42688800-10804441-5   b540
LCM42688800-10804441-6   b1075
LCM42688800-10942137-4   b231
LCM42688800-11622649-8   b1923
LCM42688800-11789145-4   b124
LCM42688800-11848441-8   b2087
LCM42688800-12450649-8   b1962
LCM42688800-12575641-4   b44
LCM42688800-12575641-5   b557
LCM42688800-12602745-6   b1125
LCM42688800-12602745-7   b1636
LCM42688800-12602745-8   b1884
LCM42688800-13430745-4   b94
LCM42688800-13430745-5   b598
LCM42688800-13504441-4   b1
LCM42688800-13504441-5   b523
LCM42688800-13504441-6   b1058
LCM42688800-13531545-7   b1593
LCM42688800-13531545-8   b1842
LCM42688800-14318041-8   b2097
LCM42688800-14870169-4   b142
LCM42688800-14870169-5   b624
LCM42688800-14870169-6   b1174
LCM42688800-15165049-8   b1970
LCM42688800-15698169-4   b181
LCM42688800-16204441-8   b2100
LCM42688800-16958745-4   b91
LCM42688800-16958745-5   b595
LCM42688800-16958745-6   b1136
LCM42688800-17184537-4   b255
LCM42688800-17465017-8   b1994
LCM42688800-17772345-4   b60
LCM42688800-17786745-4   b130
LCM42688800-17860441-4   b13
LCM42688800-17860441-5   b535
LCM42688800-17860441-6   b1070
LCM42688800-17860441-7   b1555
LCM42688800-17860441-8   b2152
LCM42688800-17998137-4   b226
LCM42688800-18398169-6   b1167
LCM42688800-18674041-6   b1020
LCM42688800-18674041-7   b1524
LCM42688800-18674041-8   b2109
LCM42688800-18678649-8   b1917
LCM42688800-18830745-7   b1597
LCM42688800-18830745-8   b1845
LCM42688800-19226169-4   b180
LCM42688800-19502041-4   b11
LCM42688800-19502041-5   b533
LCM42688800-19631641-4   b41
LCM42688800-19631641-5   b554
LCM42688800-19654137-4   b265
LCM42688800-19658745-6   b1119
LCM42688800-19658745-7   b1630
LCM42688800-19658745-8   b1878
LCM42688800-20867769-4   b147
LCM42688800-20867769-5   b629
LCM42688800-20867769-6   b1179
LCM42688800-21148249-8   b1926
LCM42688800-21162649-8   b1977
LCM42688800-21526137-4   b224
LCM42688800-21540537-4   b268
LCM42688800-21821017-6   b963
LCM42688800-21821017-7   b1475
LCM42688800-21821017-8   b2032
LCM42688800-23030041-4   b4
LCM42688800-23030041-5   b526
LCM42688800-23030041-6   b1061
LCM42688800-23034649-8   b1953
LCM42688800-23057145-7   b1595
LCM42688800-23057145-8   b1844
LCM42688800-23186745-7   b1626
LCM42688800-23186745-8   b1874
LCM42688800-23462617-8   b1999
LCM42688800-23858041-4   b21
LCM42688800-23858041-5   b543
LCM42688800-24010137-4   b277
LCM42688800-24014745-4   b86
LCM42688800-24014745-5   b590
LCM42688800-24014745-6   b1131
LCM42688800-24290617-6   b972
LCM42688800-24690649-8   b1974
LCM42688800-24828345-4   b53
LCM42688800-24828345-5   b566
LCM42688800-24828345-6   b1092
LCM42688800-24828345-7   b1603
LCM42688800-24828345-8   b1851
LCM42688800-24902041-8   b2090
LCM42688800-24916441-8   b2146
LCM42688800-25223769-4   b185
LCM42688800-25504249-8   b1963
LCM42688800-25730041-6   b1017
LCM42688800-25730041-7   b1521
LCM42688800-25730041-8   b2106
LCM42688800-26484345-4   b95
LCM42688800-26990617-8   b1996
LCM42688800-27523737-4   b230
LCM42688800-27818617-6   b968
LCM42688800-27818617-7   b1480
LCM42688800-27818617-8   b2037
LCM42688800-28370745-4   b121
LCM42688800-29157241-4   b43
LCM42688800-29157241-5   b556
LCM42688800-29184345-6   b1122
LCM42688800-29184345-7   b1633
LCM42688800-29184345-8   b1881
LCM42688800-29258041-7   b1518
LCM42688800-29258041-8   b2103
LCM42688800-30086041-4   b0
LCM42688800-30086041-5   b522
LCM42688800-30086041-6   b1057
LCM42688800-30113145-7   b1590
LCM42688800-30113145-8   b1839
LCM42688800-30238137-4   b258
LCM42688800-30840345-4   b131
LCM42688800-30899641-8   b2096
LCM42688800-31066137-4   b273
LCM42688800-31746649-8   b1967
LCM42688800-31884345-6   b1087
LCM42688800-31884345-7   b1598
LCM42688800-31884345-8   b1846
LCM42688800-32560249-8   b1958
LCM42688800-33921369-4   b148
LCM42688800-33921369-5   b630
LCM42688800-34046617-8   b1990
LCM42688800-34353945-4   b57
LCM42688800-34353945-5   b570
LCM42688800-34353945-6   b1096
LCM42688800-34442041-4   b12
LCM42688800-34442041-5   b534
LCM42688800-34442041-6   b1069
LCM42688800-34442041-7   b1554
LCM42688800-34442041-8   b2151
LCM42688800-34579737-4   b225
LCM42688800-34594137-4   b271
LCM42688800-35255641-6   b1019
LCM42688800-35255641-7   b1523
LCM42688800-35255641-8   b2108
LCM42688800-36235737-4   b264
LCM42688800-36240345-6   b1116
LCM42688800-36240345-7   b1627
LCM42688800-36240345-8   b1875
LCM42688800-36516217-8   b2000
LCM42688800-37449369-4   b144
LCM42688800-37449369-5   b626
LCM42688800-37449369-6   b1176
LCM42688800-37729849-8   b1924
LCM42688800-37896345-4   b125
LCM42688800-37955641-8   b2091
LCM42688800-37970041-7   b1552
LCM42688800-37970041-8   b2149
LCM42688800-38277369-4   b186
LCM42688800-38402617-8   b2028
LCM42688800-38682841-4   b48
LCM42688800-38682841-5   b561
LCM42688800-38709945-6   b1127
LCM42688800-39638745-7   b1594
LCM42688800-39638745-8   b1843
LCM42688800-40591737-4   b276
LCM42688800-40596345-6   b1128
LCM42688800-40872217-6   b969
LCM42688800-40872217-7   b1481
LCM42688800-40872217-8   b2038
LCM42688800-41272249-8   b1971
LCM42688800-41409945-4   b52
LCM42688800-41409945-5   b565
LCM42688800-41409945-6   b1091
LCM42688800-41409945-7   b1602
LCM42688800-41409945-8   b1850
LCM42688800-42085849-8   b1961
LCM42688800-42311641-6   b1015
LCM42688800-42311641-7   b1519
LCM42688800-42311641-8   b2104
LCM1331114400-45563769-6   b1182
LCM1331114400-98808345-6   b1141
LCM1331114400-249096537-4   b290
LCM1331114400-287584569-4   b163
LCM1331114400-327618841-8   b2159
LCM1331114400-340829145-4   b108
LCM1331114400-385233241-6   b1028
LCM1331114400-385233241-7   b1530
LCM1331114400-385233241-8   b2118
LCM1331114400-390544249-8   b1985
LCM1331114400-448629241-4   b25
LCM1331114400-448629241-5   b547
LCM1331114400-448629241-6   b1082
LCM1331114400-448629241-7   b1565
LCM1331114400-448629241-8   b2165
LCM1331114400-467285017-8   b2014
LCM1331114400-476965849-8   b1933
LCM1331114400-491117337-4   b282
LCM1331114400-500798169-4   b196
LCM1331114400-529605369-4   b154
LCM1331114400-529605369-5   b633
LCM1331114400-529605369-6   b1186
LCM1331114400-569639641-4   b29
LCM1331114400-569639641-5   b551
LCM1331114400-569639641-6   b1086
LCM1331114400-577538937-4   b243
LCM1331114400-582849945-4   b100
LCM1331114400-582849945-5   b601
LCM1331114400-582849945-6   b1144
LCM1331114400-621808569-4   b201
LCM1331114400-650615769-4   b158
LCM1331114400-650615769-5   b637
LCM1331114400-650615769-6   b1190
LCM1331114400-680498617-6   b978
LCM1331114400-680498617-7   b1488
LCM1331114400-680498617-8   b2048
LCM1331114400-709305817-8   b2005
LCM1331114400-748264441-6   b1033
LCM1331114400-748264441-7   b1535
LCM1331114400-748264441-8   b2123
LCM1331114400-753575449-8   b1981
LCM1331114400-761474745-6   b1099
LCM1331114400-761474745-7   b1610
LCM1331114400-761474745-8   b1858
LCM1331114400-801509017-6   b982
LCM1331114400-801509017-7   b1492
LCM1331114400-801509017-8   b2052
LCM1331114400-830316217-8   b2010
LCM1331114400-839997049-8   b1939
LCM1331114400-854148537-4   b286
LCM1331114400-863829369-4   b192
LCM1331114400-882485145-4   b66
LCM1331114400-882485145-5   b576
LCM1331114400-882485145-6   b1103
LCM1331114400-882485145-7   b1614
LCM1331114400-882485145-8   b1862
LCM1331114400-940570137-4   b239
LCM1331114400-945881145-4   b103
LCM1331114400-945881145-5   b604
LCM1331114400-945881145-6   b1147
LCM1331114400-990285241-8   b2115
LCM1331114400-1003495545-4   b73
LCM1331114400-1043529817-8   b2043
LCM1331114400-1082017849-8   b1931
LCM1331114400-1232306041-6   b1037
LCM1331114400-1285550617-6   b985

[Dmitriy40]

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

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

А почему нет, собственно?
Малые $qr$ до нескольких тысяч можно проверить отдельно ("унивесальным софтом" но с заданными в параметрах длиной цепочки и количеством делителей).

Для больших значений порога $M$ придётся перебирать простые очень уж далеко, это попросту нереально.

[Dmitriy40]

Вот скажем для поиска пятнашки нужно проверять простые до $\sqrt{8\cdot10^{34}/17/2}\approx 4.85\cdot10^{16}$ (худший случай, подставляем на место с 2), это нереально долго, я до 2e10 проверял больше суток (по кусочкам в несколько потоков), а это в 2.4млн раз больше.

-- 09.11.2022, 17:37 --

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

А точнее, что за 5 правильных чисел и где именно вокруг?

Сорри, отвлекли и не успел сразу ответить: это числа 32p-2,32p-1,32p,32p+1,32p+2, только они есть в любой десятке.