Арифметические пргрессии из простых чисел

[VAL]

Про такое усиление теоремы Грина-Тао я не слышал. А вы?

Верно ли, что для любого простого $p$ существует арифметическая прогрессия с первым членом $p$ (и положительной разностью), у которой первые $p$ членов - простые числа?

[Booker48]

VAL в сообщении #1442553 писал(а):

Верно ли, что для любого простого $p$

Ну, для любого точно неверно. $2$ и $3$, очевидно, выпадают.

[mihaild]

Booker48 в сообщении #1442558 писал(а):

$2$ и $3$, очевидно, выпадают.

Почему? $2,3,\ldots$ - арифметическая прогрессия, $3, 5, 7, \ldots$ - тоже.

[Booker48]

Сорри, первый член почему-то не посчитал...

[kotenok gav]

А для $p=7$ такая последовательность существует?

[mihaild]

kotenok gav в сообщении #1442563 писал(а):

А для $p=7$ такая последовательность существует?

Да, минимальная разность - $150$.
(очевидно что разность должна делиться на $(p-1)\#$ и не должна делиться на $p$, так что перебор тут был не очень большой)

[VAL]

Для 11 наименьшая разность - 322593616800.
Для 13 пока не нашел. Но полагаю - это реально. А дальше - задача для проектов распределенных вычислений.

[kotenok gav]

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

разность должна делиться на $(p-1)\#$

Почему?

[mihaild]

kotenok gav в сообщении #1442603 писал(а):

Почему?

Потому что если шаг $s$ не делится на простое число $x < p$, то хотя бы одно из чисел $p, p + s, p+2s, \ldots, p + (x - 1)s$ делится на $x$ (т.к. все остатки от деления на $x$ у этих $x$ чисел разные, значит один из них равен $0$).

[Dmitriy40]

VAL в сообщении #1442567 писал(а):

Для 11 наименьшая разность - 322593616800.

простите, а как же это?

? forprime(p=3,11,pp=vecprod(primes([1,p-1]));forstep(s=pp,10^13,pp,v=vector(p,i,p+i*s-s);if(vecsum(isprime(v))==p,printf("p=%u, s=%u\n",p,s);break)))
p=3, s=2
p=5, s=6
p=7, s=150
p=11, s=1536160080
? vector(11,i,11+(i-1)*1536160080)
%1 = [11, 1536160091, 3072320171, 4608480251, 6144640331, 7680800411, 9216960491, 10753120571, 12289280651, 13825440731, 15361600811]
? isprime(%1)
%2 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

-- 02.03.2020, 18:48 --

Остальные можно посмотреть здесь: A088430.

[VAL]

Я случайно дважды на коэффициент 210 умножил. Мое $32259361680$ - это $1536160080\cdot 210$ Поэтому и не нашел A088430 в OEIS.
Хотя и удивился, что этой штуки там нет. Оказывается, есть!

PS: Кстати, автор A088430 у меня во френдах на FB.

[mathpath]

VAL в сообщении #1442624 писал(а):

PS: Кстати, автор A088430 у меня во френдах на FB.

Нифига себе:
Zak Seidov, родился в Баку в 1939 году !

У него еще есть:
https://oeis.org/search?q=author%3ASeid ... &go=Search

[Dmitriy40]

Поиск по OEIS сочетания "2,6,150" даёт всего два результата, один из которых не подходит даже по описанию (для надёжности можно конечно и числа проверить благо они небольшие), а второй правильный.
С числовыми последовательностями вечно так, только придумаешь что-то красивое, как оказывается оно уже есть в OEIS, надо лишь не забывать при получении хотя бы нескольких элементов их там поискать (тоже вечно забываю).

[VAL]

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

С числовыми последовательностями вечно так, только придумаешь что-то красивое, как оказывается оно уже есть в OEIS, надо лишь не забывать при получении хотя бы нескольких элементов их там поискать (тоже вечно забываю)

В том-то и дело, что я не забыл. Но искал вместе с неправильным значением a(5). И почему-то не нашел

[vorvalm]

Практические исследования АППЧ (арифметические прогрессии простых чисел)
показывают, что длинные цепочки простых чисел образуются при разности прогрессий,
равной праймориалу или числу, кратному праймориалу. Общий член прогрессии равен

$p_n= p_1+d\cdot (n-1)$

Здесь $d=p_r\#$ или $d = K\cdot p_r\#,\;\;(K,p_{r+1})=1$.

Если принять первый член прогрессии $p_1=p_{r+1}$, то получим

$p_n=p_{r+1}+p_r\#\cdot (n-1)$

Очевидно, что от $n=1$ до $n=p_{r+1}$ все члены прогрессии будут
взаимно простые числа и представляют полную систему вычетов по модулю $m=p_{r+1}$
и только при $n=p_{r+1}+1$ получим вычет, кратный первому члену прогрессии.
Вычеты прогрессии между $p_1=p_{r+1}$ и $p_n=p_{r+1}\cdot (p_r\#+1)$ попарно не сравнимые
по модулю $m=p_{r+1}$ и взаимно просты с этим модулем, т.е. представляют собой
приведенную систему вычетов по модулю $m= p_{r+1}$. Число их равно $p_{r+1}-1$,
но т.к. первый член у нас $p_{r+1}$, то вся цепочка будет состоять из $p_{r+1}$ вычетов.
Пример. $p_n=5+6 (n-1)$ имеем $5, 11, 17, 23, 29.$
При разности прогрессии $d= K\cdot p_r\# $ ничего принципиально не изменится.
Единственное требование к коэффициенту $ K$. Он не должен быть кратным числу $p_{r+1}$.
Пример.$ p_n=7+5\cdot 30(n-1)$ имеем $7, 157, 307, 457, 607, 757, 907.$
Итак, максимальное число вычетов данных прогрессий равно начальному простому числу.
Дело в том, что остальные вычеты таких прогрессий могут быть не простыми числами, но
обязательно взаимно простыми. Если хотя бы один вычет не является простым, то такие
прогрессии будем считать неполными.
Кстати, почти все известные достаточно длинные цепочки простых чисел являются неполными.

Теперь рассмотрим случай, когда первый член прогрессии не равен $p_{r+1}$.
Очевидно, что он должен быть больше $p_{r+1}$, т.е. $p_t > p_{r+1},$ тогда

$p_n= p_t+p_r\#(n-1)$

Введем новое понятие нулевого вычета

$q_0=p_t-p_r\#(n-1)=k\cdot p_{r+1}$

Этот вычет может быть и отрицательным, но обязательно кратным $p_{r+1}$. Получим цепочку

$p_n=k\cdot p_{r+1}+p_r\#(n-1)$

Здесь число взаимно простых вычетов по модулю $m=p_{r+1}$ равно $p_{r+1}-1$,
следовательно, число вычетов АППЧ не может быть больше простого числа $p_{r+1}$
при разности прогрессии $d=p_r\#$.
Например, возьмем $p_t=11, \;p_r\#=30.$ Получим $q_0=11-30-30=-49$.
Составим прогрессию c начальным вычетом $q_0=-49$.

$p_n=-49 + 30 n = (-19, 11,41, 71, 101, 131,) (161)$

Как видим, число вычетов прогрессии взаимно простых с $p_r=7$ равно $p_r-1=6$,

В выборе разности АППЧ мы не ограничены и можем получить бесконечное число АППЧ
любого конечного размера.
Несколько примеров полных цепочек простых чисел.
(35), 41, 47, 53, 59, (65),\;\;d=3#=6.
(77), 107, 137, 167, 197, 227, 257, (287),\;\;d=5#=30.
-11, 199. 409, 613, 829, 1039, 1243, 1459, 1669, 1879, 2089, (2299),\;\;d=7#=210.
(96577=13* 7429,) 110437, 124297, 138157, . . . . 235177, 249037, 262897, (276757=13* 21289).\;\;d=6* 11#=13860.