2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Гипотеза о многочленах, дающих простые значения
Сообщение28.09.2022, 14:23 
Заслуженный участник


20/12/10
8858
В книге Фомин А.А., Кузнецова Г.М. Международные математические олимпиады. М.: Дрофа, 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\}$.

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение28.09.2022, 17:11 
Заслуженный участник


20/08/14
11069
Россия, Москва
Возможно помогут ссылки из A014556?

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение28.09.2022, 18:03 
Заслуженный участник


20/12/10
8858
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 назад.

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


13/08/08
14430
Решил немножко попарить в $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$.
Вотъ. Извините за ерунду. Дело было вечером:)

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение28.09.2022, 19:56 
Заслуженный участник


20/12/10
8858
gris в сообщении #1565584 писал(а):
Дело было вечером:)
Увы, совершенно не понятно, как что-нибудь из этого можно доказать. Даже классический случай (Эйлеровы числа) требует весьма нетривиальной машинерии.

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение29.09.2022, 01:07 
Заслуженный участник


20/08/14
11069
Россия, Москва

(Оффтоп)

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

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение29.09.2022, 08:46 
Аватара пользователя


26/05/12
1534
приходит весна?
gris в сообщении #1565584 писал(а):
причём кортежей большей длины дальше и не наблюдается.

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

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


13/08/08
14430
Разумеется, это баловство и всё давно уже известно.
Вот возьмём строку-индикатор простых чисел $(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$
Просто интересно поглазеть :oops: :oops: :oops:

 Профиль  
                  
 
 Re: Гипотеза о многочленах, дающих простые значения
Сообщение06.10.2022, 17:44 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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