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

[Yadryara]

В том что по этому прогнозу получалось в 10 и в 6 раз больше.

[Dmitriy40]

Т.е. по С9 было в 10 раз больше чем сейчас тоже по С9? Ну-ну.
Посмотрите какая начальная точка была тогда, может слишком маленькая, потому и ожидание завышено. Если константы (и их количество) одинаковы, то разница только в пределах интегрирования.

[Yadryara]

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

Т.е. по С9 было в 10 раз больше чем сейчас тоже по С9?

Нет, не по С9, а по одинаковой лёгкости. Вот для C10 тот же приём:

Номер   Паттерн   Прогноз по HL1     Норм.   Лёгкость
                            штук    формул     поиска
                          
                     для 0 - 71#

1.     21-324-1            0.171     2.435      0.070
2.     21-324-2            0.460     6.575      0.070  *

Сначала прошёл по первому паттерну слева направо и получил лёгкость 0.070. Затем приравнял лёгкость для второго паттерна к лёгкости первого и прошёл уже справа налево, получив 0.460.

А на каком основании я приравнял? На основании многочисленной предыдущей статистики. Для одних и тех же диаметров (при одинаковой длине) лёгкости были очень близки.

Может ещё быть ошибка при обсчёте 1-го паттерна...

[Yadryara]

Ну вот ещё одно неравенство лёгкости обнаружилось:

Номер   Паттерн   Конст.   Прогноз по HL1     Норм.   Лёгкость
                     max             штук    формул     поиска

                              для 0 - 73#

1.     21-336-1        9            0.068     1.752      0.039
2.     21-336-2        9            0.300     2.561      0.117
3.     21-336-3       10            0.154     1.186      0.130

                              для 0 - 79#

1.     21-336-1        9            2.766     1.752      1.579
2.     21-336-2        9            8.044     2.561      3.140
3.     21-336-3       10            3.780     1.186      3.188

1-й паттерн заметно отличается.
Буду дальше считать 336-й диаметр. 10 таких паттернов имеется.

[Yadryara]

Забываю спросить:

Точностью Вы пожертвовали ради скорости. Возможно ли ещё пожертвовать в случае необходимости?

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

4-й и 5-й паттерны совпали по лёгкости со 2-м и 3-м. Добавил в таблицу ещё и количество обсчитанных констант. Для стартовых точек интегрирования $10^8$ — $10^{16}$ матожидания всё равно до тысячных одинаковые.

Номер   Паттерн   Конст.   Прогноз по HL1     Норм.   Лёгкость
                     max             штук    формул     поиска

                              для 0 - 73#

1.     21-324-1       10            2.504     2.435      1.028
2.     21-324-2       10            1.017     6.575      0.155  трудный

3.     21-336-1        9            0.068     1.752      0.039  трудный
4.     21-336-2        9            0.300     2.561      0.117
5.     21-336-3       10            0.154     1.186      0.130
6.     21-336-4        9            0.154     1.423      0.109
7.     21-336-5        9            0.210     1.942      0.108
8.     21-336-6        9            0.296     3.139      0.094

Попытался понять, почему же некоторые паттерны трудные:

                                   30        42
1.  [0, 12, 30, 42, 54, 60, 72,  84, 114, 120, 162,

                          24  30        24
2.  [0, 12, 30, 42, 54, 60, 84, 114, 120, 144, 162,


                                   42        42
1.  [0,  6, 18, 36, 48, 60, 66,  78, 120, 126, 168,

2.  [0,  6, 18, 36, 48, 60, 66,  90, 120, 126, 168,
3.  [0,  6, 18, 36, 48, 66, 78,  90, 120, 126, 168,
4.  [0,  6, 18, 36, 48, 66, 78,  90, 126, 150, 168,
5.  [0,  6, 18, 36, 60, 66, 78,  90, 120, 126, 168,

                              30        30
6.  [0,  6, 18, 36, 60, 66, 78, 108, 120, 150, 168,

7.  [0,  6, 18, 48, 60, 66, 78,  90, 120, 126, 168,
8.  [0,  6, 18, 48, 60, 78, 90, 120, 126, 150, 168,
9.  [0,  6, 30, 36, 48, 78, 90,  96, 126, 156, 168,
10. [0,  6, 30, 48, 78, 90, 96, 126, 138, 156, 168,

Выписал половинки паттернов и наверху подписал некоторые гэпы.

Как видим в трудном паттерне диаметром 324 три гэпа не меньше 24, причём два идут подряд.

А в трудном паттерне диаметром 336 два гэпа не меньше 42. В других паттернах не более одного гэпа-42.

Предполагаю, что с диаметром 336 первый паттерн так и останется единственным трудным. 21-336-6 хотя и не трудный, но трудноватый.

[Dmitriy40]

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

Точностью Вы пожертвовали ради скорости. Возможно ли ещё пожертвовать в случае необходимости?

Ну попробовать можно: для перемножения количества остатков задействовать AVX вместо FPU, но не думаю что это даст заметный выигрыш скорости, тормозит как бы не оно, а точность упадёт на 4 цифры (мантисса вместо 64 бит будет 53 бита). Да, точно не даст: для паттерна 21-420 и maxn=5 убрал вообще умножения и сложения в vC (т.е. он весь остался нулевым), время уменьшилось с 29с до 28с. Нафиг-нафиг.
Я наоборот знаю как повысить точность (правда не знаю насколько): сейчас основная потеря точности происходит при суммировании в vC - при сложении меньшего и сильно большего чисел с плавающей точкой происходит потеря точности (меньшее число перед сложением сдвигается вправо с потерей младших битов), можно это дело немного улучшить, но вместо одной команды сложения будет цепочка команд сложения длиной до 8 штук (точнее до $\lceil\log_2\pi(D/2)\rceil$, $D$ - диаметр), плюс обвязка. Но учитывая как мало влияют даже те же 6 умножений (выше), то возможно замедление будет и незаметным. Эту мысль держу в резерве, лень организовывать массив и цепочку сложений.

Пока всё пытаюсь как-нибудь по другому ускорить, но пока не получается, независимо от ухудшения точности (она и не ухудшается). Вот сейчас получил что для малых maxn ускорения нет вообще, даже скорее замедление, а для 21-420 с maxn=5 время уменьшается с 30с до 29с, а для maxn=6 с 282с до 269с. Как-то маловато, а кода нового ради этого прилично.

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

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

Потому что ненадёжен и когда снова сглючит неизвестно. Можно конечно проверять правильность первых 2-3 maxn, но нет гарантии что не сглючит на более заполненных паттернах (при больших maxn). И не понимаю как быстро убедиться что он не сглючил.
К тому же он лишь для симметричных паттернов, а текущий алгоритм может надёжно считать любые паттерны - что мне иногда надо.

[Dmitriy40]

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

точнее до $\lceil\log_2\pi(D/2)\rceil$, $D$ - диаметр

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

Сделал, точность реально возросла до 18-20 цифр (на 19-252 по C13, максимальная относительная ошибка меньше 3.1e-19 - на C1). Скорость при этом упала не сильно, для 19-252 по C8 с 40с до 43с, а по С10 с 267с до 288с, а по C13 с 1807с до 1926с, в общем порядка 8% замедление.
Выложил под новым именем hl-vc-time2: https://cloud.mail.ru/public/uYgX/GsDfyneGp, размер 71680 байтов, MD5=5a9c89d9191170d0441ffa4a67722db9, SHA256= ede3ed04f4d5a2ab0b63890c4f6b0a3ad4823789eed80dd2e597b32ac1405853.

[Yadryara]

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

Предполагаю, что с диаметром 336 первый паттерн так и останется единственным трудным.

Да, так и оказалось. Лишь один из 10. При этом все 10 паттернов 13-180 были примерно одинаковы по лёгкости, что меня и сподвигло на ту гипотезу.

Но дальше-то ещё интереснее получилось! Начал обсчёт паттернов 21-360 с конца. И вот он первый совершенно неожиданный результат. Покажу все обсчитанные. Чтобы удобнее было сравнить, привёл все паттерны кроме первых двух к C9.

Номер   Паттерн   Конст.   Прогноз по HL1     Норм.   Лёгкость
                     max             штук    формул     поиска

                              для 0 - 73#

1.     21-324-1       10            2.504     2.435      1.028
2.     21-324-2       10            1.017     6.575      0.155  трудный

3.     21-336-1        9            0.068     1.752      0.039  трудный
4.     21-336-2        9            0.300     2.561      0.117
5.     21-336-3        9            0.130     1.186      0.109
6.     21-336-4        9            0.154     1.423      0.109
7.     21-336-5        9            0.210     1.942      0.108
8.     21-336-6        9            0.296     3.139      0.094
9.     21-336-7        9            0.334     3.108      0.108
10.    21-336-8        9            0.475     4.297      0.110
11.    21-336-9        9            0.259     2.438      0.106
12.    21-336-10       9            0.274     2.708      0.101

13.    21-348-1        9            0.120     1.575      0.076

38.    21-360-25       9            3.914     3.447      1.136
_________________________________________
                                   10.056

Так что для проекта о25 прекрасная новость: паттерн 21-360-25 пока самый лёгкий из этих 14-ти!

И в интервале $0 - 71\#$ ожидается примерно $0.28 - 0.30$ таких кортежей.

[Yadryara]

Плохие новости. Для паттерна 21-360-24 обнаружил у Дмитрия ошибку для константы C4:

C4 slow      = 5050012910011857410.9045239814057472357;
C4 fast      = 5050012910011857410.9045239814057532437;
hl1-vc-time  = 4683457527247439734.400862,

Как обнаружил. При интегрировании получилось отрицательное значение для счёта до C9 включительно.

Для проверки запустил старые способы, медленный и быстрый, до 5-х констант. Паттерн хороший — уполовинивание сработало.

-- 05.05.2025, 01:15 --

Остальные константы совпадают. Как обычно, не во всех цифрах.

Как бы не пришлось всё пересчитывать.

-- 05.05.2025, 01:32 --

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

Выложил под новым именем hl-vc-time2:

Только hl1, а не hl. Проверил также эту версию:

C4 slow      = 5050012910011857410.9045239814057472357;
C4 fast      = 5050012910011857410.9045239814057532437;
hl1-vc-time  = 4683457527247439734.400862,
hl1-vc-time2 = 4683457527247439734.400862,

[Yadryara]

Ну да, ошибки есть и в других паттернах. Проверенные до C5 паттерны:

21-324-1    C3
21-324-2
21-336-1    C0

21-360-24   C4
21-360-25   C3

Все эти паттерны хорошо уполовиниваются. Так что все проверены дважды. Указана ошибочная константа. Как видим, она пока каждый раз только одна или ни одной.

В предположении, что больше ошибок нет, пересчитал до C9 по исправленным константам :

Номер   Паттерн   Конст.   Прогноз по HL1     Норм.   Лёгкость
                     max             штук    формул     поиска

                              для 0 - 73#

1.     21-324-1        9            0.334     2.435      0.137
2.     21-324-2        9            0.944     6.575      0.144

3.     21-336-1        9            0.195     1.752      0.111
4.     21-336-2        9            0.300     2.561      0.117
5.     21-336-3        9            0.130     1.186      0.109
6.     21-336-4        9            0.154     1.423      0.109
7.     21-336-5        9            0.210     1.942      0.108
8.     21-336-6        9            0.296     3.139      0.094
9.     21-336-7        9            0.334     3.108      0.108
10.    21-336-8        9            0.475     4.297      0.110
11.    21-336-9        9            0.259     2.438      0.106
12.    21-336-10       9            0.274     2.708      0.101

13.    21-348-1        9            0.120     1.575      0.076

...
37.    21-360-24       9            0.248     6.268      0.040
38.    21-360-25       9            0.151     3.447      0.044
_________________________________________
                                    4.425

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

[Yadryara]

То есть согласно этой гипотезе получается простая и скучная вещь:

Номер   Паттерн   Конст.   Лёгкость поиска
                     max       для 0 - 73#

1.       21-324        9              0.14
2.       21-336        9              0.11
3.       21-348        9              0.08
4.       21-360        9              0.04

Это с недостатком. Если обсчитать все до 10-х констант, лёгкость будет с небольшим избытком и поднимется на 1-2 сотых.

И не вижу никаких причин, по которым эта тенденция уменьшения лёгкости с ростом диаметра вдруг изменится. Она, скорее всего, затормозится.

Ну и для проекта о25 это плохая новость: они ищут 21-ки среди диаметров 360 и больше. А самые лёгкие диаметры почему-то игнорят.

[Dmitriy40]

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

Плохие новости. Для паттерна 21-360-24 обнаружил у Дмитрия ошибку для константы C4:

Спасибо! Подтверждаю, все выложенные версии ошибаются в C4:

>hl1-vc-time2.exe 5  0,30,36,54,84,96,114,120,126,150,180,210,234,240,246,264,276,306,324,330,360
[8088995791109319210e42, 1968612639555287800e44, 2328433359392419607e45, 1783459280152537787e46, 9223372036854775808e46, 4303668043520822125e47]
Time: 13.527s

Число 9223372036854775808 это ровно 2^63 - xто и есть признак ошибки, такого быть не может, где-то произошло переполнение и число не влезло в int64.
Подозрительно что только в C4.
При этом С0-С3,C5 совпадают с PARI просто отлично:

8088995791109319210258409898580974187538936571709358080000000,
8088995791109319210e42,

196861263955528779961057597334380049183792764279701501216000000,
1968612639555287800e44,

2328433359392419606814749728967417562027245150826968861554769920,
2328433359392419607e45,

17834592801525377867928880698653062154551590249764638618017194500,
1783459280152537787e46,

99452482677544156466518493798640145130727939938743677152190726144,
9223372036854775808e46,

430366804352082212494610305171671510368406079709727882976600594638,
4303668043520822125e47,

Разбираюсь.

[Dmitriy40]

Yadryara
Ошибка не в расчётной части, это радует. Неправильная конвертация числа с плавающей точкой в два целых (мантисса и порядок) для вывода (WinAPI их выводить не умеет, гадство). Ошибка возникает для значений мантиссы от 2^63=9223372036854775808 до 10^19, т.е. в среднем лишь в 8% случаев и как-то не попалась при тестах.

Поправил.
Все файлы в облаке обновлены, ссылки те же:
hl1-vc.exe: 72704 байта, MD5=6f2aebd4d11cddc8d3d5d3b6f575fd93, SHA256=7db60a8f61f0ff94050bac981b09ce07d328c69773012a6ee5a3550db2faff6d
hl1-vc-time.exe: 72704 байта, MD5=81eb60d32b3f59c6b9192429be7769c9, SHA256=d96eb8bfc8b1c57a37f445087699c4393c0a67b137f7433c438a8bda839cbe36
hl1-vc-time2.exe: 71680 байтов, MD5=5b167f29dc04227c6716851fa849c7fa, SHA256=6e3ffa849b3c67c4835f74b1c9b22448b5ab4d61b2950424a41b372f7c941975

[Yadryara]

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

Ошибка возникает для значений мантиссы от 2^63=9223372036854775808 до 10^19, т.е. в среднем лишь в 8% случаев и как-то не попалась при тестах.

А, то есть надо смотреть детально, может все паттерны пересчитывать и не придётся.

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

Может ещё быть ошибка при обсчёте 1-го паттерна...

И вот поленился я его перепроверить. Больше грешил на себя, а не на Дмитрия. Ан нет, никому верить нельзя — всё равно проверять надо.

В данном случае взаимопроверка ещё вчера могла сработать и не пришлось бы столько пересчитывать.

Я же ведь получил неожиданные данные. И уже надо было получше перепроверять. Нет же, только вопиющий результат заставил это сделать — отрицательное число там, где его не должно было быть. Вот она лень-матушка.

[Dmitriy40]

Имея посчитанные константы пересчитывать всё не столь обязательно: поделить их на CC[] чтобы получить то что выдала асм программа и если старшая цифра мантиссы окажется 9 (и порядок 18 и больше) - пересчитывать.