Прогрессии из простых чисел

[genk]

Здравствуйте.Известно,что существуют арифметические прогрессии сколь угодно большой длины,состоящие из простых чисел(теорема Тао).Мне захотелось проверить ресурсы домашнего компа(естественно,для небольших длин) и вот что получилось в Maple.
Код: with(combinat):p:={seq(prevprime(i),i=4..100)}:s:=choose(p,5):for i to nops(s) do if s[i][2]=0.5(s[i][1]+s[i][3])and s[i][3]=0.5(s[i][2]+s[i][4])and s[i][4]=0.5(s[i][3]+s[i][5]) then print(s[i]) fi od;
{5,11,17,23,29}

{5,17,29,41,53}

Как видно,в пределах первой сотни натуральных чисел нашлись 2 прогрессии длины 5 с указанным свойством.Прогрессий длины 6 в этих пределах не обнаружено.Я решил расширить диапазон чисел,но сразу столкнулся с ограниченными ресурсами компа-он стал писать,что не хватает памяти даже в пределах первых 150 натуральных чисел.Дело в создании массива из сочетаний по 6 элементов из данного множества простых чисел.Может быть,возможен другой алгоритм в обход предварительного создания множества сочетаний?

[gris]

Ждал и ждал и надеялся, что кто-то напишет вечную истину. Наконец решил проверить, так ли понял?
Вот тупой перебор за минуту для прогрессии из 6 членов.
forprime( p=3,1000, for( d=4,200,
if(isprime(p+2*d)&&isprime(p+4*d)&&isprime(p+6*d)
&&isprime(p+8*d)&&isprime(p+10*d),
print(p," ",p+2*d," ",p+4*d," ",p+6*d," ",p+8*d," ",p+10*d))))
7 37 67 97 127 157
7 157 307 457 607 757
11 71 131 191 251 311
13 103 193 283 373 463
13 223 433 643 853 1063
23 263 503 743 983 1223
........
829 1039 1249 1459 1669 1879
881 1091 1301 1511 1721 1931
Что на самом деле нужно?

[genk]

Какая версия Maple?Что за функция forprime?

[gris]

Это PARI/GP ставшие последнее время популярными на форуме. Очень советую, особенно для точных действий с большими целыми числами. Про кленовый сироп я как-то и забыл:( Наверное, там есть какие-то средства борьбы с простыми числами

[genk]

Да,спасибо, PARI явно превосходит кленовый сироп и Wolfram в мире простых чисел.Практически мгновенно выдал прогрессии и из 8 членов и далее.Интересно,каков предел длины прогрессии на домашнем компе,но этим лень заниматься из-за муторного вывода с print.Осталось последнее:что означает Ваша загадочная фраза"ждал,ждал и надеялся".

[gris]

Ну я только изучаю PARI и консультировать не возьмусь. Поэтому всегда выжидаю пару часов, пока не придут в тему спецы. А они шли и шли и пели вечную память. Извините, дурная привычка не к месту приводить цитаты.
Так по теме. И попробовал сейчас такой вариант:
{for(L=3,12,
forprime(p=3,8000,
for(d=1,5000,ind=1;
for( i=1,L-1, if(!isprime(p+i*d),ind=0;break) );
if(ind==1, print(L," ",p," ",2*d);break(2));
)))}
Выводится длина прогрессии и наименьший (по-моему) пример (длина, начало, разность) для разности от 2 до 10000:
3 3 4
4 5 12
5 5 12
6 7 60
7 7 300
8 103 9240
9 199 420
10 199 420
Для длины 11 началось торможение. Попробую увеличить диапазоны. Самому интересно
Кстати, результаты можно выводить в текстовый файл.
++ Вот нашлось. Далеко, однако. Но в PARI бывают и по огромному количеству знаков числа. Правда, с ними тоска зелёная
11 4943 120120

[gris]

Ещё чуточку. Маленькая неточность. Там выведена двойная разность, которая и предполагалась к использованию. Вот так всегда.

[Dmitriy40]

https://en.wikipedia.org/wiki/Primes_in ... rogression

gris
Нет необходимости перебирать все возможные разности, достаточно с шагом 6: forstep(d=6,100000,6, ...

А для длинных цепочек (кажется уже начиная от длины 6) и кратно ещё большему числу, не 6. Минимальные разности указаны здесь - A033188

Много разных рекордов и вообще результатов: http://primerecords.dk/aprecords.htm

Ну и Вы бы это, пользовались тегом code, а ...

[wrest]

genk в сообщении #1573530 писал(а):

.Интересно,каков предел длины прогрессии на домашнем компе,

Оценка сверху 27. Т.е. прогрессию длиной 28 членов найдёте вряд ли. Ну а длиной 27 при помощи компьютера найти легко: эта последовательноть есть в википедии.

P.S. А, вот и Dmitriy40 туда же, в википедию :)

[gris]

Оно да, там всё есть, но хочется и самому попробовать. Кстати, важна именно разность и её можно считать и до ста миллиардов. Для любой простяшки можно стартовать прогрессию длины не больше её самой. Но разности могут быть огромны.
$3\;-\;5\;-\;7$

$3\;-\; 6666666666683\;-\; 13333333333363$

А тэгом [tt] пользуется wrest. Я подражаю, хотя отступов не хватает

[Dmitriy40]

gris
Тег tt удобен когда надо часть строки или одну (ну пару) строку привести. Если же строк несколько, то лучше таки code.

Здесь от ind можно избавиться:

for(...,
  ind=1;
  for(i=1,L-1, if(!isprime(p+i*d),ind=0;break);
  if(ind>0, print(...));
);

вот таким образом:

for(...,
  for(i=1,L-1, if(!isprime(p+i*d),next(2));
  print(...);
);

Т.е. print() пропускается и происходит переход к следующей итерации внешнего цикла.

-- 12.12.2022, 17:03 --

Кстати минимальная разность для цепочки длины $n$ равна $n\#$ (праймориал, произведение простых до $n$ включительно) если только $n$ не простое и не подходит одна единственная цепочка $n+k\times n\#/n$. Иначе не хватит возможных остатков.

-- 12.12.2022, 17:32 --

Правда таких цепочек или исключительно мало, или вообще больше нет после $n=5$ (по крайней мере до $n<10^4$).

[wrest]

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

А тэгом [tt] пользуется wrest. Я подражаю, хотя отступов не хватает

Я пробовал как-то тег code для PARI,

(но есть нюансы)

и мне категорически не понравилсь. Я когда публикую тексты (на форуме), то практически всегда делаю копипаст в PARI и смотрю работает ли (исключения -- если я делаю какую-то иллюстрацию и по ходу текста вставляю комментарии-пояснения).
А из тега code, кажется (но это не точно), так не получалось. То ли переводы строк там не такие то ли отступы, то ли ещё что, короче вставляешь, а оно не работает. Что-то не так <cr>,<lf>,<tab>,<eol> и т.п. При том, что копи-паст у меня бывает и кросс-ОСный (из виндовс в линукс, или из андроид-браузера в другое приложение андроида, командную строку, а то и вовсе -- через телеграм-сообщение самому себе). Там чем меньше непечатных символов, тем надежней копипаст будет. Пробелы PARI съедает без проблем, а вот отальное...
Но у меня и тексты в подавляющем большинстве однострочные :) Мне в этом видится некая как-бы элегантность, что ли.
P.S. Я кстати пишу код, так сказать, наугад, в смысле закрывающих скобок. Накидаю сколько-нибудь "на глаз", потом добавляю/убавляю, если интерпретатор ругается на синтаксис.

-- 12.12.2022, 18:54 --

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

Для длины 11 началось торможение.

Если я правильно понял как в википедях пишут, то длины 11 и нет. Там после 10 сразу 12 (ясно что 11 как-бы входит в 12, но чтобы было просто 11, a 12й член уже мимо -- почему-то таких не написали).

[gris]

wrest, да вроде бы есть АП для 11-ти:
p=60858179; d=2310
-1 60855869 0
01 60858179 1
02 60860489 1
03 60862799 1
04 60865109 1
05 60867419 1
06 60869729 1
07 60872039 1
08 60874349 1
09 60876659 1
10 60878969 1
11 60881279 1
12 60883589 0
С приграничными и индикатором простоты. Может быть, какого-то вида допускаются?
(701 +i*9902970)

[Dmitriy40]

В A033189 есть все AP-k до 21.

-- 12.12.2022, 21:41 --

gris
Быстрая проверка последовательности:

? isprime(vector(11+2,i,701+(i-2)*9902970))
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]

-- 12.12.2022, 22:11 --

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

(701 +i*9902970)

А ещё есть такие:
$13+8423621\cdot11\#\cdot i$
$17+21302684\cdot11\#\cdot i$
$19+4258072\cdot11\#\cdot i$
$23+214408638\cdot11\#\cdot i$
$29+3203185\cdot11\#\cdot i$
$73+980732\cdot11\#\cdot i$
$79+263739\cdot11\#\cdot i$
$89+3038461\cdot11\#\cdot i$

[Dmitriy40]

Собственно похоже цепочка $p_i=p+n\#\cdot d \cdot \{0\ldots n-1\}$ есть для всех $p>n$, но возможно с довольно большим $d$. Например для $p=53$ наименьшее $d=304577406$.