2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Прогрессии из простых чисел
Сообщение10.12.2022, 11:29 


20/02/20
67
Здравствуйте.Известно,что существуют арифметические прогрессии сколь угодно большой длины,состоящие из простых чисел(теорема Тао).Мне захотелось проверить ресурсы домашнего компа(естественно,для небольших длин) и вот что получилось в 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 элементов из данного множества простых чисел.Может быть,возможен другой алгоритм в обход предварительного создания множества сочетаний?

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение10.12.2022, 16:06 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Ждал и ждал и надеялся, что кто-то напишет вечную истину. Наконец решил проверить, так ли понял?
Вот тупой перебор за минуту для прогрессии из 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

Что на самом деле нужно?

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение11.12.2022, 11:46 


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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение11.12.2022, 12:08 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 10:26 


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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 11:45 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Ну я только изучаю 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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 14:39 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 15:14 
Заслуженный участник


20/08/14
11065
Россия, Москва
https://en.wikipedia.org/wiki/Primes_in ... rogression

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

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

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

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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 15:19 


05/09/16
11467
genk в сообщении #1573530 писал(а):
.Интересно,каков предел длины прогрессии на домашнем компе,

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

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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 16:21 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 16:54 
Заслуженный участник


20/08/14
11065
Россия, Москва
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$).

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 18:33 


05/09/16
11467
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й член уже мимо -- почему-то таких не написали).

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 20:27 
Заслуженный участник
Аватара пользователя


13/08/08
14430
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)

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 21:34 
Заслуженный участник


20/08/14
11065
Россия, Москва
В 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$

 Профиль  
                  
 
 Re: Прогрессии из простых чисел
Сообщение12.12.2022, 22:42 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group