2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Составные полиномы
Сообщение05.11.2016, 03:59 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
$f(x)=x^{12}+488669$ дает составные числа для $0 \leq x \leq 616979$. Смотрите тут: https://oeis.org/A122131

Задача: Найдите полином $f(x)$, который дает наибольшее количество составных чисел подряд. Другими словами, найдите $f(x)$ которое составное для $0 \leq x \leq K$, где $K$ как можно больше ($K>616979$) и $f(K+1)$ простое.
$f(x)$ должен иметь вид $A_0+A_1x+A_2x^2 + \ldots + A_nx^n$, где все коэффициенты $A_0 \ldots A_n$ целые числа.

Оригинальная версия задачи тут: http://www.primepuzzles.net/puzzles/puzz_855.htm

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


13/08/08
14429
Известный полином $n!+2+x$ даёт подряд по крайней мере $n-1$ составныx при $x=0..(n-2)$. Поэтому полинома, дающего наибольшее количество составных подряд, не существует без дополнительных ограничений. Например, что его коэффициенты не больше миллиона. Или, что степень его не меньше $12$.
Или я чего не понял?
А, наверное, условие, которое идёт за словами "другими словами", что составных должно быть ровно $k+1$ для заданного $k$? Но, согласитесь, что эти другие слова совершенно меняют условие :-)

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 11:07 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
gris в сообщении #1166183 писал(а):
Известный полином $n!+2+x$ даёт подряд по крайней мере $n-1$ составныx при $x=0..(n-2)$

Ух ты! Проверил и вроде правда. А где написано об этом известном полиноме?

Ну хорошо меняем немного условия задачи: коэффициенты должны быть не больше 10 миллионов. Таким образом ваш полином только 21 набирает при $n=8$.

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


13/08/08
14429
Ну как же, это при доказательстве того, промежуток между простыми может быть как угодно большим. Правда слова "подряд" в Вашем понимании и моём совпадают только для линейного полинома. Я думаю, Вашу задачу можно только подбором решить :-(

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 11:18 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
gris в сообщении #1166191 писал(а):
Ну как же, это при доказательстве того, промежуток между простыми может быть как угодно большим.

Спасибо. Кстати мне кажется что речь идет не о факториалах, а о праймориалах: https://ru.wikipedia.org/wiki/%D0%98%D0 ... 0%BC%D0%B8

gris в сообщении #1166191 писал(а):
Вашу задачу можно только подбором решить :-(


Возможно. Но при поиске многие варианты можно не рассматривать...

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


13/08/08
14429
Первый полином просто красив.
Но вот полином, который принимает только составные значения: $p(x)=2x$.
А он формально удовлетворяет Вашему условию до других слов.
Но мы все понимаем, о чём речь :-) Просто полная формализация нудна.
Кстати, Ваша задача очень хороша, как исследовательская. Если о ней думать, то порождается много вопросов: все ли натуральные числа содержатся в последовательности интервалов между простяшками и по конечному ли количеству раз. Верно ли то, что неразложимый над натуральными полином (корректно ли так сказать?) принимает бесконечное число простых значений? Ну и так далее. Конечно, специалист с этим знаком, но любителя задача может завлечь в интересные дебри. Может быть, даже близкие к Великой.

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 14:06 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
gris в сообщении #1166197 писал(а):
Но вот полином, который принимает только составные значения: $p(x)=2x$.
А он формально удовлетворяет Вашему условию до других слов.

Именно поэтому я добавил другие слова :)

gris в сообщении #1166197 писал(а):
Кстати, Ваша задача очень хороша, как исследовательская.

Да действительно. А у вас есть ответы или какие нибудь предположения к этим вопросам?

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 17:41 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Я очень поверхностно знаком с этой областью. Скорее всего, проводились какие-то поиски полиномов для простых чисел, типа знаменитого $x^2+x+1$. Ну и набрели на полином с большими пустыми интервалами в самом начале. Алгоритмически такой перебор организовать несложно, если есть функция проверки на простоту для достаточно простых чисел и огромное количество времени. Впрочем, я могу переоценивать.
Но неинтересно будет представить полином сотой степени с восьмизначными коэффициентами, который даёт миллион составных при последовательных натуральных значениях аргумента. А что-нибудь вида $2x^{16}+3x^8+K$ подойдёт, хотя и со скрипом.
Наверняка это уже исследовано, хотя сомневаюсь, что теоретически.
Ну если в рукопашную попробовать, то для первой степени я приводил пример, а для второй вот: $x^2+26$. Даёт десять составных. Мало, но с чего-то нужно начинать :-) .

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 18:47 
Заслуженный участник


20/08/14
11057
Россия, Москва
gris в сообщении #1166314 писал(а):
а для второй вот: $x^2+26$. Даёт десять составных.
Простите, но всего 8, т.к. $9^2+26=107$, а оно простое.
Вот полином $x^2+29$ даёт 11 составных. А уже $x^2+576239$ даёт 401 составное.
Ну и как экстремум, $2x^2+2$ даёт бесконечное количество составных. ;-)

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 19:17 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Dmitriy40, ладно, не десять, но уж девять. Начинаем с нуля.
А второй Ваш полином не подходит, так как он разложим в произведение. А мы работаем с полиномами, которые дают хотя бы одно простое значение. ВотЪ :!:

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 19:41 
Заслуженный участник


20/08/14
11057
Россия, Москва
Да, про ноль не обратил внимания, для меня он не является натуральным.

(Больше тысячи составных подряд.)

Перебор выдал полином $x^2+54168539$ дающий более тысячи (1007 если с $x=1$) составных подряд.

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение05.11.2016, 19:44 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Тут ещё есть требование: чтобы количество составных превышало величину свободного члена.

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение06.11.2016, 02:27 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
gris в сообщении #1166370 писал(а):
Тут ещё есть требование: чтобы количество составных превышало величину свободного члена.

Откуда такое требование?

-- 06.11.2016, 08:14 --

gris в сообщении #1166314 писал(а):
Я очень поверхностно знаком с этой областью. Скорее всего, проводились какие-то поиски полиномов для простых чисел

У Al Zimmermann было интересное соревнование на эту тему: http://recmath.com/contest/PGP/index.php

-- 06.11.2016, 09:08 --

Кстати задача относительно известная: http://mathworld.wolfram.com/Prime-Gene ... omial.html

До сих пор не могу понять почему именно этот полином $f(x)=x^{12}+488669$ дает много составных значений? Что особенного в степени 12 и в константе 488669? Понятно что если $x$ нечетное то $f(x)$ будет четное и таким образом составное. Но почему $f(x)$ составное когда $x$ четное и какие у него делители?

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение06.11.2016, 03:33 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dimkadimon в сообщении #1166485 писал(а):
Но почему $f(x)$ составное когда $x$ четное и какие у него делители?

Частично отвечаю на свой вопрос. Если $x \mod 10 = 2, 4, 6, 8$ то $x^{12}$ оканчивается на $6$ и тогда $f(x)$ оканчивается на 5 - значит составное. Осталось определить что происходит когда $x \mod 10 = 0$.

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение07.11.2016, 18:53 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Красивое наблюдение.
Ой, я только что увидел, что это раздел CS. То есть компьютерный подход и предполагается. То есть цель — оптимизация алгоритма перебора и проверок?
Двенадцатая степень, конечно, сильно сокращает количество необходимых проверок на простоту. Но не рискованно ли сокращать перебор константы числами, оканчивающимися на девять?

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

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



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

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


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

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