Hardy–Littlewood-1 in practice

[Yadryara]

Классическая формула HL1 для приблизительного количества кортежей на интервале такова:

$$C_0\int\limits_{2}^{x}\frac{dt}{\ln^{l}t}$$

Здесь $2$ — $x$ — интервал прогнозирования, $l$ — длина кортежа, $C_0$ — некая константа.

И для прогнозирования количества кортежей по сверхплотным паттернам вполне достаточно этой самой единственной константы.

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

Универсальная формула для чистых кортежей такова:

$$\int\limits_{2}^{x}\frac{dt}{\ln^{l}t}\left(C_0 - \frac{C_1}{\ln t} + \frac{C_2}{\ln^2t} - \frac{C_3}{\ln^3t}+ ...\right)$$

Как видим, формулы отличаются количеством констант и классическая формула является частным случаем универсальной при нулевых значениях остальных констант.

Как же считать эти самые константы? В нынешней теме как раз и предлагаю поговорить об этом. Попробую рассказать о существующей методике.

Также предлагаю обсудить вопрос, возможно ли применение HL1 для прогнозирования количества цепочек натуральных чисел с одинаковым количеством делителей, много обсуждавшихся в теме «Пентадекатлон мечты».

[vicvolf]

Yadryara
Я уже писал ранее, но Вы на это не обратили внимание. Если для расчетов используется первая гипотеза Харди-Литтлвуда, то справедлива теорема Галлахера - количество допустимых простых $k$-кортежей на интервале [$2,x$] - имеют распределение Пуассона с параметром:
$\lambda(x) \sim C(H)\int_2^x {\frac{dt}{\ln^k(t)}}$.
Для данного распределения мат. ожидание и дисперсия равны $\lambda(x)$.
Распределение Пуассона имеет длинный хвост справа, поэтому ошибка в определении мат. ожидания при прогнозе не так сказывается.

[Yadryara]

vicvolf, Спасибо за внимание к теме.

Видите, слова "in practice" (на практике) в заголовке? Практика — критерий истины.

Предскажите пожалуйста ожидаемое количество не сильно длинных рыхлых кортежей на не сильно большом интервале. Я тоже сделаю прогноз. Затем поищем реальные чистые кортежи. И сравним.

[Yadryara]

Читал наше прошлогоднее летнее обсуждение HL1. Оно началось с тех пор как vicvolf вновь обратил наше внимание на HL1. За что большое Спасибо.

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

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

[vicvolf]

Вот здесь в другой теме Вы писали:

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

То есть прогноз для этого интервала был: 9.527 кортежей 17-240-1 (центральных 17-к), а вовсе не 21 и не 20. Мы с Демисом недавно закончили проверку этого интервала и нашли в нём 11 центральных 17-к.

Таким образом, здесь относительная ошибка прогноза $(11-9,527)/11=13,39$% послу учета 13 коэффициентов.
Рассмотрим другой пример. Возьмем паттерн $(0,6)$. По формуле Х-Л на диапазоне до $10^6$ (по формуле с одним интегралом, т.е. по-вашему с коэффициентом $C_0$) количество кортежей равно $16496$. Реальное же число "чистых" кортежей на данном диапазоне $13549$.
Подсчитаем мат. ожидание расстояния между такими кортежами $10^6/13549=73,81$ и $10^6/16496=60,62$, т.е. относительная ошибка $17,87%$%. Не очень большая для прогноза с одним коэффициентом. Сравнительно небольшая относительная ошибка связана с большим хвостом распределения Пуассона.

[Dmitriy40]

vicvolf в сообщении #1700975 писал(а):

$10^6/13549=73,81$ и $10^6/16496=60,62$, т.е. относительная ошибка $17,87%$%.

$(16496-13549)/13549=16496/13549-1=21.75\%$.

vicvolf в сообщении #1700975 писал(а):

Возьмем паттерн $(0,6)$. По формуле Х-Л на диапазоне до $10^6$ (по формуле с одним интегралом, т.е. по-вашему с коэффициентом $C_0$) количество кортежей равно $16496$. Реальное же число "чистых" кортежей на данном диапазоне $13549$.

А оценка по двум константам, как и надо делать для чистых кортежей, ведь допустимы ещё и паттерны $(0,2,6)$ и $(0,4,6)$, даёт величину $13604$, что соответствует относительной ошибке $13604/13549-1=0.406\%$.

[Yadryara]

vicvolf в сообщении #1700975 писал(а):

Таким образом, здесь относительная ошибка прогноза $(11-9,527)/11=13,39$% послу учета 13 коэффициентов.

Не, ну такое крошечное количество кортежей не стоило смотреть. Это ещё повезло, что погрешность всего лишь 13%. Надо было хотя бы сотни смотреть. А лучше тысячи. Вот же у нас с Демисом было триумфальное подтверждение прогноза во время того же счёта:

По прогнозу было 1133 кортежа, а нашли 1147.

vicvolf в сообщении #1700975 писал(а):

Возьмем паттерн $(0,6)$. По формуле Х-Л на диапазоне до $10^6$ (по формуле с одним интегралом, т.е. по-вашему с коэффициентом $C_0$) количество кортежей равно $16496$.

Да всё так. $C_0 \approx 2.640647263$

vicvolf в сообщении #1700975 писал(а):

Реальное же число "чистых" кортежей на данном диапазоне $13549$.

Ну так и надо было всего лишь посчитать с учётом ещё и $C_1 \approx 5.716497191$

Получается прогноз 13604 кортежа. Погрешность лишь $0.4 %$.

Другие константы равны нулю, ибо паттерн [0, 6] можно загрязнить не более чем одним простым числом.

[vicvolf]

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

vicvolf в сообщении #1700975 писал(а):

Таким образом, здесь относительная ошибка прогноза $(11-9,527)/11=13,39$% послу учета 13 коэффициентов.

Не, ну такое крошечное количество кортежей не стоило смотреть. Это ещё повезло, что погрешность всего лишь 13%. Надо было хотя бы сотни смотреть. А лучше тысячи. .

Так где их взять? Часто мы прогнозируем появление первого кортежа.

[Yadryara]

vicvolf в сообщении #1701036 писал(а):

Так где их взять?

Например, в существующих Базах. Вот сравнение для сотен:

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

А вот и сравнение с Базами:

№     Паттерн    Прогноз   Факт
1.   13-168          262    252
2.   13-180-1        279    282
3.   13-180-2        415    447
4.   13-180-3        727    696
5.   13-180-4        568    544
6.   13-180-5        185    195
7.   13-180-6        594    622
8.   13-180-7        686    737
9.   13-180-8        533    519
10.  13-180-9        693    673
11.  13-180-10       503    523
12.  13-192-1        226    232
13.  13-192-2        195    214
14.  13-192-3        124    103    17 %
15.  13-192-4        158    145
16.  13-192-5        246    250
17.  13-192-6        276    285
18.  13-204-1        126    132
19.  13-204-2        173    171
20.  13-204-3        283    282
21.  13-204-4        208    180
_______________________________
                    7462   7484   0.3 %

HL1 по-прежнему прекрасно предсказывает.

Были и сравнения для тысяч. Поищу.

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

А если единичные кортежи прогнозировать, то нужно помнить, что расхождение с реальными данными может быть огромным — в разы.

[Yadryara]

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

Были и сравнения для тысяч. Поищу.

Нашёл в той же теме чуть ниже:

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

>findstr /E /C:": 0 30 48 54 78 84 90 114 120 138 168" n11 | find /c ":"
14300

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

Очередной триумф HL1. Полагал, что погрешность уложится в 1%, а она ещё в два раза меньше.

Подставляю:

  Паттерн   Прогноз    Факт

11-168-10     14376   14300
                      _____
13-192-5         67      58
                      = 247

Вот сравнение с фактами:

14376 / 14300 = 1.005

   67 / 58    = 1.155

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

[vicvolf]

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

А если единичные кортежи прогнозировать, то нужно помнить, что расхождение с реальными данными может быть огромным — в разы.

Я об этом и говорю. В этом случае не надо определять мат. ожидание с такой точностью и рассчитывать столько интегралов.

[Yadryara]

Сколько столько? Интеграл считается только один, на финальном этапе. Основное время занимает счёт констант.

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

А если единичные кортежи прогнозировать, то нужно помнить, что расхождение с реальными данными может быть огромным — в разы.

Важным моментом здесь является то, что это расхождение может быть в любую сторону, так что знание эталонного значения как раз имеет смысл.

Я ранее говорил о том, что когда-нибудь люди будут искать 21-ку. А почему я так говорил? Разве в проекте ODLK2025 21-ку уже несколько месяцев не ищут? Например, одно из приложений так и называется: "Calc21Tuples".

Да потому что таким темпом вполне можно искать двадцать тысяч лет и всё равно не найти. А откуда я взял такой временной отрезок? С потолка?