Re: У квадруплета есть центр может кому интересно.

[GogalNikolay]

Ende в сообщении #1738087 писал(а):

очему стартовое сообщение начинается с пункта 7? Где предыдущие 6? Эту тему тоже в карантин снести?

Так там формулы не все правильно, а этот кусок вроде без помех.
Квадруплеты простых чисел: структура коридора, модули типов и близнецовое решето

1. Определения

Квадруплет — четвёрка простых вида p,\ p+2,\ p+6,\ p+8. Первые примеры: 5, 7, 11, 13; 11, 13, 17, 19; 101, 103, 107, 109.

Чистое m — такое, что оба числа 6m-1 и 6m+1[/m Все квадруплеты, кроме [math]5, 7, 11, 13, удовлетворяют:

p \equiv 11 \pmod{30} — последние цифры всегда 1, 3, 7, 9;
центр квадруплета p+4 кратен 15;
слева — «стена»: p-2 делится на 3;
справа — ровно одна «дверь»: p+10 делится на 3, а p+12 — единственная свободная позиция для пятого простого;
за дверью — «стена»: p+14 делится на 5.
Отсюда невозможность шести подряд простых в такой конфигурации. Все утверждения доказываются покрытием вычетов по модулям 3 и 5.

3. Модуль типа

У каждого типа констелляции — свой модуль. Возьмём смещения d относительно центра c. Простое q назовём покрывающим, если запрещённые для центра классы -d \bmod q занимают все классы, кроме ровно одного.

Модуль типа — произведение покрывающих простых; центр сидит в единственном классе по модулю этого произведения.

Близнецы {c-1, c+1}: покрывающие 2, 3 — модуль 6, c = 6m (чистые m);
Квадруплет {c \pm 2, c \pm 4}: покрывающие 2, 3, 5 — модуль 30, c = 15(2k+1), то есть p \equiv 11 \pmod{30};
Секступлет {c \pm 2, c \pm 4, c \pm 8}: покрывающие 2, 3, 5, 7 — модуль 210, c = 105(2k+1), то есть p \equiv 97 \pmod{210};
Октет {0,2,6,8,12,18,20,26}, центр c = p+13: покрывающие 2, 3, 5, 7 — модуль 210, c \equiv 24 \pmod{210}.
Проверено счётом: все 294 квадруплета до 2 \cdot 10^6 — центры в классе 15 по модулю 30; секступлеты 97, 16057, 19417, 43777 — в классе 97 по модулю 210. Модули — примориалы: 6, 30, 210. «Стены» раздела 2 — это и есть покрывающие простые, а «дверь» — единственный свободный класс. Примориальность при этом не автоматика: она следствие формы паттерна. У октета симметрия нарушена, и уже 11 оставляет три свободных класса — лестница спотыкается на форме, а не на размере.

4. Лемма о произведении

Лемма. Пусть n_1, \dots, n_k — натуральные числа из интервала [p,\ p+C], P=n_1 n_2 \cdots n_k. Тогда все n_i простые тогда и только тогда, когда P не делится ни на одно простое q \le \lfloor \sqrt{p+C} \rfloor.

Доказательство — в две строки: лемма Евклида даёт q \mid P \iff q делит один из сомножителей, а любое составное n_i имеет простой делитель \le \sqrt{n_i} \le \sqrt{p+C}. Наблюдение школьного уровня, но оно превращает k проверок в одну.

5. Лестница корней

Так как \sqrt{p+C} - P^{1/(2k)} \le \frac{C}{\sqrt{p+C}+\sqrt{p}}, при достаточно больших p зазор меньше единицы, и граница \lfloor P^{1/(2k)} \rfloor + 1 накрывает \lfloor \sqrt{p+C} \rfloor целиком; малые случаи проверяются непосредственно.

Пара (p, p+2): k=2, P = p(p+2) = 36m^2-1, глубина P^{1/4}+1, зазор меньше единицы при всех p \ge 1;
Квадруплет: k=4, P = (36m^2-1)(36(m+1)^2-1), глубина P^{1/8}+1, зазор меньше единицы при p \ge 13; случаи p=5, 11 проверяются напрямую;
Шестёрка {p, p+4, p+6, p+10, p+12, p+16}: k=6, глубина P^{1/12}+1, зазор меньше единицы при p \ge 57; случай p=7 проверяется напрямую.
Пример: P = 101 \cdot 103 \cdot 107 \cdot 109 = 121,330,189. Нечётно; сумма цифр 28 — не делится на 3; не кончается на 0 или 5; на 7 даёт остаток 204; знакочередующаяся сумма цифр равна 2 — не делится на 11. Произведение чисто — все четыре числа простые. Одна цепочка делений вместо четырёх.

Проверено счётом: для квадруплетов до 2 \cdot 10^6 и секступлетов до 2 \cdot 10^5 — ноль расхождений с полной проверкой простоты. Первые секступлеты: 7, 97, 16057, 19417, 43777.

Где лестница останавливается. Три подряд чистых m существуют только при m = 1, 2, 3: паттерн {0, 2, 6, 8, 12, 14} накрывает все вычеты по модулю 5 и неадмиссивен. Поэтому форма ^3[/math] сертифицирует ровно один объект — 5, 7, 11, 13, 17, 19. Общая секступлет-констелляция продолжает лестницу, но уже не как произведение значений 36m^2-1.

6. Что даёт лестница — честно

Выигрыш по числу делений — ровно k-кратный. Но по битовой работе выигрыша нет: деление на малое q линейно по длине делимого, и k коротких делений стоят столько же, сколько одно длинное. Лестница — это лестница сертификатов, а не ускорений. Замер (кандидаты до 2 \cdot 10^6): 168 348 мод-операций по отдельности против 42 100 через произведение, время — 10 мс против 8. Реальное ускорение даёт не произведение, а отсечение кандидатов: p \equiv 11 \pmod{30} оставляет 6667 значений m из 33 334 — пятикратный срез ещё до всяких делений.

7. Оптика центра

У квадруплета есть центр: c = p+4. Все четыре числа — это c-4,\ c-2,\ c+2,\ c+4, и произведение сворачивается в квадраты:

P = (c^2-16)(c^2-4) = c^4 - 20c^2 + 64.

Отсюда мгновенный фильтр. Простое q бьёт квадруплет тогда и только тогда, когда q делит один из сомножителей, то есть когда

c^2 \equiv 4 \pmod{q} \quad \text{или} \quad c^2 \equiv 16 \pmod{q},

то есть когда c \equiv \pm 2 или \pm 4 по модулю q. Запрещённые значения c^2 — это квадраты смещений стен коридора. Для пары близнецов всё то же самое в предельном виде: P = c^2-1, блокер означает c^2 \equiv 1, запрещённые корни — \pm 1. Для секступлетов с центром c = p+8:

P = (c^2-4)(c^2-16)(c^2-64),

— c^2 должна избегать уже трёх квадратов. Лестница продолжается: k симметричных чисел означает, что c^2 избегает k/2 квадратов.

Пример: c = 105. Проверяем c^2 на запреты для всех простых q \le \sqrt{109}, то есть q = 2, 3, 5, 7: остатки нулевые, а ноль не равен \pm 2 и не равен \pm 4. Ни одного запрещённого квадрата — все четыре числа 101, 103, 107, 109 простые. Одна проверка остатка центра вместо четырёх вычитаний.

Заметьте: требование «центр кратен 15», которое в разделе 2 доказывалось покрытием вычетов, здесь вылезает само. Запреты по q = 3 (нельзя c^2 \equiv 1) и q = 5 (нельзя c^2 \equiv 1, 4) разрешают для квадруплета только c \equiv 0. Вычетная структура и квадратичная оптика — два языка об одном и том же.

Замеры (кандидаты p \equiv 11 \pmod{30} до 2 \cdot 10^6, 66 667 кандидатов):

четыре числа по отдельности: 1 902 848 мод-операций, 148 мс;
произведение P, корень 8-й степени: 475 783 мод-операций, 104 мс;
центр c = p+4, запрет c \equiv \pm 2, \pm 4: 475 712 мод-операций, 88 мс.
Все три метода дали ровно 294 квадруплета.

Почему центр — единственный метод с реальным ускорением, а не только сертификатом. Произведение давало 4-кратную экономию по числу делений, но съедало её битовой стоимостью: одно деление, но делимое вчетверо длиннее. Центр этой цены не платит: c \bmod q — деление маленького числа, а сравнение остатка с набором {\pm 2, \pm 4} — константная работа. Получается и сжатие произведения (в 4 раза меньше операций), и дешёвое делимое. Для больших p, когда числа перестают влезать в машинное слово, выигрыш центра только растёт: c \bmod q остаётся дешёвым, а деления длинных чисел дорожают линейно.

Бонус для теории. Доля выживших кандидатов читается прямо с запретов: на каждое простое q > 4 квадруплет теряет 4 запрещённых вычета из q, и произведение таких множителей по q — это в точности сингулярный ряд Харди — Литтлвуда для квадруплетов. Квадратичная оптика не только фильтрует, но и объясняет, откуда берётся константа в прогнозе, с которым наши данные сходились в пределах единиц процентов.

8. Мораль

Квадруплеты ищутся не особым фильтром, а как тень близнецового решета. Одно решето по парам (6m-1,\ 6m+1) даёт чистые m — и близнецы, и квадруплеты, и все «пятёрки» за дверью. Квадруплет — это просто соседние строки в списке чистых m: ноль дополнительных делений, бесплатный приплод. Работу делает вычетная структура: пять «стен» на каждые тридцать чисел, и путь p \equiv 11 \pmod{30} сквозь них.

Вопрос «кончаются ли чистые m» остаётся гипотезой Харди — Литтлвуда. Но теперь у него есть форма, в которой его удобно держать в руках: бесконечность квадруплетов равна бесконечности соседних строк в одном решете.

[Dmitriy40]

GogalNikolay
И снова формулы без $ ... Сколько раз повторять то ...

[Ende]

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

[GogalNikolay]

Ende в сообщении #1738092 писал(а):

Главное - доллар слева и доллар справа от строчной формулы, а если формула в отдельной строке - то два доллара слева и два доллара справа. Теги сами расставятся

поставил долл а выходит матх обязательно надо

[mathpath]

Их как собак нерезаных, и растут они как грибы

[GogalNikolay]

8. Стоп-лестница и цена запрета

Почему лестница примориалов обрывается. Продолжим лестницу модулей вверх. Чтобы простое q стало покрывающим для центра, запрещённые классы -d \bmod q должны занять все классы, кроме одного — то есть паттерн должен иметь не менее q-1 смещений. У паттерна из k симметричных чисел всего k смещений, значит для очередного покрывающего простого нужно q \le k+1. Лестница идёт ровно до тех пор, пока k+1 — простое:

близнецы: k=2, q=3 простое — модуль 6;
квадруплет: k=4, q=5 простое — модуль 30;
секступлет: k=6, q=7 простое — модуль 210;
октет: k=8, q=9 = 3^2 составное — ступени нет.
Общий закон: модуль k-элементного паттерна не превосходит примориал наибольшего простого, не превосходящего k+1; потолок достигается, когда для каждого простого q \le k+1 смещения занимают ровно q-1 классов. Значения k=8 и k=9 — дырки в лестнице: даже идеально симметричный октет восьмью смещениями физически нечем занять 10 классов по модулю 11. Лестница 6 \to 30 \to 210 \to 2310 соответствует k = 2, 4, 6, 10 — её ступени прыгают через составные k+1.

Показательно, что октет при том же модуле 210 всё же живёт: по 5 и 7 он покрыт идеально (4 из 5 и 6 из 7 классов), а по 11 запрещено только 8 классов из 11 — свободны три: c \equiv 3, 8, 10 \pmod{11}. Это уже не стена, а мягкое ограничение: покрывающий принцип нарушен, но сито продолжает работать с меньшим напором.

Цена запрета: сколько съедает каждое простое. Запрещённые корни c \equiv \pm 2, \pm 4 \pmod{q} различны, если только q не делит разность корней. Разности здесь — 2, 4, 6, 8, и склейки происходят только на малых q:

q=2: все корни склеиваются в один класс {0}, выживает 1/2;
q=3: 6 делится на 3, корни \pm 2 и \pm 4 сливаются в пары — запрещены 2 класса, выживает 1/3;
q \ge 5: все 4 корня различны, выживает /q[/math].
\prod_{q} \frac{q - w_q}{q} = \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{1}{5} \cdot \frac{3}{7} \cdot \frac{7}{11} \cdots

Правило на пальцах: после колеса p \equiv 11 \pmod{30} каждое следующее простое q съедает ровно 4/q того, что осталось. Семёрка съедает 57%, одиннадцатерка 36%, тринадцатерка 31%. Проверка стоит одно деление и одно сравнение: поделил c на q, сравнил остаток с {\pm2, \pm4} — жив или мёртв.

Сверка с фактом. Кандидатов p \equiv 11 \pmod{30} до 2 \cdot 10^6 — 66,667. Произведение \prod_{7 \le q \le 1414} (1 - 4/q) \approx 0{,}0044 даёт прогноз 296 выживших; факт — 294 квадруплета. Расхождение 0{,}8% — чистые краевые эффекты. Сингулярный ряд Харди — Литтлвуда для паттерна {0, 2, 6, 8}, полученный заменой конечного произведения бесконечным, даёт константу S = 4{,}1512 (совпадающую с известной константой простых квадруплетов) и прогноз 286 — 3% от факта.

Важно, что произведение \prod (1 - 4/q) здесь не эвристика, а точный подсчёт: китайская теорема об остатках гарантирует независимость запретов по разным q, поэтому перемножение долей — это буквально устройство сита. Сингулярный ряд — то, во что это произведение превращается в пределе. Два прогноза, 296 и 286, сходятся к факту с двух сторон: комбинаторной и аналитической.

[Dmitriy40]

GogalNikolay в сообщении #1738104 писал(а):

\prod_{7 \le q \le 1414} (1 - 4/q) \approx 0{,}0044

Так лучше:
$\prod\limits_{7 \le q \le 1414} \left (1 - \frac{4}{q} \right ) \approx 0{,}0044$

И когда наконец научитесь расставлять знаки доллара в формулах?

[Gagarin1968]

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

Так лучше:
$\prod\limits_{7 \le q \le 1414} \left (1 - \frac{4}{q} \right ) \approx 0{,}0044$

А так ещё лучше:

$$\prod\limits_{7 \leqslant q \leqslant 1414} \left (1 - \dfrac{4}{q} \right ) \approx 0{,}0044$$

[GogalNikolay]

9. Закономерности и интеграл

Счёт квадруплетов и интеграл четвёртого порядка. Гипотеза Харди — Литтлвуда даёт для паттерна {0, 2, 6, 8} асимптотику

Q(x) \sim S_4 \cdot \mathrm{Li}_4(x) = S_4 \int_2^x \frac{dt}{(\ln t)^4}

где S_4 = 4{,}1512 — сингулярный ряд из раздела 8. Проверка прямым счётом:

x Факт S_4,\mathrm{Li}_4(x) Расхождение
10^4 12 24,2 −50%
10^5 38 52,9 −28%
10^6 166 183,7 −10%
2 \cdot 10^6 295 285,9 +3%
10^7 899 862,9 +4%
10^8 4 768 4 734,6 +0,7%
На декадном интервале 10^7 \le x \le 10^8 интеграл предсказывает 3,871{,}7, факт 3,869 — расхождение 0{,}07%. Это самая сильная проверка во всём посте: интеграл, выведенный из запретов центра, работает с точностью до десятой доли процента.

Квадруплеты против простых корневого интервала. Сравним Q(x) с \pi(\sqrt{x}) — числом простых до корня:

x Q(x) \pi(\sqrt{x}) Отношение
10^4 12 25 0,48
10^5 38 65 0,58
10^6 166 168 0,99
10^7 899 446 2,02
10^8 4 768 1 229 3,88
Асимптотика читается из двух формул: Q(x) \sim S_4 x/\ln^4 x и \pi(\sqrt{x}) \sim 2\sqrt{x}/\ln x, поэтому

\frac{Q(x)}{\pi(\sqrt{x})} \sim \frac{S_4 \sqrt{x}}{2 \ln^3 x}

— отношение растёт монотонно и навсегда. Точка равенства при x = 10^6 — не особая отметка, просто кривая прошла через единицу: 166 против 168 — красивое совпадение, но не глубина.

Квадруплеты против простых на своём интервале. На одном и том же отрезке плотность квадруплетов относительно простых падает как S_4/\ln^3 x:

Интервал Квадруплетов Простых Отношение S_4/\ln^3 x
10^4 \le x \le 10^5 26 8 363 0,0031 0,0037
10^5 \le x \le 10^6 128 68 906 0,0019 0,0020
2 \cdot 10^6 \le x \le 10^7 604 515 646 0,0012 0,0012
10^7 \le x \le 10^8 3 869 5 096 875 0,0008 0,0008
К x = 10^8 квадруплетов примерно в 1300 раз меньше, чем простых, и разрыв растёт как \ln^3 x.

Отношение квадруплетов к квадруплетам. По декадам: Q(10x)/Q(x) равно 3,17 → 4,37 → 5,42 → 5,30. Асимптотика: 10,(1 - 4\ln 10/\ln x + \dots) — медленно ползёт к 10. Интегральная версия: \mathrm{Li}_4(10x)/\mathrm{Li}_4(x) = 5{,}49 против факта 5,30 на последней декаде.

Смысл одной фразой. Все три наблюдения — тени одного интеграла. Формула Q(x) \approx S_4 \mathrm{Li}_4(x) — асимптотика Харди — Литтлвуда для паттерна {0, 2, 6, 8}; пара «квадруплеты против простых до корня» — та же кривая, делённая на другую; интервальные отношения — плотность интеграла относительно плотности простых. Совпадение при 10^6 — просто место, где \sqrt{x} и \ln^3 x поменялись ролями.

Примечание про 294/295. Прямым счётом до 2 \cdot 10^6 — 295 квадруплетов, а фильтры разделов 5–7 дали 294, потому что колесо p \equiv 11 \pmod{30} отсеивает основателя (5, 7, 11, 13): его центр 9 не в классе 15. В раздел 3 достаточно добавить строку: «295 квадруплетов до 2 \cdot 10^6, из них 294 — в классе p \equiv 11 \pmod{30}; единственное исключение — (5, 7, 11, 13)».

[Dmitriy40]

А так ещё лучше:

$$\prod\limits_{q=7}^{1414} \left (1 - \dfrac{4}{q} \right ) \approx 0{,}0044$$

GogalNikolay
И кстати данное произведение равно $9\cdot10^{-11}$, а вовсе не $0{,}0044$:

? s=1.0; for(q=7,1414, s*=1-4/q); s
%1 = 9.0437639630177414037074283850598928869 E-11

Оно уже для верхнего порога 19 становится меньше 0.0044.
Выходит Вы вообще не проверяете свои (и свои ли?) выкладки ...

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

GogalNikolay в сообщении #1738108 писал(а):

\frac{Q(x)}{\pi(\sqrt{x})} \sim \frac{S_4 \sqrt{x}}{2 \ln^3 x}

Доллары в формулы!!

[GogalNikolay]

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

кстати данное произведение равно $9\cdot10^{-11}$, а вовсе не $0{,}0044$:

«Проверил: в вашем цикле for(q=7,1414,…) PARI перебирает все целые, а не простые — для простых нужен forprime(q=7,1414,…). Произведение по простым равно 0,004443746… (проверено точным рациональным счётом), прогноз 66667·0,0044437 = 296 против фактических 294 квадруплетов. Ваше 9,04×10⁻¹¹ — это произведение по всем целым, оно считается явно: ∏(n−4)/n от 7 до N = 360/((N−3)(N−2)(N−1)N), при N = 1414 даёт ровно ваши 9,0438×10⁻¹¹. Показательно, что и упомянутый вами "порог 19" работает только для целых — по простым произведение до 19 равно 0,114».

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

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

Оно уже для верхнего порога 19 становится меньше 0.0044.
Выходит Вы вообще не проверяете свои (и свои ли?) выкладки ...

[Dmitriy40]

GogalNikolay в сообщении #1738108 писал(а):

x Q(x) \pi(\sqrt{x}) Отношение
10^4 12 25 0,48
10^5 38 65 0,58
10^6 166 168 0,99
10^7 899 446 2,02
10^8 4 768 1 229 3,88

А это по нормальному оформляется таблицей:
\begin{tabular}{c|rrc} $x$ & $Q(x)$ & $\pi(\sqrt{x})$ & Отношение \\ \hline $10^4$ & $12$ & $25$ & $0{,}48$ \\ $10^5$ & $38$ & $65$ & $0{,}58$ \\ $10^6$ & $166$ & $168$ & $0{,}99$ \\ $10^7$ & $899$ & $446$ & $2{,}02$ \\ $10^8$ & $4768$ & $1229$ & $3{,}88$ \end{tabular}

[GogalNikolay]

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

А это по нормальному оформляется таблицей:

блин и так ставлю и ...
\begin{table}[h]
\centering
\begin{tabular}{c|rrc}
$x$ & $Q(x)$ & $\pi(\sqrt{x})$ & \text{Отношение} \\
\hline
$10^4$ & 12 & 25 & 0,48 \\
$10^5$ & 38 & 65 & 0,58 \\
$10^6$ & 166 & 168 & 0,99 \\
$10^7$ & 899 & 446 & 2,02 \\
$10^8$ & 4768 & 1229 & 3,88
\end{tabular}
\caption{Сравнение количества квадруплетов и простых чисел до $\sqrt{x}$}
\label{tab:quadruplets_vs_primes}
\end{table}
вставил ошибок не высвечивает а полная фигня

[Dmitriy40]

GogalNikolay в сообщении #1738110 писал(а):

Произведение по простым равно 0,004443746…

ОК, но в формуле про простые не указано ... Это можно сделать например так:

$$\prod\limits_{\substack {q=7 \\ q \in \mathbb{P}}}^{1414} \left (1 - \dfrac{4}{q} \right ) \approx 0{,}0044$$

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

GogalNikolay в сообщении #1738113 писал(а):

вставил ошибок не высвечивает а полная фигня

Пользуйтесь предпросмотром своих текстов и исправляйте до отсылки.
И смотрите как сделано у других, хоть бы у меня выше - нажмите кнопку Цитата и рассматривайте. Например Вы забыли тег math вокруг таблицы.

[GogalNikolay]

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

Например Вы забыли тег math вокруг таблицы.
И доллары в формулы!!

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