Составные полиномы

[dimkadimon]

$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

[gris]

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

[dimkadimon]

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

Известный полином $n!+2+x$ даёт подряд по крайней мере $n-1$ составныx при $x=0..(n-2)$

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

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

[gris]

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

[dimkadimon]

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

Ну как же, это при доказательстве того, промежуток между простыми может быть как угодно большим.

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

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

Вашу задачу можно только подбором решить

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

[gris]

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

[dimkadimon]

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

Но вот полином, который принимает только составные значения: $p(x)=2x$.
А он формально удовлетворяет Вашему условию до других слов.

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

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

Кстати, Ваша задача очень хороша, как исследовательская.

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

[gris]

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

[Dmitriy40]

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

а для второй вот: $x^2+26$. Даёт десять составных.

Простите, но всего 8, т.к. $9^2+26=107$, а оно простое.
Вот полином $x^2+29$ даёт 11 составных. А уже $x^2+576239$ даёт 401 составное.
Ну и как экстремум, $2x^2+2$ даёт бесконечное количество составных.

[gris]

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

[Dmitriy40]

Да, про ноль не обратил внимания, для меня он не является натуральным.

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

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

[gris]

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

[dimkadimon]

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$ четное и какие у него делители?

[dimkadimon]

dimkadimon в сообщении #1166485 писал(а):

Но почему $f(x)$ составное когда $x$ четное и какие у него делители?

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

[gris]

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