Симметричные кортежи из последовательных простых чисел

[Yadryara]

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

Ну и просто по приколу самая наибольшая (ближе всех к 67#):
7858183652829941796270727:

Я так понимаю, что у этого способа есть и ещё огромный минус.

Мало того, что кандидаты генерятся в непонятно какой последовательности по всему диапазону $0-67\#$, так она ещё и непонятна нам, а компу понятна.

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

Правильно понимаю? Пока не придумано как перезапустить с посчитанной точки?

[Dmitriy40]

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

Мало того, что кандидаты генерятся в непонятно какой последовательности по всему диапазону $0-67\#$, так она ещё и непонятна нам, а компу понятна.

И мне понятна, просто я не указываю эту часть инфы из лога так как она не несёт никакого полезного смысла для нас. Вот пример полной строки из лога (показанной выше):
[66,55,25]=179090:1791808741444077180184441: [ 0, 6, 12, 30, 42, -58, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222,-228, 240, 246, 252], len=21, valids=19
Видим остатки по 67,61,59, плюс значение из их общей таблички (это КТО на них трёх), которое и передаётся в мою программу аргументом (ради упрощения её кода, в PARI считать КТО в разы легче). Только остатки вычисляются не от x, а от x+252 - так надо, считать удобнее и быстрее, не буду пока лезть в дебри.
Чуть подробнее ниже.

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

Правильно понимаю? Пока не придумано как перезапустить с посчитанной точки?

Возможность перезапуска закладывалась изначально, ограничением длины вычисляемого куска из полного размера 293e15.. При перезапуске ошибочного куска счёта потери составят от 5 минут до получаса (зависит от того на каком компе считается). Но для перезапуска надо самому посмотреть где остановилось, поправить (убрать последний насчитанный кусок из лога чтобы в нём не получилось дублей), указать в файле .gp откуда начать считать и запустить дальше. Потерять при сбое 5...30 минут мне не жалко, это случается типа раз в месяц-два (чаще всего свет рубанут).
Собственно в .gp файле указываются остатки по 67,61.59, они и перебираются внешней программой (на PARI или чём угодно) и прямо указываются в логах, и в ней же производится допроверка кандидатов. И именно по этой границе удобно перезапускать счёт при любых сбоях, ошибках или желании. Или делить работу между несколькими компьютерами. Внутри программы производится сначала перебор по 43,47,53 (объединёнными в одну таблицу), для каждого перебираются 2,17,31,37,41 (тоже одной общей таблицей), для каждого этого перебираются оставшиеся (тоже по одной общей таблице). Итого три таблицы внутри программы (22848, 11520, 13824 элементов) и один перебор (с допроверкой найденных кандидатов) снаружи. И если бы не желание ускорить проверку на простоту, то можно было обойтись буквально сотнями килобайт требуемой памяти (независимо от количества потоков), но ради скорости программа при запуске строит себе большую табличку размером 13824*16*216 слов (по два байта) на 95МБ для ускорения проверки делимости на простые 256...32768 (делимость на простые 32768...131072 проверяется гораздо дольше, но на общую скорость влияние мизерное). Мне 100МБ памяти не жалко, тем более что табличка общая на все потоки сразу.
Поэтому в логах (для каждого компьютера) числа появляются в порядке увеличения остатков по 59, потом по 61, потом по 67. Ну или уменьшения, кому как нравится. Порядок тоже можно поменять при желании (но тогда неудобно стыковать разные компы между собой чтобы не считать повторно). В каком порядке в логах остатки по меньшим простым я точно не знаю потому что не интересовался и не задавал, но это тоже легко установить, кроме самого внутреннего цикла (длиной 13824), там проведена сортировка по величине (x*d)%M, где M это произведение соответствующих простых (3...29 кроме 17), x это значение остатка по модулю M, а d обратный элемент по этому же модулю от произведений остальных простых (2,17,31...67) - так надо для ускорения вычисления КТО по модулям малых простых (71...256) в самом внутреннем цикле.
Так что нет, всё в порядке с перезапуском не с самого начала, потери времени несущественные. Правда перезапуск требует ручной работы, не автоматически, но меня устраивает. Предыдущая программа работала больше года ровно в таком же режиме.

[Yadryara]

Ну, хорошо. Я пока не вникал в нюансы, но поправив Вашу с gris-ом программу, увидел, что остатки по каждому простому перебираются лексикографически:

 9     [0, 12, 24, 30, 42, 54, 60, 72, 84]

 0 (0.E-9) - 30030 (3.0 E4)

2   [1]

3   [1, 2]

5   [2, 4]

7   [1, 6]

11   [7, 8]

13   [3, 4, 8, 12]

64 kandidata

28057   1   2   1   7   3
4957   1   2   1   7   4
2647   1   2   1   7   8
337   1   2   1   7   12
14407   1   2   1   8   3
21337   1   2   1   8   4
19027   1   2   1   8   8
16717   1   2   1   8   12
6607   1   2   6   7   3
13537   1   2   6   7   4
11227   1   2   6   7   8
8917   1   2   6   7   12
22987   1   2   6   8   3
29917   1   2   6   8   4
27607   1   2   6   8   8
25297   1   2   6   8   12
10039   1   4   1   7   3
16969   1   4   1   7   4
14659   1   4   1   7   8
12349   1   4   1   7   12
26419   1   4   1   8   3
3319   1   4   1   8   4
1009   1   4   1   8   8
28729   1   4   1   8   12
18619   1   4   6   7   3
25549   1   4   6   7   4
23239   1   4   6   7   8
20929   1   4   6   7   12
4969   1   4   6   8   3
11899   1   4   6   8   4
9589   1   4   6   8   8
7279   1   4   6   8   12
18047   2   2   1   7   3
24977   2   2   1   7   4
22667   2   2   1   7   8
20357   2   2   1   7   12
4397   2   2   1   8   3
11327   2   2   1   8   4
9017   2   2   1   8   8
6707   2   2   1   8   12
26627   2   2   6   7   3
3527   2   2   6   7   4
1217   2   2   6   7   8
28937   2   2   6   7   12
12977   2   2   6   8   3
19907   2   2   6   8   4
17597   2   2   6   8   8
15287   2   2   6   8   12
29   2   4   1   7   3
6959   2   4   1   7   4
4649   2   4   1   7   8
2339   2   4   1   7   12
16409   2   4   1   8   3
23339   2   4   1   8   4
21029   2   4   1   8   8
18719   2   4   1   8   12
8609   2   4   6   7   3
15539   2   4   6   7   4
13229   2   4   6   7   8
10919   2   4   6   7   12
24989   2   4   6   8   3
1889   2   4   6   8   4
29609   2   4   6   8   8
27299   2   4   6   8   12

62 ms

Центральной проблемой ведь до сих пор остаётся генерация кандидатов по всему диапазону? В данном случае $0-13\#$.

[Dmitriy40]

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

увидел, что остатки по каждому простому перебираются лексикографически

В работающей программе - нет, не так, лексикографически перебираются остатки по простым 2,17,31...53, как будут перебираться остатки по 59,61,67 выбирает внешняя программа, а по простым 3..29 кроме 17 перебор я выше указал как идёт, в порядке увеличения величины (x*d)%M (M=29#/2/17).
Но при показе результатов я руками сортирую по возрастанию начального числа кортежа (в логах такой сортировки нет). Ради красоты и удобства.

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

Центральной проблемой ведь до сих пор остаётся генерация кандидатов по всему диапазону? В данном случае $0-13\#$.

Не уверен что понял вопрос: у меня все проблемы решены (кроме желаемой в мечтах скорости поиска). По указанным простым (3...29 кроме 17, это 29#/2/17) сформирована табличка длиной 13824, никаких проблем с ней нет, как и с остальными двумя в программе. Вопрос деления полного 67# на поддиапазоны (четыре таблички, одна снаружи) - вопрос отдельный и хитрый, там много подводных камней, опять же не хочу пока лезть в дебри, выбрал и выбрал, на то есть веские основания и результаты тестов.
Есть странная проблема со скоростью проверки делимости на 128...256, оно почему-то вдвое/втрое медленнее проверки по простым 71...128 (и количество простых не так важно), но таков уж код и имеющиеся команды процессора, не получается сделать быстрее. Или мне не хватает понимания арифметики по модулю чтобы сократить и ускорить код, работает ну и пусть пока считает.
Кстати про скорость, после полной реализации всех проверок оказалось что скорость внутреннего цикла выше предыдущей всего на 25%, почти весь остальной выигрыш получается за счёт замены линейного перебор по простым 53...67 на перебор только по допустимым остаткам (в чём и состояла цель новой программы).

-- 11.08.2024, 13:38 --

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

При перезапуске ошибочного куска счёта потери составят от 5 минут до получаса (зависит от того на каком компе считается).

Т.е. за указанное время 5...30 минут перебираются все 13824*11520*22848=3.64e12 (триллионов!) вариантов (добавок по новой терминологии НМ) на интервале 53#, примерно по полмиллиарда в секунду в каждом потоке. А хочется ещё хотя бы на порядок быстрее ...

[Yadryara]

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

Не уверен что понял вопрос

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

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

Ну и просто по приколу самая наибольшая (ближе всех к 67#):
7858183652829941796270727:

Ведь лучше было искать не возле 78е23, а повыше уже проверенного, то есть 17е23. Ответ: не получается на периоде 67# генерить кандидатов иначе как по всему диапазону $0-67\#$. Так ?

[Dmitriy40]

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

Ответ: не получается на периоде 67# генерить кандидатов иначе как по всему диапазону $0-67\#$. Так ?

Да, так. Размазывание по всему 67# происходит уже в самом внутреннем цикле (где перебираются только простые 3...29 кроме 17), куда очень и очень не хочется добавлять лишний код ограничения величины чисел (ещё и потому что там просто физически нет самих чисел, только их остатки по модулям малых простых, а считать для всех ещё и КТО это убиться). А куда можно безболезненно добавить (проверка делимости на простые 256...32768) - даже в теории не даст заметного ускорения (максимум несколько процентов). Фактически эта невозможность - плата за скорость, которая важнее. Если придумаю как не потерять в скорости - может и добавлю, хотя лишние 22% времени счёта уже проверенного куска от 67# меня не сильно напрягают.

-- 11.08.2024, 14:29 --

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

Размазывание по всему 67# происходит уже в самом внутреннем цикле (где перебираются только простые 3...29 кроме 17)

Поясню подробнее: внутренний цикл для заданного x1 вычисляет выражение (x1+Mx1*(((y1-x1)*d)%My1))%p для всех p=71...128 (My1=29#/2/17, Mx1=67#/My1, d=Mod(1/Mx1,My1)), причём сразу для 32-х чисел y1 (они все меньше My1) из общего количества 13824. И хотя в скобках стоит корректная КТО в полном 67# (что и даёт размазывание по всему 67#), физически она не вычисляется, считаются сразу только 32 остатка по каждому простому p для проверки на допустимость. Потому и быстро (порядка 2млрд вариантов/добавок в секунду в одном потоке). Как не слишком тормозя вычислить ещё и скобку для ограничения диапазона, хотя бы приблизительно, я пока не знаю, ещё подумаю, мысли есть, но пока других забот хватает.

-- 11.08.2024, 15:11 --

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

И хотя в скобках стоит корректная КТО в полном 67# (что и даёт размазывание по всему 67#)

Она перебирается по y1, что даёт перебор внутри My1=29#/2/17 (вместо 13# из вашего вопроса), но значения КТО оказываются размазанными по всему 67# (потому что сначала перемешиваются домножением на d по модулю My1, а главное потом домножаются на огромный Mx1). Ну вот так КТО считается. Не только у меня, в PARI ровно так же, да и вообще везде так же, даже если по немного другим формулам (их две с половиной есть разных для вычисления КТО), результат всегда одинаков.
А по x1 перебирать нельзя, придётся делать страшно медленное %My1 внутри внутреннего цикла. Скорость наше всё!

[Dmitriy40]

Сделал пропуск первых 21.6% от 67# (1.7e24), скорость увеличилась на 14%. Экономия составит чуть больше месяца счёта, вместо 8.6 месяцев будет 7.4. Как-то не слишком актуально.

[Yadryara]

Dmitriy40, вроде могут пригодиться вот эти данные по малопростым:

67#: 0, 0, 0, 0, 0, 54760, 6792018, 325858198, 8732689082, 153606059908, 1913747177340, 17483063702860, 119249071095310, 615440511892708, 2432725989818718, 7447022885574328, 17813512167763926, 33491264807265158, 49603797522180000, 57819061781785358, 52856050981018074, 37699907542234036, 20848732917709526, 8879811423403526, 2895245491002764, 719253136438230, 135295969437234, 18878969508802, 1836531247768, 107619357728, 2666478240, sum=293416757467545600

Что если искать чистую 19-ку надо прежде всего среди самых чистых, то есть среди 54760 кандидатов, а затем уже среди 6792018 и так далее...

Вы вроде не сохранили эти 54760. Но можно пересчитать, вроде это довольно старый счёт был, с тех пор придумали способы ускорения, расщепление, например.

[Dmitriy40]

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

Что если искать чистую 19-ку надо прежде всего среди самых чистых, то есть среди 54760 кандидатов, а затем уже среди 6792018 и так далее...

Идея интересная, подумаю как её реализовать.

[Yadryara]

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

для произвольного пятикратно загрязнённого паттерна их 391e12,

Дак а чего нам париться насчёт произвольных пятикратно загрязнённых паттернов, если можно посчитать конкретные 27380 паттернов. Каждый из них проверять дальше, по простым от 71 до корня.

Я думаю, надо на других паттернах этот способ проверить, посмотреть сколько находится чистых и как быстро. Для 19-252 сильно загрязнёнными, видимо, можно пренебречь.

[Dmitriy40]

Ни среди 54760, ни среди 6715850 (чуть меньше всех 6792018) нет ни одного кортежа длиной 19 и более, независимо от valids (количества совпадений с паттерном).

[Yadryara]

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

Вы вроде не сохранили эти 54760. Но можно пересчитать, вроде это довольно старый счёт был, с тех пор придумали способы ускорения

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

Да, это был довольно старый счёт, завершён не позднее 5 апреля:

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

Если что я 67# для 19-252 уже посчитал

Но сколько потоков и сколько часов — не сказано.

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

Ни среди 54760, ни среди 6715850 (чуть меньше всех 6792018) нет ни одного кортежа длиной 19 и более

А какие есть? Какой длины и с каким валидс? 18 есть?

-- 12.08.2024, 17:41 --

Надо посмотреть средние потери. Можно ли статистику примерно в таком виде:

Было:     v+op     штук   
         19+ 5    54760

Стало:   14+ 4    32000
         15+ 3    18000
         15+ 2     4760

Было:     v+op       штук   
         19+ 6    6792018

Стало:   

[Yadryara]

Надеюсь, понятно зачем нужна статистика. Вот у нас есть 26 групп:

19+ 5               54760
19+ 6             6792018
19+ 7           325858198
19+ 8          8732689082
19+ 9        153606059908
19+10       1913747177340
19+11      17483063702860
19+12     119249071095310
19+13     615440511892708
19+14    2432725989818718
19+15    7447022885574328
19+16   17813512167763926
19+17   33491264807265158
19+18   49603797522180000
19+19   57819061781785358
19+20   52856050981018074
19+21   37699907542234036
19+22   20848732917709526
19+23    8879811423403526
19+24    2895245491002764
19+25     719253136438230
19+26     135295969437234
19+27      18878969508802
19+28       1836531247768
19+29        107619357728
19+30          2666478240
_________________________
       293416757467545600

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

[Dmitriy40]

Из 54760 кортежей (8 минут счёта) самые длинные:
1113364620831480865011091: [ 0, +6, +12, +30, +42, 72, 90, +96, 120,+126, 132,-148, 156, 162,+180, 210, 222,+240, 246, 252], len=12, valids=11
1985883239156407011705211: [ +0, 6, +12, 30, +42, -58, 72, -88, 90, 96,-118,+120, 126,+132,+156,+162, 180,+210, 222,+240, 246,+252], len=12, valids=9
И он же с наибольшим valids=11.
len=11 или valids=10:
200463998808083498622061: [ 0, +6, 12, -16, -28, 30, +42, -58, +72, -82, +90, +96,+120, 126,+132,+156, 162,-166, 180,+210,+222,+240,+246,+252], len=11, valids=6
4104435721456023968388301: [ 0, 6, 12, +30, 42, -58, +72, 90, +96, 120, 126, 132, 156,+162,+180,+210, 222,+240,+246,+252], len=11, valids=10
4459632816520166880338671: [ 0, 6, +12, 30, 42, +72, +90, +96,+120,+126,+132, 156,+162, 180,-186, 210, 222,+240, 246, 252], len=11, valids=10
6384480533474561145183377: [ +0, 6, +12, -26, 30, +42, 72, 90, 96, 120,+126,+132, 156,+162, 180,+210,+222, 240, 246,+252], len=11, valids=10
6872402632701873188625631: [ +0, +6, 12, 30, 42, 72, +90, +96, 120, 126,+132, 156,+162,+180, 210,+222, 240,+246, 252], len=10, valids=10
Статистика (len\valids: штук):

Используется синтаксис Text

        11      10      9       8       7       6       5       4       3       2       1       0
12      1               1
11              3                               1
10              1       6       17      5       2
9                       7       41      44      22      4
8                               44      174     173     74      7       2
7                                       218     521     439     146     16      2
6                                               655     1468    1076    261     24
5                                                       1794    3073    1516    281     11
4                                                               3956    5012    1707    164     9
3                                                                       6181    5499    1193    62
2                                                                               6975    3931    395
1                                                                                       4695    1300
0                                                                                               1551

Из 6715850 (часть из всех 6792018) (35 минут счёта) самые длинные:
2961099763918228380153527: [ 0, 6, 12, +30, 42, +72, 90, 96, 120, 126, 132, 156,+162,-164, 180,-182,+210,+222,-230, 240,+246,+252], len=15, valids=12
3559430634064690374709801: [ +0, 6, 12, +30, 42, 72, -78, 90, 96,+120, 126,-130,+132, 156, 162, 180, 210,+222, 240,+246,+252], len=14, valids=12
2588146182951700519524197: [ 0, +6, 12, +30, +42, +72, 90, 96, 120,-122, 126, 132, 156,+162,-164, 180,-182,+210, 222, 240,+246,+252], len=14, valids=11
6477418661511178632567137: [ 0, 6, 12, +30, 42, -44, +72, +90, +96,+120, 126, 132, 156,+162,-170,+180,-194, 210, 222, 240,+246, 252], len=14, valids=11
180577207620532549852847: [ +0, 6, 12, +30, 42, -44, +72, 90, 96,+120,+126,+132, 156,+162,-164, 180,-194, 210,+222,-230,+240, 246, 252], len=14, valids=10
13022709420728675501761: [ 0, +6, +12, -22, 30, +42, -58, 72, -82, -88, +90, +96, 120, 126,+132,-148, 156,+162,+180,+210, 222, 240,+246, 252], len=14, valids=9
3298449361800147520529491: [ 0, +6, 12, 30, 42, -70, 72, -78, -88, +90, +96,-118, 120, 126,+132,+156, 162,-166,+180, 210,+222,+240,+246,+252], len=14, valids=9
4804624105589416429446947: [ 0, +6, +12, 30, 42, 72, 90, +96, 120, 126, 132,+156, 162,+180, 210, 222,+240, 246, 252], len=13, valids=13
Плюс 8шт с valids=11, 8шт с valids=10, 8шт с valids=9 и 4шт с valids=8 (все len=13).
Кортежи короче len=13 не подсчитывались.

Из общего времени 7.5 минут занимает генерация кортежей, остальное их проверка.

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

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

Пока я могу подсчитать (на PARI) только две группы: 19+5 и почти всю 19+6. Уже следующая 19+7 с 326млн будет считаться несколько дней.

[Yadryara]

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

Пока я могу подсчитать (на PARI) только две группы: 19+5 и почти всю 19+6. Уже следующая 19+7 с 326млн будет считаться несколько дней.

А, ну и так вроде понятно, что 19+7 считать пока и не надо. Вроде бы 19+9 более перспективная группа.

-- 12.08.2024, 19:55 --

Dmitriy40, а ну так обратный анализ же можно сделать.

У Вас в логах полно отсортированных цепочек. Можно проверить их по модулям до 67 и определить из каких они групп.