Кортежи из простых чисел

[Yadryara]

Теперь перечитываю другую кортежную тему, начиная с 3-й страницы. Начиная с вот этого поста я рассказываю о придуманном методе.

Кстати, не сразу понял и не всё ещё вспомнил по тому методу. Сейчас мне представляется, что я объяснял не лучшим образом, поэтому Дмитрий меня не сразу понял. Но понял. А другие люди, возможно, и до сих пор не понимают.

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

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

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

А не превратятся ли малопростые числа в простые? Да, если кортеж полностью состоит из чисел, которые меньше тысячи, превратятся. И это будет самый настоящий искомый кортеж из простых чисел.

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

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

А по HL1 — наоборот, количество более чистых посчитать легче. И, для обсуждаемых в последнее время паттернов CPAP-x-210, они уже частично посчитаны мной.

[Yadryara]

Считал и пересчитывал CPAP-2-30x. Интересная картинка:

Паттерн     Вариантов ненулевых            Ёлочный кэф
            загрязнений (констант)             (теор.)
            Теоретически   Практически         0 — 59#

[0,  30]               8             8            23.3
[0,  60]              15            15            44.5
[0,  90]              21            21            87.4
[0, 120]              26            27           168.1
[0, 150]              31*           33           329.4
[0, 180]              37*           38
[0, 210]              43*           42

* Посчитано одним способом, по остаткам. В других слуячаях посчитано ещё и по HL1, по программе Дмитрия на асме.

[wrest]

1. Как правильно называются интересующие всех коэффициенты к интегральным логарифмам?
Вот такое описание подходит?

Цитата:

Коэффициенты A[j] связаны с гипотезой Харди–Литтлвуда о простых кортежах, которая предсказывает асимптотику количества кортежей заданного паттерна H₀ в интервале [1, x] как C(H₀) · x / (ln x)^k, где k = |H₀|, а C(H₀) — константа, учитывающая локальные ограничения по простым модулям. Коэффициенты A[j] описывают вклад конфигураций, в которых j дополнительных позиций из X также оказываются простыми («загрязнения» кортежа), и позволяют уточнить эту константу для расширенных паттернов.

Вариант2 :

Цитата:

Коэффициенты A[j] входят в формулу Харди–Литтлвуда для количества простых кортежей заданного диаметра d в интервале [1, x]: оно асимптотически равно Σⱼ A[j] · ∫₂ˣ dt / (ln t)^{|H₀|+j}, где |H₀| — длина базового паттерна, а j — число дополнительных простых позиций («загрязнений») внутри того же диаметра. Каждый коэффициент A[j] равен сумме локальных констант по всем допустимым конфигурациям с j загрязнениями и определяет совокупный вклад кортежей длины |H₀|+j в эту сумму.

2. Имея "паттерн" например H₀ = [0,2,60], как можно быстро вычислить количество ненулевых коэффициентов A[j], равное 14 для этого случая, не вычисляя сами коэффициенты?

P.S. TeX не использован намеренно т.к. этот текст будет в хелпе программы командной строки.

[Yadryara]

wrest в сообщении #1727978 писал(а):

1. Как правильно называются интересующие всех коэффициенты к интегральным логарифмам?

Ну, не знаю, кого это всех. Константами интересовались в основном мы с Дмитрием. А vicvolf, который и привлёк моё внимание к HL1, довольно долгое время говорил не о нескольких, а об одной константе, которую к тому же безосновательно приравнял к 1-це, из-за чего его прогноз улетел по меньшей мере на 10 порядков.

wrest в сообщении #1727978 писал(а):

2. Имея "паттерн" например H₀ = [0,2,60], как можно быстро вычислить количество ненулевых коэффициентов A[j], равное 14 для этого случая, не вычисляя сами коэффициенты?

Если правильно понял вопрос, то об этом как раз рассказано начиная вот с этого поста.

Ну и не только. Позже соберусь с мыслями и отвечу конкретней.

[Yadryara]

wrest в сообщении #1727978 писал(а):

2. Имея "паттерн" например H₀ = [0,2,60], как можно быстро вычислить количество ненулевых коэффициентов A[j], равное 14 для этого случая, не вычисляя сами коэффициенты?

Да, правильно — для этого паттерна всего 14 констант.

Да, правильную ссылку дал. Вот чуть дальше в теме, на 11-й странице я определил количество констант для весьма сложного паттерна:

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

Вот фрагмент такой же таблицы для паттерна 19-252. Она в два раза шире, ибо продолжается до 49 ($valids=19, len = 49$).

Ну то есть длина кортежей по паттерну 19-252 в зависимости от загрязнений меняется от 19 до 49 включительно, то бишь имеется 31 константа. А все сами константы мы вычислили очень нескоро, больше чем через год, как раз когда Дмитрий написал программу на асме.

Но, как уже говорил, последние константы весьма мало волнуют, для обсчёта вполне хватило и 12 первых констант.

[wrest]

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

Вот чуть дальше в теме, на 11-й странице я определил количество констант для весьма сложного паттерна:

Я не понял. Вот есть паттерн [0,1600]
Как вычислить ненулевое количество констант быстро (меньше секунды), не вычисляя сами константы. Это возможно? Если нет, то и не надо, мне не принципиально.

-- добавлено через 2 минуты --

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

последние константы весьма мало волнуют,

Это я тоже понял. Но я спрашиваю "а где можно купить велосипед", а вы отвечаете "я когда-то покупал синий велосипед, в прошлом году, вот запись в блоге" вместо того чтобы ответить "велосипеды закончились, купить негде". Спасибо, конечно.

[Yadryara]

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

wrest в сообщении #1728005 писал(а):

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

Смотрите что я ответил сразу же, сейчас подчеркнул важное слово:

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

об этом как раз рассказано начиная вот с этого поста.

То есть для того чтобы понять как считать нужно именно что читать тему и вникать. Необязательно конечно именно с этого места.

wrest в сообщении #1728005 писал(а):

Я не понял. Вот есть паттерн [0,1600]
Как вычислить ненулевое количество констант быстро (меньше секунды), не вычисляя сами константы. Это возможно?

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

Я же ведь совсем недавно подсчитывал:

Паттерн     Количество        констант
                                      
            Теоретически   Практически
                                      
[0,  30]               8             8
[0,  60]              15            15
[0,  90]              21            21
[0, 120]              26            27
[0, 150]              31*           33
[0, 180]              37*           38
[0, 210]              43*           42

Вот для последних трёх паттернов не удаётся быстро подсчитать программой Дмитрия. Но мне удалось посчитать другим способом.

[wrest]

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

То есть для того чтобы понять как считать нужно именно что читать тему и вникать.

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

[Dmitriy40]

Количество констант можно попробовать подсчитать начиная с правого края, с максимального загрязнения, мы так посчитали 7 правых констант (других, не для HL1) для 19-252. Но в любом случае некий перебор, правда относительно быстрый и требующий не слишком много памяти, если ограничиться 3-5 правыми константами и считать лишь до стабилизации их общего количества, там по мере проверки простых с 3 и далее количество констант уменьшается и где-то стабилизируется. Для надёжности надо считать загрязнение простыми до D/6 для симметричных паттернов и до D/2 для несимметричных (D - диаметр паттерна), но ограничиваясь лишь несколькими самыми правыми константами это несложно. Для 19-252 стабилизация количества наступила на простом 19, при этом понадобилось всего 384 варианта паттернов, а для 23 (на котором и обнаружена стабилизация количества) всего 2304 вариантов - это про затраты памяти.
Для проверки лучше использовать паттерн [0,30,60], для которого тогда были посчитаны все те константы, 14шт, достигнуто уже на простом 7. Ну или [0,48,96] или [0,60,120] (для этого там счёт не закончен, но количество установлено).
Для того метода сами константы другие, но их количество ровно то же - количество возможных загрязнений.

[wrest]

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

[0, 60, 120, 180]
[0, 120, 240, 360]
[0, 180, 360, 540]

В общем, Монте-Карло пока плохо работает для больших диаметров (>1000)

Но для небольших (<500) вроде довольно сносно.

Первые 20 коэффициентов (так название им и не придумали)
Для [0, 60, 120, 180], оценка погрешности -- вроде должно быть не хуже чем вторая-третья справа значащая цифра мантиссы

[1.744607966726e+32, 3.38523e+33, 3.15748e+34, 1.88505e+35, 8.09251e+35, 2.66073e+36, 6.96809e+36, 1.49251e+37, 2.6642e+37, 4.0185e+37, 5.1745e+37, 5.7327e+37, 5.4961e+37, 4.5794e+37, 3.3261e+37, 2.1099e+37, 1.1701e+37, 5.6750e+36, 2.4066e+36, 8.9036e+35, 2.8645e+35]

Для [0, 60, 240, 360]

[1.28771941e+68, 4.643064e+69, 8.19860e+70, 9.44954e+71, 7.99487e+72, 5.29428e+73, 2.85730e+74, 1.29216e+75, 4.99644e+75, 1.67742e+76, 4.9483e+76, 1.2950e+77, 3.0303e+77, 6.3810e+77, 1.2157e+78, 2.1054e+78, 3.3270e+78, 4.8133e+78, 6.3935e+78, 7.8164e+78, 8.8138e+78]

Если уже есть точные значения, прошу проверить.
Ну а если нет -- пользуйтесь :)

[Yadryara]

wrest, погодите, вы же хотели посчитать для паттерна [0, 210, 420]. Не получилось?

А эти, с гэпами кратными 60, я привёл в качестве иллюстрации к методу двукратного ускорения. В любом случае Спасибо, чем больше статы, тем лучше.

[Dmitriy40]

>hl1-vc-time2.exe 8   0 60 120 180
[1744607966735346380e14, 3385172913347003603e15, 3157368611819966724e16, 1884950481137999236e17, 8091904806720382714e17, 2660478257909118007e18, 6967302828414788095e18, 1492315645520457588e19, 2663848364556069509e19]
>hl1-vc-time2.exe 6   0 60 240 360
[1287719410676632871e50, 4643070574054038554e51, 8198622286198573217e52, 9449588762803012682e53, 7994935692694964001e54, 5294336683958156006e55, 2857337800240892253e56]

[wrest]

[0, 180, 360, 540]

[3.772302263e+105, 1.929197e+107, 4.86258e+108, 8.05272e+109, 9.85559e+110, 9.50692e+111, 7.52773e+112, 5.03165e+113, 2.89770e+114, 1.46031e+115, 6.51930e+115, 2.60372e+116, 9.3787e+116, 3.0674e+117, 9.1618e+117, 2.5112e+118, 6.3434e+118, 1.4821e+119, 3.2136e+119, 6.4842e+119, 1.2206e+120]

-- добавлено через 46 минут --

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

погодите, вы же хотели посчитать для паттерна [0, 210, 420]. Не получилось?

Получилось :)

[1.50349479022e+80, 6.335757e+81, 1.31148e+83, 1.77753e+84, 1.77420e+85, 1.39068e+86, 8.91453e+86, 4.80533e+87, 2.22293e+88, 8.96221e+88, 3.18747e+89, 1.0098e+90, 2.8725e+90, 7.3854e+90, 1.7259e+91, 3.6832e+91, 7.2077e+91, 1.2979e+92, 2.1572e+92, 3.3181e+92, 4.7345e+92, 6.2794e+92, 7.7555e+92, 8.9337e+92, 9.6112e+92, 9.6689e+92, 9.1049e+92, 8.033e+92, 6.644e+92, 5.156e+92, 3.756e+92, 2.569e+92, 1.650e+92, 9.958e+91, 5.644e+91, 3.005e+91, 1.503e+91, 7.06e+90, 3.12e+90, 1.30e+90, 5.08e+89, 1.88e+89, 6.494e+88, 2.101e+88, 6.355e+87, 1.799e+87, 4.761e+86, 1.177e+86, 2.717e+85, 5.8422e+84, 1.1691e+84, 2.1732e+83, 3.7463e+82, 5.9775e+81, 8.8092e+80, 1.1963e+80, 1.4932e+79, 1.7082e+78, 1.7849e+77, 1.6931e+76, 1.3257e+75]

-- добавлено через 14 минут --

Dmitriy40
Да, вроде у меня точность заявленная (вторая справа значащая цифра мантиссы) получилась.

[Yadryara]

Благодарю. Как понял, на огромный завышенный порядок не надо обращать внимание.

[wrest]

Программа для расчёта безымянных коэффициентов
hl1_mc5
ссылка: https://disk.yandex.ru/d/N-g8FHL0dxuaBw
Программа на Си, нестандартных библиотек не требует (кроме openmp, не знаю насколько она нестандартная). Команда для компиляции приведена в комментарии.
Зависимости:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include <omp.h>

У меня компилируется и работает под aarch64 (андроид, bionic) в среде termux и под amd64 (glibc, нужен Линукс или Windows Subsystem for Linux)
Как под венду компилировать не знаю :)
Нормально считает кортежи длиной до 800, потом надо сильно увеличивать объём выборки.
Работает многопоточно с очень хорошим коэффициентом многопоточности, использует openmp.
Результат два вектора, вектор безымянных коэффициентов + вектор оценок среднеквадратичных отклонений в процентах (можно отключить).
Результат выводится в stdout, остальной текст в stderr
Текст хелпа:

hl1_mc5 — Sequential Importance Sampling для оценки коэффициентов A[j].

ОПИСАНИЕ:
  Коэффициенты A[j] входят в формулу Харди–Литтлвуда для количества
  простых кортежей заданного диаметра d в интервале [1, x]: оно
  асимптотически равно Σⱼ A[j] · ∫₂ˣ dt / (ln t)^{|H₀|+j}, где |H₀| —
  длина базового паттерна, а j — число дополнительных простых позиций
  («загрязнений») внутри того же диаметра. Каждый коэффициент A[j] равен
  сумме локальных констант по всем допустимым конфигурациям с j
  загрязнениями и определяет совокупный вклад кортежей длины |H₀|+j
  в эту сумму.

  Программа использует Sequential Importance Sampling с двумя прогонами:
  - Прогон 1 (alpha=0): Равномерное сэмплирование, точное для малых j
  - Прогон 2 (alpha=2.0): Importance Sampling, лучшее для больших j
  Результаты объединяются через обратные дисперсии.

ИСПОЛЬЗОВАНИЕ:
  ./hl1_mc5 [опции] MAXN h1 h2 ... hk

АРГУМЕНТЫ:
  MAXN          Максимальный индекс j для вывода (A[0]..A[MAXN]).
  h1 h2 ... hk  Элементы множества H₀ (обязательные позиции кортежа).
                Диаметр d = max(h_i). H₀ должно содержать 0 и d.

ОПЦИИ:
  --size N      Количество сэмплов (K, M, G, T). По умолчанию: 5M
  --full        Выводить числа целиком (%.0f)
  --plain       Вывод без квадратных скобок (для парсинга)
  --nostdev     Не печатать массив относительных погрешностей (СКО)
  --help        Показать эту справку

ПРИМЕРЫ:
  ./hl1_mc5 --size 10M 30 0 210 420     # d=420, 10M сэмплов
  ./hl1_mc5 --size 1M 999 0 210 420 630 840 1050 1260  # d=1260

В пост код к сожалению не влез (ограничениеие 20 тыс символов).

-- добавлено через 2 минуты --

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

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

Не понял о чём вы. Не обращайте :)