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

[Yadryara]

Спасибо. Поступил так же: посчитал средневзвешенную длину и разделил на первоначальную длину:

$$\lfloor{\dfrac{2.783}{23}}\rfloor = 0.121$$

Что заметно отличается от $0.129$ полученного другим способом.

Тогда тем более интересно будет увидеть всю строчку vc[], обсчитать и сравнить с прогнозом по HL-1.

[Yadryara]

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

При необходимости можно пожалуй и C11 посчитать

А вот теперь неплохо бы посчитать. Заодно проверим наши прогнозы и по доле чистых, и по скорости. 14 часов?

Вверху пока сравнить не могу, так что пошёл вниз, а внизу не помешает точность повыше, с учётом C11. Сравниваю оценки по чистым по HL-1 со своим 2-м способом без поправки.

$\tikz[scale=.1]{ \draw[step=20cm] (0,300) grid +(60,50); \draw (0,350) -- (60,350); \draw (0,330) -- (60,330); \draw (0,310) -- (60,310); \node at (10,345){\text{Диапазон}}; \node at (30,345){\text{HL-1}}; \node at (50,345){\text{Y2}}; \node at (10,335){$\leqslant 59\#$}; \node at (10,325){$\leqslant 61\#$}; \node at (10,315){$\leqslant 67\#$}; \node at (10,305){$\leqslant 71\#$}; \node at (30,335)[red]{\text{0.002}}; \node at (30,325)[red]{\text{0.027}}; \node at (30,315)[red]{\text{0.511}}; \node at (30,305){\text{10.970}}; \node at (50,335)[red]{\text{0.002}}; \node at (50,325)[red]{\text{0.040}}; \node at (50,315)[red]{\text{0.728}}; \node at (50,305){\text{}}; }$

Надеюсь понятно, что красным обозначил значения меньше 1-цы.

[Dmitriy40]

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

Тогда тем более интересно будет увидеть всю строчку vc[], обсчитать и сравнить с прогнозом по HL-1.

На PARI я могу получить весь vc[] для 71# дней за 25. Многопоточно на асме старой программой - за 35. И то и другое влом, слишком долго.
Что значит "обсчитать" вообще не понял.

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

А вот теперь неплохо бы посчитать. Заодно проверим наши прогнозы и по доле чистых, и по скорости. 14 часов?

Запустил, посмотрим.

[Yadryara]

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

Что значит "обсчитать" вообще не понял.

Я вот думаю: начать объяснять издалека или в режиме вопросов и ответов, с важного начинать или с второстепенного. Хочется покороче.

Второстепенное: заполнить недостающую клеточку в таблице выше.
Важное: точнее оценить вот этот параметр:

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

В среднем, если проверять кортежи безыдейно, то для нахождения $\frac1{11}$ всех кортежей нужно проверить ту же долю, то есть 9.1% кандидатов. Если проверять от чистых к грязным, то 5.2%.

Понятно, как я посчитал эти 5.2% ? То есть вижу уменьшение среднего обсчёта по меньшей мере в 1.75 раза.

По меньшей мере — потому что для 71# жду улучшения примерно до 5%.

Далее сравниваю между собой два периода. Не по скорости, а по количеству кандидатов.

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

Значит до 1-го кортежа проверить нужно будет в среднем почти 800 квадриллионов кандидатов. Что конечно гораздо больше чем все 293 квадрика в нынешнем 67#.

293.4 квадра на 0.51 кортежа это примерно 575 квадров на кортеж.

При счёте по 71# , видимо, всё-таки поменьше чем 800:

$293.4\cdot52\cdot0.05\approx 763$ квадра на кортеж.

[Dmitriy40]

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

Я вот думаю: начать объяснять издалека или в режиме вопросов и ответов, с важного начинать или с второстепенного. Хочется покороче.

Достаточно указать что мне надо посчитать. Надеюсь не всю строку vc[] для 71#.

Константа C11 считается, первая итерация (из 54) заняла 4ч9м, это должно быть где-то 1/6 всего времени. Но может и 1/4, вроде с увеличением номера константы коэффициент падает ...
Две итерации завершились за 4ч53м.

[Dmitriy40]

А три итерации за 5ч44м.
Четыре за 6ч36м.

-- 14.08.2024, 17:39 --

Я тут немного поисследовал свою новую программу.
Инициализация таблиц занимает 0.7с.
Проверка по простым 71-128 занимает 31.5% общего времени и оставляет 1/15.7 кандидатов.
Проверка по простым 128-256 занимает 40.5% и оставляет 1/197 кандидатов.
Проверка по простым 256-32768 занимает 28% и оставляет 1/28.7e6 кандидатов.
Проверка по простым 32768-131072 занимает меньше секунды и оставляет 1/308e6 кандидатов.

При этом проверка по 128-256 проверяет сразу все 23 остатка для каждого входного кандидата. Если бы её переделать чтобы проверялись по 16 кандидатов по 23 простым подряд, то по идее может стать быстрее в 3.5 раза, т.е. с 40.5% уменьшится до 12%, выигрыш 29% или 2.5 месяца счёта. Неплохо, буду думать как сделать.
А если ту же идею применить уже и к первой проверке, то может получиться и ещё неделю выиграть ... Не, неактуально.

[Yadryara]

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

Надеюсь не всю строку vc[] для 71#.

Ну, 5 левых и 7 правых ведь уже посчитаны. Чтобы матожидание дошло до 1-ки надо добраться до длины 34. Значит ещё 11 левых.

Но это уже тонкости. Главный итог ведь уже понятен: правильное изменение порядка обсчёта в среднем уменьшает объём этого обсчёта в 1.8 раза.

[Dmitriy40]

С11 посчиталась за 12ч.

[Dmitriy40]

Поиск 19-252.
Вчера утром нашлась цепочка со всего двумя "дырками" (по терминологии НМ, подчёркнуты):
2711238988784023109503627:[0, 6, 12, 30, 70, 72, 90, 96, 120, 126, 132, 156, 162, 202, 210, 222, 240, 246, 252], valids=17
До этого было лишь по три "дырки" (8шт).

Из другого интересного нашлось 8шт с valids=18 с распределением длин начиная с 18: 1, 1, 4, 1, 1.
Центральные только 13-ки (7шт), не длиннее.

[Dmitriy40]

Три дня назад доделал программу перебора в порядке возрастания загрязнённости групп, группы перебираются по 29#/17 (все простые по 29 за исключением 17), таковых вариантов 13824:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 68, 278, 800, 1896, 3140, 3578, 2400, 1208, 352, 78, 20, 2], sum=13824
На текущий момент выполнено 1% всего перебора 67#, перебраны две первые группы (и 15% третьей) и две последние (на разных компах).
Из интересного нашлось лишь:
2492836870083454588343317: [ 0, +6, 12, 30, 42, -52, 72, -82, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246, 252], len=20, valids=18 - в последней группе
3286904276729247309856087: [ 0, 6, +12, 30, 42, 72, 90, 96, 120, 126, 132, 156, 162, 180, 210, 222, 240, 246,+252], len=17, valids=17 - во второй группе
3783306150919457171319677: [ 0, 6, 12, 30, 42, 72, +90, 96, 120, 126, 132, 156, 162, 180, 210,+222, 240, 246, 252], len=17, valids=17 - во второй группе
7752657149781561151874821: [ 0, 6, 12, 30, 42, 72, 90, 96, 120, 126,+132,+156, 162, 180, 210, 222, 240, 246, 252], len=17, valids=17 - в третьей группе
Как-то пока не сильно похоже что левые группы (а в них перебрано раз в 5 больше) дают лучше результаты ...

[Yadryara]

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

Как-то пока не сильно похоже что левые группы (а в них перебрано раз в 5 больше) дают лучше результаты ...

А Вы обратный анализ делали?

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

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

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

[Dmitriy40]

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

А Вы обратный анализ делали?

Не делал: тогда было не до него, да и показалось сложным. А оказывается остатки до 67 и не надо считать, достаточно лишь тех остатков, группы по которым строятся и если интересуют лишь группы по 29#/17, то и вариантов всего 13824, а не квадриллионы. Так что сейчас сделал анализ, только вот по этим группам что сейчас запущены в работу:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 68, 278, 800, 1896, 3140, 3578, 2400, 1208, 352, 78, 20, 2], sum=13824
Две известные грязные 19 оказались в группах 25 и 27:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0], sum=2
Все найденные старой программой (до 1.7e24) valids=18:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 18, 14, 19, 21, 8, 4, 1, 0, 0], sum=89
Все найденные старой программой (до 1.7e24) len=19:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26, 533, 2765, 9855, 27852, 55047, 75957, 60741, 36419, 12331, 3340, 1014, 130], sum=286010
Все вообще цепочки от старой программы (до 1.7e24):
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 439, 8910, 42878, 144028, 395778, 754166, 994603, 767660, 446753, 147427, 38313, 11189, 1265], sum=3753409
Видно что везде количество найденных цепочек в общем коррелировано с числом вариантов в группах, т.е. нет явного преимущества способа перебора.
Пересчитывать всё это в группы 67# долго и не вижу смысла, всё равно я не могу перебирать в их порядке. Хотя и интересно конечно, завтра пожалуй тоже сделаю.

[Yadryara]

19+17           
19+18          4      439    109.75
19+19         68     8910    131.03     0.838  
19+20        278    42878    154.24     0.850
19+21        800   144028    180.03     0.857
19+22       1896   395778    208.74     0.862
19+23       3140   754166    240.18     0.869
19+24       3578   994603    277.98     0.864 
19+25       2400   767660    319.86     0.869
19+26       1208   446753    369.83     0.865
19+27        352   147427    418.83     0.883
19+28         78    38313    491.19     0.853
19+29         20    11189    559.45     0.878
19+30          2     1265    632.50     0.885
_____________________________________________
           13824  3753409    271.51     0.866*

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

* Самые надёжные данные — в середине: $(0.862, 0.869, ..., 0.865)$, что в среднем как раз даёт $0.866=1-0.134$.

Вот здесь у меня получалось это же число:

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

Попытался посчитать матожидание количества кортежей для 67# уже 3-м способом. По HL-1 было 0.51 кортежа. Однако у меня получается 0.51 только если взять $p=0.134$.

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

Две известные грязные 19 оказались в группах 25 и 27:
29#/17: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0], sum=2

А я здесь вижу, что в группах 23 и 25.

[Dmitriy40]

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

А я здесь вижу, что в группах 23 и 25.

Трижды пересчитал нолики, всё же левый 0 в группе 19+0, а левая 1 в группе 19+25, правая в 19+27.

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

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

Похоже для 67# это вообще мало что даст и можно было не париться с порядком обхода ...
Впрочем, ладно, поменяю порядок обхода у компов на обратный (боле быстрый комп с конца).

[Dmitriy40]

Сделал анализ для 67#.
Две известные грязные 19 оказались в группах 18 и 20:
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], sum=2
Все найденные старой программой (до 1.7e24) valids=18:
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 3, 6, 16, 11, 16, 13, 15, 4, 1, 1], sum=89
Все найденные старой программой (до 1.7e24) len=19:
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 81, 449, 1878, 6320, 16071, 32055, 49000, 58574, 53464, 37274, 19767, 8038, 2346, 577, 99, 8], sum=286010
Все вообще цепочки от старой программы (до 1.7e24):
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 32, 233, 1630, 8627, 34467, 105441, 250891, 467369, 675058, 760428, 661735, 442269, 225347, 87557, 25595, 5730, 893, 103, 3], sum=3753409
И тоже на первый взгляд не вижу преимущества в порядке обхода ... Где вариантов больше, там в общем цепочки и находятся ...

-- 24.08.2024, 13:11 --

Для сравнения, распределение по группам предыдущего поиска (выполнено 6.1% от 67#), без оптимизации порядка обхода:
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 24, 181, 803, 3292, 9972, 22813, 40959, 57111, 61770, 50875, 32271, 15726, 5658, 1534, 297, 44, 1], sum=303334

-- 24.08.2024, 13:34 --

А вот то что насчиталось за три дня по первым и последним двум группам в 29#/17 (и 15% третьей группы):
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 105, 466, 1664, 3931, 6779, 7887, 6217, 3420, 1861, 2225, 3759, 4878, 4824, 3061, 1436, 431, 74, 2], sum=53028
И оно же отдельно для левых двух групп (и 15% третьей):
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 105, 466, 1664, 3931, 6778, 7882, 6173, 3201, 1073, 215, 25, 2], sum=31523
И правых двух групп:
67#: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 44, 219, 788, 2010, 3734, 4876, 4824, 3061, 1436, 431, 74, 2], sum=21505