Гипотеза о многочленах, дающих простые значения

[nnosipov]

В книге Фомин А.А., Кузнецова Г.М. Международные математические олимпиады. М.: Дрофа, 1998 (есть на либгене) рассматривается такая задача:

28.6. Пусть $f(x)=x^2+x+p$, где $p$ --- натуральное число. Доказать, что если все числа $f(0)$, $f(1)$, ..., $f([\sqrt{p/3}])$ --- простые, то простыми являются вообще все числа $f(0)$, $f(1)$, ..., $f(p-2)$.

В конце решения этой задачи авторы приводят пример многочлена, удовлетворяющего условию задачи: это $f(x)=x^2+x+41$. Далее они пишут: "Кроме случая $p=41$, условию рассмотренной задачи удовлетворяют многочлены $x^2+x+p$ при $p= 2, 3, 5, 11, 17$. Неизвестно, существуют ли еще такие многочлены." Мне кажется, что ответ (отрицательный) на самом деле известен, причем довольно давно. Хотелось бы, во-первых, независимого подтверждения и, во-вторых, ссылок на литературу, содержащую подобные результаты. В частности, меня интересует, верно ли (и если да, то где доказано) следующее утверждение: если многочлен $2x^2+p$ принимает простые значения при $x=0,1,\dots,p-1$, то $p \in \{2,3,5,11,29\}$.

[Dmitriy40]

Возможно помогут ссылки из A014556?

[nnosipov]

Dmitriy40
Да, спасибо, что-то я не догадался заглянуть на oeis. Здесь действительно подтверждают. Вот это впечатлило (смотреть дату):

Цитата:

(PARI) is(p)=for(n=1, sqrt(p/3)\/1, if(!isprime(n*(n-1)+p), return(0))); 1 \\ Charles R Greathouse IV, Aug 26 2022

Если не ошибаюсь, 28-я IMO была лет так 30 назад.

[gris]

Решил немножко попарить в $2n^2+p$, причём поискать не кортеж простых с самого начала, а вообще кортеж максимальной длины с любого $n$ ну в диапазоне миллиончика. Состряпал программку

{for (k=0,50, l=0;lm=0;lmn=1;kk=2*k+1; 
for(n=0,1000000, 
if (isprime(2*n*n+kk),l=l+1,if (l>lm, lm=l; lmn=n-lm);l=0)
); print ("2n^2+",kk," lmax=",lm, " from=",lmn););}

и увидел удивительные вещи. Ваша гипотеза, разумеется, подтверждается, причём кортежей большей длины дальше и не наблюдается. Для остальных даже просто нечётных $p$ длины кортежей маленькие.
Но вот пример: для $2n^2+59$ есть пять последовательных значений, которые просты и начинаются с $n=203201$. Для $2n^2+71$ есть восемь последовательных значений, которые просты и начинаются с $n=8$.
Вотъ. Извините за ерунду. Дело было вечером:)

[nnosipov]

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

Дело было вечером:)

Увы, совершенно не понятно, как что-нибудь из этого можно доказать. Даже классический случай (Эйлеровы числа) требует весьма нетривиальной машинерии.

[Dmitriy40]

(Оффтоп)

nnosipov в сообщении #1565579 писал(а):

Dmitriy40
Да, спасибо, что-то я не догадался заглянуть на oeis.

Да дело не в OEIS, мне сама формула показалась знакомой, не так уж давно даже обсуждали её здесь (что кто-то там вдруг нашёл полиномы с более длинной последовательностью (чел ошибся), я проверял и искал тоже и потом даже находил списки рекордов), но просто там получилось найти быстрее (причём через гугл - вики - oeis, но ссыль на вики менее информативная). Теорию конечно не смотрел, понадеялся сами разберётесь полезно или нет.

[B@R5uk]

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

причём кортежей большей длины дальше и не наблюдается.

Это и не удивительно. Эйлеров полином основную свою массу простых результатов даёт в самом начале простых чисел, где их густота ещё достаточно велика, чтобы с небольшим везением можно получить длинный кортеж. Для больших результатов полиномы лучше судить не по длине кортежа, а по доле простых результатов. Можно ещё по доле составных результатов из двух простых множителей, больших, например, корня кубического из результата.

[gris]

Разумеется, это баловство и всё давно уже известно.
Вот возьмём строку-индикатор простых чисел $(001101010001010001010001000001...)$ и будем искать в ней подстроки.
$(1)$ определяет просто простые числа. Их бесконечно много.
$(101)$ определяет числа-близнецы. Б-г с ними.
$(101020201)$ (двойка это любое) соответствует началу значений многочлена $2n^2$ длины три.
Вот несколько троек:$(3,5,11), (5,7,13), (11,13,19), (29,31,19), (59,61,67), (71,73,79)$.
Если у тройки первое число обозначить $p$, то тройка будет соответствовать первым трём значениям многочлена $2n^2+p$. И как раз ранее упомянутым. Первые четыре продолжаются до нужной длины $p$.
Интереснее искать не тройки, а более длинные подстроки, определяемые многочленом $2n^2$.
В пределах миллиона их количество уменьшается с длиной:(
$3 \rightarrow 1427,\;\; 4 \rightarrow 363,\;\; 5 \rightarrow 108,\;\; 6 \rightarrow 37,\;\; 7\rightarrow 16$
Просто интересно поглазеть

[victor.l]

А почему и другие квадратичные вычеты не использовать. Например $2x^2+2x+19$.