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

[Побережный Александр]

Праймориал - это произведение последовательных простых чисел, начиная с $2$.
Так для любого числа $N$ всегда можно указать число $i$, что это число будет находиться в пределах $\prod p_i \leqslant N < \prod p_{i+1}$.
Можно также утверждать, что число $N=a\prod p_i+b$, где $1 \leqslant a<p_{i+1}$, $ 0 \leqslant b < \prod p_i$, $a \in \mathbb{N}$.

Гипотеза.
Пусть $b$ - число взаимнопростое с праймориалом $\prod p_i$.
Зафиксируем $\prod p_i$ и $b$.
Если $a$ пробегает значения от $1$ до $p_{i+1}$, то всегда найдется простое число $P$ вида $P=a\prod p_i+b$

Пример.
Пусть праймориал равен $30=2\cdot3\cdot5$
Выбираем число $b$ взаимнопростое с праймориалом и меньше его, например $b=23$
$a$ пробегает значения от $1$ до $6$
Уже при $a=1$ получается простое число.
$1\cdot30+23=53$
Выбирая произвольный праймориал и фиксируя число $b$, всегда находим простое число, перебирая конечные значения числа $a$.
Во всяком случае, я нашел много простых чисел, включая число с 30000 десятичных знаков.

[vorvalm]

Побережный Александр в сообщении #955365 писал(а):

Выбирая произвольный праймориал и фиксируя число $b$, всегда находим простое число, перебирая конечные значения числа $a$.
Во всяком случае, я нашел много простых чисел, включая число с 30000 десятичных знаков.

Этот вопрос решается с помощью теоремы Дирихле о простых числах в арифметических прогрессиях.

[Sonic86]

vorvalm в сообщении #955449 писал(а):

Этот вопрос решается с помощью теоремы Дирихле о простых числах в арифметических прогрессиях.

Вроде как нет: теорема Дирихле говорит просто о бесконечности простых, а у ТС стоит ограничение $1\leqslant a\leqslant p_{i+1}$. Это что-то вроде теоремы Линника о первом простом числе в прогрессии (если не вру), только в частном случае и сильнее.
Кстати, сама формулировка не вызывает никакого желания это разбирать - исследовать надо в общем случае. Праймориалы и простые числа для ограничения на $a$ вообще не нужны. Прежде всего, надо хотя бы эмпирически проверить, дает ли специфика коэффициента прогрессии усиление ограничения на размер первого простого числа или нет. Скорее всего дает какой-нибудь коэффициент $O(1)$ и не более.

[vorvalm]

Sonic86 в сообщении #955457 писал(а):

теорема Дирихле говорит просто о бесконечности простых

Не только, но и на конечном интервале через функцию Эйлера.

[Sonic86]

vorvalm в сообщении #955528 писал(а):

Не только, но и на конечном интервале через функцию Эйлера.

ничего подобного. Пруф - в формулировке теоремы.

[vicvolf]

Побережный Александр в сообщении #955365 писал(а):

Гипотеза.
Пусть $b$ - число взаимнопростое с праймориалом $\prod p_i$.
Зафиксируем $\prod p_i$ и $b$.
Если $a$ пробегает значения от $1$ до $p_{i+1}$, то всегда найдется простое число $P$ вида $P=a\prod p_i+b$.

Из теоремы Дирихле вытекает следующее утверждение.

Максимум асимптотической плотности простых чисел в арифметической прогрессии $f(n)=kn+l$ при целых положительных $(k,l=1)$ и при минимальном значении k достигается при $k=2 \cdot 3...p_s$.

Это Ваша последовательность, но бесконечная, поэтому не удивительно, что плотность простых там наибольшая.

С другой стороны, как справедливо указал Sonic, существует теорема Линника, что для любой арифметической прогрессии $f(n)=kn+l$ с $(k,l=1)$, независимо от разложения $k$ (при $k$ больше 1), существует абсолютная константа С, что первое простое число в указанной арифметической прогрессии будет меньше $k$ в степени С.

В гипотезе утверждается, что когда $k=2 \cdot 3...p_s$, то номер первого простого числа в данной арифметической прогрессии не превосходит $p_{s+1}$.

Но числа вида $2 \cdot 3...p_s,2 \cdot 3...p_s+2,... 2 \cdot 3...p_s+p_s$ можно сразу исключить, так как они составные. Остаются только, как подозрительные на простые, числа $2 \cdot 3...p_s+1, 2 \cdot 3...p_s+p_{s+1}$. Число $2 \cdot 3...p_s+1$ может не быть простым. Значит остается доказать, что когда $2 \cdot 3...p_s+1$ не простое, то число $2 \cdot 3...p_s+p_{s+1}$ является простым.

[vicvolf]

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

Но числа вида $2 \cdot 3...p_s,2 \cdot 3...p_s+2,... 2 \cdot 3...p_s+p_s$ можно сразу исключить, так как они составные. Остаются только, как подозрительные на простые, числа $2 \cdot 3...p_s+1, 2 \cdot 3...p_s+p_{s+1}$. Число $2 \cdot 3...p_s+1$ может не быть простым. Значит остается доказать, что когда $2 \cdot 3...p_s+1$ не простое, то число $2 \cdot 3...p_s+p_{s+1}$ является простым.

Последнее справедливо, так как по теореме 1.4 Прахар "Распределение простых чисел" (стр. 19) не может быть цепочек составных чисел большей длины. На основании этой теоремы утверждение обобщается на случай, когда в качестве $k$ берется просто факториал.

[Sonic86]

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

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

Значит остается доказать, что когда $2 \cdot 3...p_s+1$ не простое, то число $2 \cdot 3...p_s+p_{s+1}$ является простым.

Последнее справедливо.

Это очевидно неверно при $s=9$.

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

Максимум асимптотической плотности простых чисел в арифметической прогрессии $f(n)=kn+l$ при целых положительных $(k,l=1)$ и при минимальном значении k достигается при $k=2 \cdot 3...p_s$.

Неверно из тривиальных соображений.

[vorvalm]

К.Прахар
По теореме Дирихле сравнение

$p\equiv l\pmod k,\;\;(k,l)=1$

имеет бесконечно много простых решений.

и далее Теорема 7.5

$\pi(x,k,l)\sim\frac {x}{\varphi(k)\ln x}$

[Someone]

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

Последнее справедливо, так как по теореме 1.4 Прахар "Распределение простых чисел" (стр. 19) не может быть цепочек составных чисел большей длины.

Числа вида $\prod\limits_{k=1}^np_k+b$ для $1\leqslant n\leqslant 100$ могут быть простыми
а) при $b=1$ — только для $n\in\{1,2,3,4,5,11,75\}$;
б) при $b=p_{n+1}$ — только для $n\in\{1,2,3,6,7,8,14,16,17,21,73\}$;
в) при $b=p_{n+2}$ — только для $n\in\{1,2,3,4,24,25,35,62,83\}$
(фактически простоту не проверял).

[vicvolf]

Спасибо Someone, но я ушел немного в сторону. Разговор в гипотезе шел о другой последовательности $P=a\prod p_i+b$, где $1 \leqslant a<p_{i+1}$, $ 0 \leqslant b < \prod p_i$, $a \in \mathbb{N}$.

Для этой последовательности выполняется утверждение.

Локальный максимум асимптотической плотности простых чисел в арифметической прогрессии $f(n)=kn+l$ при целых положительных $(k,l=1)$ на интервале от $p_1\cdot p_2\cdot ...\cdot p_s$ до $p_1\cdot p_2\cdot ...\cdot p_{s+1}-1$ достигается при $k=2 \cdot 3...p_s$.

Доказательство
Из теоремы Дирихле следует, что асимптотическая плотность простых чисел в последовательности арифметической прогрессии определяется по формуле: $P(f,2,x) \sim \frac {k} {\varphi(k)\ln(x)}.(1)$.

Пусть каноническое разложение k имеет вид:
$k=p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_s^{a_s},$
где $p_i$ - простое число с номером i.

Тогда:
$\frac {k} {\varphi(k)}=\frac {p_1^{a_1}\cdot p_2^{a_2}\cdot ...\cdot p_s^{a_s}} {p_1^{a_1-1}\cdot p_2^{a_2-1}\cdot ...\cdot p_s^{a_s-1}(p_1-1)(p_2-1)...(p_s-1)}=\frac {p_1\cdot p_2\cdot ...\cdot p_s}{(p_1-1)\cdot (p_2-1)\cdot ...\cdot (p_s-1)}>1,(2)$


На основании (2) асимптотическая плотность простых чисел в арифметической прогрессии $f(n)=kn+l$ при целых положительных (k,l)=1 не зависит от степеней $a_1,a_2,...a_s$ в каноническом разложении k.

Поэтому при возрастании k локальный максимум асимптотической плотности простых чисел на интервале от $p_1\cdot p_2\cdot ...\cdot p_s$ до $p_1\cdot p_2\cdot ...\cdot p_{s+1}-1$ достигается при $k=p_1\cdot p_2\cdot ...\cdot p_s$.

Например.
При $k=2$ плотность простых чисел равна $P(f,2,x) \sim \frac {2} {\ln(x)}$ (локальный максимум на интервале от 2 до 5).
При $k=3$ плотность простых чисел равна $P(f,2,x) \sim \frac {3} {2\ln(x)}$, т.е. меньше, чем в локальном максимуме.
При $k=4$ плотность простых чисел равна $P(f,2,x) \sim \frac {2} {\ln(x)}$ (повторяет значение локального максимума, но при большом значении k).
При $k=5$ плотность простых чисел равна $P(f,2,x) \sim \frac {5} {4\ln(x)}$, т.е меньше, чем в локальном максимуме.
При $k=6$ плотность простых чисел равна $P(f,2,x) \sim \frac {3} {\ln(x)}$ (локальный максимум на интервале от 6 до 29).
и.т.д.

[Someone]

Побережный Александр в сообщении #955365 писал(а):

Праймориал - это произведение последовательных простых чисел, начиная с $2$.
Так для любого числа $N$ всегда можно указать число $i$, что это число будет находиться в пределах $\prod p_i \leqslant N < \prod p_{i+1}$.
Можно также утверждать, что число $N=a\prod p_i+b$, где $1 \leqslant a<p_{i+1}$, $ 0 \leqslant b < \prod p_i$, $a \in \mathbb{N}$.

Гипотеза.
Пусть $b$ - число взаимнопростое с праймориалом $\prod p_i$.
Зафиксируем $\prod p_i$ и $b$.
Если $a$ пробегает значения от $1$ до $p_{i+1}$, то всегда найдется простое число $P$ вида $P=a\prod p_i+b$

У Вас здесь плохие формулировки.
Во-первых, написано $\prod p_i$ без указания пределов произведения, а затем употребляется обозначение $p_{i+1}$. Я это интерпретирую как $\prod\limits_{k=1}^ip_k$ и $p_{i+1}$.
Во-вторых, в одном месте написано "$1\leqslant a<p_{i+1}$", а в другом — "$a$ пробегает значения от $1$ до $p_{i+1}$", что при обычном словоупотреблении означает $1\leqslant a\leqslant p_{i+1}$.
И первое, и второе требует уточнения.

Сформулированная гипотеза, тем не менее, неверна (в том виде, как я её понял).
Если мы предполагаем, что $1\leqslant a<p_{i+1}$, то наименьшее значение $i$, для которого гипотеза неверна, равно $6$. В этом случае $\prod\limits_{k=1}^6p_k=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13=30030$, и для $b=10037$ (простое число) все числа $30030a+10037$ при $1\leqslant a<17$ составные. (При $a=17$ получаем простое число $30030\cdot 17+10037=520547$.)
Если же мы предполагаем, что $1\leqslant a\leqslant p_{i+1}$, то гипотеза неверна при $i=7$. В этом случае $\prod\limits_{k=1}^7p_k=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510$, и при $b$, равном каждому из чисел $126449$ ($=31\cdot 4079$), $199489$ (простое) или $304013$ (простое), все числа вида $510510a+b$, $1\leqslant a\leqslant 19$, являются составными. При $i=8$ таких "плохих" значений $b$ уже $156$:

(таблица)

117071, 151289, 172453, 237737, 439349, 491287, 599653, 654923,
677431, 688097, 698981, 709469, 723553, 864271, 943097, 1101391,
1271003, 1272413, 1313341, 1399367, 1683541, 1715359, 1721611,
1732463, 1748317, 1808447, 1823077, 1832671, 1999783, 2097679,
2258369, 2286787, 2326349, 2406347, 2465483, 2597671, 2681587,
2839061, 2899297, 2926109, 2961659, 2978863, 2980643, 3036343,
3086957, 3477217, 3596051, 3615011, 3620189, 3634837, 3707387,
3756671, 3778771, 3803101, 3820073, 3991531, 4112387, 4166167,
4350331, 4353199, 4360403, 4463983, 4527989, 4574113, 4621549,
5019767, 5040439, 5045021, 5060663, 5094091, 5102309, 5206007,
5294057, 5298859, 5398259, 5401351, 5489593, 5537579, 5556731,
5572373, 5693329, 5830499, 5848567, 6031283, 6057299, 6079043,
6088171, 6154921, 6176503, 6189541, 6247729, 6279107, 6487961,
6507661, 6618943, 6747833, 6836183, 6866527, 6967063, 7069633,
7092737, 7111787, 7121843, 7260467, 7324721, 7328327, 7345379,
7348273, 7391429, 7402537, 7403971, 7432991, 7451677, 7453597,
7509083, 7548241, 7550183, 7634483, 7700087, 7712431, 7798501,
7889867, 8025007, 8033057, 8047189, 8049773, 8098177, 8125619,
8209867, 8321167, 8342479, 8613887, 8630647, 8717383, 8718341,
8760887, 8826953, 8833807, 8861779, 8875849, 8941423, 8950573,
9036943, 9042161, 9046549, 9086821, 9178471, 9224269, 9248471,
9261779, 9290693, 9384659, 9597727, 9609521, 9676307, 9677323.

[Побережный Александр]

Уважаемый Someone, спасибо за такой труд! У меня были подозрения, что гипотеза не верна. Но я не смог найти контраргумент.
Вы совершенно правильно поняли условия гипотезы. Я имел в виду произведение $\prod\limits_{i=1}^kp_i$ и условие $1\leqslant a<p_{i+1}$.
Еще раз большое спасибо!