Числа близнецы

[gris]

Ой, то есть это $(7,11,13,17,19,23)$.
Тогда в первом миллионе их 5 штук, а во втором 3. А что тогда означает вероятность встретить секстет? Можно посмотреть количество секстетов в миллионах типа $i\cdot 10^6$:
in 1th mln there are 5 sextets
in 2th mln there are 3 sextets
in 3th mln there are 2 sextets
in 4th mln there are 2 sextets
in 5th mln there are 0 sextets
in 6th mln there are 0 sextets

Ну или посмотреть 1001 первых миллионов:
0 sextets in 742mlns of 1000
1 sextets in 214mlns of 1000
2 sextets in 36mlns of 1000
3 sextets in 6mlns of 1000
4 sextets in 2mlns of 1000
5 sextets in 1mlns of 1000
6 sextets in 0mlns of 1000
Я уже наверное надоел

[Euler-Maskerony]

gris в сообщении #1568780 писал(а):

А что тогда означает вероятность встретить секстет?

Сложно сказать. Я сделал предположение, что на отрезке $[c,c+2 \cdot 3 \cdot 5 \cdot ... \cdot p]$ вектора остатков чисел по простым делителям до $p$ распределены равномерно. Соответственно можно сделать приближение, что на отрезке длиной $p$ эти вектора также распределены равномерно. Мы не знаем как именно распределены вектора, поэтому приблизим их случайными. Суть получается в том, что мы ищем вероятность того, что при условии равномерности на отрезке длиной $p$ мы встретим близнецов. Эта теория может оказаться неверной если для всех чиcел $p$ на отрезке $[p,2p]$ все вектора не будут удовлетворять условию близнецовости, а дальше этого отрезка мы уже некомпетентны судить о близнецовости, т.к. вектора увеличиваются в размере.
Получается, что, чем ближе вероятность к единице, тем маловероятней событие, в котором на данном отрезке нет близнецов. При $p \rightarrow \infty$ стремиться как раз к единице, что означает, что либо близнецы там все таки есть, либо же простые числа ведут себя аномально.

[mihaild]

Euler-Maskerony в сообщении #1568769 писал(а):

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

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

Euler-Maskerony в сообщении #1568783 писал(а):

Я сделал предположение, что на отрезке $[c,c+2 \cdot 3 \cdot 5 \cdot ... \cdot p]$ вектора остатков чисел по простым делителям до $p$ распределены равномерно.

Это так, потому что каждый возможный вектор встречается ровно один раз.

Euler-Maskerony в сообщении #1568783 писал(а):

Соответственно можно сделать приближение, что на отрезке длиной $p$ эти вектора также распределены равномерно.

А вот это уже совершенно точно не так, потому что на отрезке такой длины по остатку от деления на $p$ однозначно восстанавливаются все остальные.

[Euler-Maskerony]

mihaild в сообщении #1568794 писал(а):

А вот это уже совершенно точно не так, потому что на отрезке такой длины по остатку от деления на $p$ однозначно восстанавливаются все остальные.

Это да, но под равномерностью я подразумеваю то, что вектора, соответствующие потенциально близнецам (а внутри отрезка $[p,2p]$ точно принадлежат близнецам), расположены на том отрезке не в "куче", а "размазаны" по всему отрезку. Я думаю, что это вполне рационально так предполагать. А из этого можно вывести следующее.

Если все "хорошие" вектора опять же "размазаны", то вероятность того, что какой-то конкретный "хороший" вектор не попадет на отрезок $[p,2p]$ равна: $p(A_i)=1-\frac{p}{2 \cdot 3 \cdot ... \cdot p}$.
Таком образом, вероятность того, что все вектора не попадут, равна:
$p(A)=(1-\frac{p}{2 \cdot 3 \cdot ... \cdot p})^{1 \cdot 1 \cdot 3 \cdot 5 \cdot ... \cdot (p-2)} =[2 \cdot 3 \cdot ... \cdot p \approx e^{\frac{p}{\ln{p}}\ln{p}} = e^{p}; 1 \cdot 1 \cdot 3 \cdot ... \cdot (p-2) \approx \frac{e^p}{\ln{(p)}^2}] = (1 - \frac{p}{e^p})^{\frac{e^p}{\ln{(p)}^2}}$

$\lim_{p\to\infty} p(A) = \lim_{p\to\infty} e^{-\frac{p}{\ln{(p)}^2}} = 0$

Следите за руками, но вроде правильно. Таким образом, если мы докажем, что вот эта вся "размазанность" выполняется, то получим, что хотя бы один близнец так точно попадет в отрезок $[p,2p]$

-- 04.11.2022, 08:28 --

Я думаю, что можно сделать какое-то статистическое исследование того, как ведут себя вот эти вектора, длиной $p$ при итерации. Нужно выявить их распределение и доказать, что оно равномерное (скорее всего нужен другой термин, но я не знаю какой). Если оно будет равномерным на каком-то участке, то это утверждение можно будет распространить по индукции на любые участки для любых $p$.

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

[Euler-Maskerony]

mihaild в сообщении #1568794 писал(а):

А вот это уже совершенно точно не так, потому что на отрезке такой длины по остатку от деления на $p$ однозначно восстанавливаются все остальные.

Под равномерностью я понимаю то, что какой бы подотрезок мы не взяли, все векторы на нем будут равномерно распределены по паралелепипеду размерности равной размеру вектора.
Если мы утверждаем, что равномерность имеет место, то соответствующие заключения, как выяснилось, сходятся с реальными данными. Осталось только на основе реальных данных показать, что равномерность есть.
Надо понять, как показать, что событие встретить "$0-$ простое" и событие встретить "$2-$ простое" независимы. Кажется, что это на кончиках пальцев находится, но я не знаю чего не хватает

-- 04.11.2022, 10:51 --

gris в сообщении #1568777 писал(а):

Секстет это $(p,p+6)$?

Я нашел, что таким наборам дано довольно смешное название
https://en.wikipedia.org/wiki/Sexy_prime

[Euler-Maskerony]

mihaild в сообщении #1568794 писал(а):

А вот это уже совершенно точно не так, потому что на отрезке такой длины по остатку от деления на $p$ однозначно восстанавливаются все остальные.

Предлагаю вот такое решение.
Пусть $n_p - $ номер простого числа $p$.
Назовем вектор хорошим, если у него нет остатков $0$ и $p_i-2$.
Обозначим простые числа, начиная с $p$ как $(p_0,p_1,p_2,...p_i,...)$
Предположим, что на отрезке $[p,2p]$ нет "хороших" векторов длины $n_p-1$. Тогда мы точно знаем, что "хорошим" векторам не соответствуют числа вида $kp_i$, где $k$ в своем разложении на простые множители имеет простые меньшие $p$, потому что иначе в векторе будет нолик. Вне этих значений "хороших" векторов такой длины быть тоже не может, т.к. иначе он будет близнецом. Получается, что "хорошие" вектора могут соответствовать числам, где $k$ состоит только из $p_i$. Минимальное из таких чисел - $p_0^2$, а максимальное надо подумать. Идея в том, что нужно показать, что таких чисел меньше, чем всего "хороших векторов".

-- 04.11.2022, 14:09 --

Я запрограмировал программу, которая считает долю таких чисел к числу "хороших векторов", и, кажется, увеличивается, поэтому надо что-то другое придумать.

[Euler-Maskerony]

mihaild в сообщении #1568794 писал(а):

А вот это уже совершенно точно не так, потому что на отрезке такой длины по остатку от деления на $p$ однозначно восстанавливаются все остальные.

Смотрите. Получается, что если "хорошие" вектора находятся в числах вида $kp_i$, то минимальное расстояние между ними равно $p$, но при этом легко посчитать, что среднее расстояние между "хорошими" векторами должно быть равно $\ln{(p)}^2$, что явно меньше. Значит "хорошие" вектора расположены плотнее, т.е. предположение неверно и близнецов бесконечно много.
Как вам?

[mihaild]

Если чуть продолжить (можно же не ограничиваться запретом двух остатков, а рассмотреть кортежи произвольной формы), то это получится асимптотика из первой гипотезы Харди-Литтлвуда. Но эта гипотеза не доказана, и вряд ли доказывается просто (а еще она противоречит второй гипотезе Харди-Литтлвуда, которая тоже выглядит очень правдоподобно).

Euler-Maskerony в сообщении #1568903 писал(а):

Получается, что если "хорошие" вектора находятся в числах вида $kp_i$, то минимальное расстояние между ними равно $p$,

Нет конечно, $k p_1$ и $q p_3$ могут отличаться очень слабо.

[Euler-Maskerony]

mihaild в сообщении #1568915 писал(а):

Нет конечно, $k p_1$ и $q p_3$ могут отличаться очень слабо.

Вы правы.
Но я придумал новый подход. Представим вектор числа $n$ в виде таблицы. Первая строка длины $p^2$ соответствует всем возможным остаткам от деления $n$ на p, смещенную влево так, чтобы текущий остаток от деления $n$ на $p$ стоял на первой позиции. Вторая строка соответствует остаткам от деления на простое число, идущее сразу до $p$, тоже длины $p^2$, т.е. мы ее расширили до такой длины, добавив справа ее же и обрезав до длины $p^2$, и также смещаем влево так, чтобы текущий остаток был на первой позиции. Так делаем для всех простых делителей. Вот картинка: https://ibb.co/wWx54CY (здесь длина строки $p$, но это просто пример)
Длина строки равна $p^2$ потому что легко показать, что если мы найдем вектор длины $n_p$ (номер $p$ в ряде простых чисел) на отрезке $[p,p^2]$, то он будет соответствовать близнецу.
Здесь вектор для $p=13$, какого-то произвольного числа. Текущие остатки находятся, соответственно, в первом столбце. Теперь, по построению, при прибавлении $1$ к этому числу, мы просто переключаемся на правый соседний столбец. Желтым я обозначил недопустимые остатки. Таким образом, нам надо найти столбец, где все клетки белые. Следует доказать, что в худщем случае при большом $p$ у нас будет такой столбец. Легко видеть, что первая, строка не закрывет $\frac{1}{2}$ всех столбцов. Вторая строка не закрывает $\frac{1}{3}$ от оставшихся. Третья строка не закрывает $\frac{3}{5}$. Понятно, что количество не закрытых столбцов на последнем шаге будет в среднем $\frac{p^2}{\ln{p}^2}$. В таком случае, при худшем сценарии у нас остается незакрытых не менее чем $\frac{p^2}{\ln{(p)}^2} - 2\frac{p}{\ln{p}}$, что очевидно возрастает. Значит даже в худшем случае у нас останется белые столбцы, а значит близнецов бесконечно много.
Как вам?

[mihaild]

Euler-Maskerony в сообщении #1568995 писал(а):

Понятно, что количество не закрытых столбцов на последнем шаге будет в среднем $\frac{p^2}{\ln{p}^2}$

Непонятно.

[Euler-Maskerony]

mihaild в сообщении #1569008 писал(а):

Непонятно.

Ну это в среднем. Я немного накосячил с оценкой худшего случая. Прочитайте вот это, пожалуйста. Сейчас напишу алгоритм, который его считает, а он, как я проверил, показывает возрастание количества белых столбиков с ростом $p$.
Пусть $(p_1=2,p_2=3,p_3=5,...,p_n)$ все рассматриваемые простые числа. Будем оценивать худший случай для каждой строки, начиная с нижней.
Для этого допустим, что мы на строке $i$. Строки под ней образуют подтаблицу, последовательность столбцов которой повторяется раз в $\#p_{p_{i-1}}$. Посчитаем количество таких промежутков:
$inter\_num_i = \lceil \frac{p_n^2}{\#p_{p_{i-1}}} \rceil$.
Далее посчитаем, сколько белых столбцов на каждом промежутке (худший случай). Мы знаем общее количество белых столбцов на $i-1$ шаге. Оно равно $rem_{i-1}$.
Давайте будем считать так. Для шагов $(1,2,3)$ не будем округлять полученное значение, т.к. там слишком много промежутков, а соответственно на каждом мало столбцов. Таким образом целевое значение равно:
$rem\_per\_inter_i = \frac{rem_{i-1}}{inter\_num_i}$ для $i \in \{1,2,3\}$ и $rem\_per\_inter_i = \lfloor \frac{rem_{i-1}}{inter\_num_i} \rfloor$ для остальных. Это не повлияет на оценку.
Далее заметим, что мы можем "закрыть" максимум столбцов на $i-$ом шаге, если на первом и втором промежутке закроем по два столбца (это самый худший случай). Если мы на первом и втором промежутке закрываем по два столбца, то следующие два столбца мы можем "закрыть" только через $p_i-2$ интервала (ну понятно, потому что последовательность столбцов в каждом интервале одинкова, а меняется только значения $i-$ой строки, а они повторяются раз в $p$ интервалов). Поэтому легко составляем формулу для оценки оставшихся белых столбцов на $i-$ом шаге:
$rem_i = \lfloor\max{(0,rem\_per\_inter_i-2)} \cdot inter\_num_i \cdot \frac{2}{p_i}\rfloor + \lfloor rem\_per\_iter_i \cdot inter\_num_i \cdot \frac{\max{(1,p_i-2)}}{p_i}\rfloor$
На самом первом шаге $rem_{i-1} = p_n^2$ = inter\_num_i$
Вот код: https://pastebin.com/4sfXdDBX
Если запустить, то с ростом $p_n$ растет и количество белых столбцов.
У меня получилась вот такая оценка этой функции: https://www.desmos.com/calculator/0kn1nikdkf .Я здесь начал сразу с шага, где $p_i=11$, чтобы избавиться от проверок на отрицательность, а также вместо пола и потолка вычитал и прибавлял единицу соответственно. Здесь $0.7 - $ сумма ряда обратных праймориалов, а $\frac{15}{210}$ - примерная доля белых столбцов для $p_i=7$. Вроде получилось очень даже ничего.
Как вам?

[Euler-Maskerony]

Это снова ошибка. Простите.

[Euler-Maskerony]

mihaild в сообщении #1569008 писал(а):

Непонятно.

А если вот так. На первых двух итерациях мы закрасим $p^2\frac{1}{6}$(точное значение). На следующей итерации мы закрасим $\frac{2}{5}$ от $p^2$ (верхняя граница). На следующей итерации для $p_i=7$ мы закрасим $p^2\frac{2}{7}$, но это слишком много и мы не сможем закрасить столько и вот почему. Рассмотрим более простой случай, когда у нас один недопустимый остаток. В этом случае этот остаток будет красить каждый раз новый стобец, т.е. отличный от предыдущих. Поэтому рассмотрим самый худший случай, когда остаток красит сначала красит белые столбцы, а потом уже закрашенные. Белых столбцов на предыдущих итерациях у нас $1 \cdot 1 \cdot 3=3$(тут уже для двух остатков). Значит мы красим $2p^2\frac{1}{7}\frac{3}{2 \cdot 3 \cdot 5}$. На следующей итерации используем такую же логику и закрашиваем $2p^2\frac{1}{11}\frac{15}{210}$.
Получается сумма: $s = 2p^2 \cdot (\frac{1 \cdot 3}{7 \cdot 30} + \frac{1 \cdot 15}{11 \cdot 210} + \frac{1 \cdot 135}{13 \cdot 2310} ...) < \frac{1}{6}p^2$
Также помимо этого мы вычитаем $1$ на каждой итерации (т.к. на каждой итерации закрашиваем минимум один столбец). Т.е. итоговое число белых столбцов оценивается так:
$p^2\frac{1}{6} - s - \frac{p}{\ln{p}}$
$s < p^2 \cdot \sum_{i=1}^{p} \frac{1}{i\ln{i}^2} = c $ сходится и скорее всего к числу $< \frac{1}{6}$
Так правильно?

[Euler-Maskerony]

Если мы распишем $s$ с самого начала, то получим:
$s = 2p^2 \cdot (\frac{1 \cdot 1}{2 \cdot 1} + \frac{1 \cdot 1}{3 \cdot 2}+\frac{1 \cdot 1}{5 \cdot 6} + \frac{1 \cdot 3}{7 \cdot 30} ...) \rightarrow p^2$, что по сути нам и нужно.
Здорово?

[mihaild]

Точно не здорово, потому что вы доказали, что доля близнецов среди всех чисел константная:)

Euler-Maskerony в сообщении #1569427 писал(а):

Белых столбцов на предыдущих итерациях у нас $1 \cdot 1 \cdot 3=3$(

Вот это непонятно что значит и откуда взялось. До того всё время белых столбцов было пропорционально $p^2$, а тут вдруг константа.