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

[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$.

[GogalNikolay]

Цепочка из 60 простых чисел, порождаемых формулой a^2 + 163

Правило:

1. При чётном a: значение a^2 + 163 (до a = 38).
2. При нечётном a: значение \dfrac{a^2 + 163}{4} (до a = 79).

Чётная ветвь (a = 2k, k = 0, \ldots, 19): 4k^2 + 163

 k    4k²+163      k    4k²+163      k    4k²+163
 0      163        7      359       14      947
 1      167        8      419       15     1063
 2      179        9      487       16     1187
 3      199       10      563       17     1319
 4      227       11      647       18     1459
 5      263       12      739       19     1607
 6      307       13      839

Нечётная ветвь (a = 2k+1, k = 0, \ldots, 39): k^2 + k + 41

 k   k²+k+41     k   k²+k+41     k   k²+k+41
 0      41      14     251      27     797
 1      43      15     281      28     853
 2      47      16     313      29     911
 3      53      17     347      30     971
 4      61      18     383      31    1033
 5      71      19     421      32    1097
 6      83      20     461      33    1163
 7      97      21     503      34    1231
 8     113      22     547      35    1301
 9     131      23     593      36    1373
10     151      24     641      37    1447
11     173      25     691      38    1523
12     197      26     743      39    1601
13     223

Точка обрыва: обе ветви заканчиваются на делителе 41:

1. Чётная: k = 20 \Rightarrow 4 \cdot 400 + 163 = 1763 = 41 \times 43.
2. Нечётная: k = 40 \Rightarrow 40^2 + 40 + 41 = 1681 = 41^2.

Итого: 20 + 40 = 60 последовательных простых чисел.

Важное наблюдение: все простые числа из чётной ветви (4k^2+163) отсутствуют в классической цепочке Эйлера k^2+k+41, но при этом они выступают как простые делители составных чисел в этой цепочке. Это показывает нетривиальную связь между двумя семействами: чётная ветвь «поставляет» делители для неч

[mathpath]

Полином: P(x) = 2x^5 + 7x^4 - 29x^3 - 75x^2 + 7x + 71

Найдена цепочка из 22 подряд идущих значений, модули которых простые:

\begin{array}{rrr} P( 0) &=& 71 \\ P( -1) &=& 23 \\ P( 1) &=& -17 \\ P( -2) &=& 37 \\ P( 2) &=& -271 \\ P( -3) &=& 239 \\ P( 3) &=& -313 \\ P( -4) &=& 443 \\ P( 4) &=& 883 \\ P( -5) &=& -89 \\ P( 5) &=& 5231 \\ P( -6) &=& -2887 \\ P( 6) &=& 15773 \\ P( -7) &=& -10513 \\ P( 7) &=& 36919 \\ P( -8) &=& -26801 \\ P( 8) &=& 74687 \\ P( -9) &=& -57097 \\ P( 9) &=& 136943 \\ P(-10) &=& -108499 \\ P( 10) &=& 233641 \\ P(-11) &=& -190097 \end{array}

Цепочка начинается с x = -11 и заканчивается на x = +10 , если подряд слева направо.

И вдогонку
Полином: P(x) =8x^5 - 45x^4 - 5x^3 + 214x^2 - 48x - 83

25 подряд идущих значений, модули которых простые:

\begin{array}{rrr} P(0) &=& -83 \\ P(-1) &=& 131 \\ P(1) &=& 41 \\ P(-2) &=& -67 \\ P(2) &=& 173 \\ P(-3) &=& -3467 \\ P(3) &=& -137 \\ P(-4) &=& -15859 \\ P(4) &=& -499 \\ P(-5) &=& -46993 \\ P(5) &=& 1277 \\ P(-6) &=& -111539 \\ P(6) &=& 10141 \\ P(-7) &=& -230047 \\ P(7) &=& 34763 \\ P(-8) &=& -429907 \\ P(8) &=& 88493 \\ P(-9) &=& -746309 \\ P(9) &=& 190321 \\ P(-10) &=& -1223203 \\ P(10) &=& 365837 \\ P(-11) &=& -1914259 \\ P(11) &=& 648191 \\ P(-12) &=& -2883827 \\ P(12) &=& 1079053 \\ \end{array}