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

[dimkadimon]

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

То есть цель — оптимизация алгоритма перебора и проверок?

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

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

Но не рискованно ли сокращать перебор константы числами, оканчивающимися на девять?

Рискованно, но такое сокращение ускоряет наш перебор примерно в 100 раз. Во первых мы проверяем только 1 из 10 константов, а во вторых мы проверяем только 1 из 10 $x$ - которые оканчиваются на 0. Кстати в своих поисках я нашел другие узоры которые тоже позволяют сокращать количество проверок. Например, бывает что константа четная. Также не исключаю другие степени.

А вот многие полиномы факторизируются и поэтому не дают простых значений, такие надо исключать. Например все полиномы вида $a^k + b^k$, где $k>1$ нечетное. Значит полиномы вида $x^{12}+b^3$ надо исключать. Какие еще виды надо исключать?

[zhekas]

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

Во первых мы проверяем только 1 из 10 константов, а во вторых мы проверяем только 1 из 10 $x$ - которые оканчиваются на 0.

Не один из десяти, а один из 2730 в обоих случаях.

-- Вт ноя 08, 2016 10:42:01 --

По такой логике функция вида: $f(x)=x^{36}+(2\cdot3\cdot5\cdot7\cdot13\cdot19\cdot37\cdot k-1)$
Должна дать результат получше. И проверять достаточно для $x=2\cdot3\cdot5\cdot7\cdot13\cdot19\cdot37\cdot k = 1919190k$. Таким образом, если найти такое число $1919190k-1$ составное, то мы уже получим ряд из как минимум 1919190 составных чисел,

[zhekas]

Кстати, число $1919189$ - составное.
Поэтому функция: $f(x)=x^{36}+1919189$ для $0\le x\le 1919189$ образует составные числа.

[zhekas]

Сейчас в maxima посчитал для $0\le i\le 79; f(1919190\cdot i)$ - составное, А для $i=80$ - простое.

Поэтому: функция: $f(x)=x^{36}+1919189$ для $0\le x\le 1919190\cdot80-1=153535199$ образует составные числа.

-- Вт ноя 08, 2016 13:43:06 --

А если возьмём функцию $f(x)=x^{36}+1919190\cdot4-1$, то для $0\le x\le 1919190\cdot369-1$ образует составные числа.

[dimkadimon]

zhekas в сообщении #1167058 писал(а):

Не один из десяти, а один из 2730 в обоих случаях.

Не могу понять почему это так? Понятно только то что 2730=2*3*5*7*13. Почему не используем фактор 11? Объясните тупому человеку...

-- 08.11.2016, 20:06 --

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

Поэтому: функция: $f(x)=x^{36}+1919189$ для $0\le x\le 1919190\cdot80-1=153535199$ образует составные числа.

А вот это уже круто! Проверил все верно.

[zhekas]

Малая теорема ферма гласит, что для простого p и взаимопростого с ним $a$
$a^{p-1} \bmod p \equiv 1$

$x^{12} = x^{13-1} = (x^{7-1})^2 = (x^{5-1})^3 = (x^{3-1})^6 = (x^{2-1})^{12}$


Возьмем произвольное число $a$ и найдём с каким числом из (13;7;5;3;2) оно взаимопросто (для примера 7). Тогда $a^{12} \bmod 7 \equiv 1$

Получается, что для любого числа, которое не делится одновременно на 13, 7, 5, 3, 2 мы можем подобрать такое $p$ (из них же), что $a^{12} \bmod p \equiv 1$

Если мы теперь к $a^{12}$ прибавим число равное $-1 \bmod p$, то данное число разделится на $p$.

Число $13\cdot7\cdot5\cdot3\cdot2\cdot k - 1 = 2730\cdot k-1$ как раз даёт -1 по всем этим модулям.

Получаем, что если a не делится на 2730 (тоесть не делится хотябы на одно из списка простыхчисел), то $a^{12}+2730\cdot k-1$ делится на одно из списка простых чисел.
Остаётся проверять числа вида $2730\cdot n$ на простоту

[dimkadimon]

Очень красиво!!! Именно такой изящный подход я искал! Спасибо за подробное объяснение. Нашел что $f(x)=x^{36}+1919190.11-1$ составное для $0 \leq x \leq 1919190.909-1 = 1744543709$

-- 08.11.2016, 21:10 --

Теперь рекорды просто посыпались (если нигде не ошибся):

$x^{36}+1919190.1124-1$ дает $1919190.1924=3692521560$ составных.

$x^{60}+56786730.2090-1$ дает $56786730.3181=180638588130$ составных.

Для степеней советую использовать вот эти числа: https://en.wikipedia.org/wiki/Highly_composite_number

[zhekas]

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

Теперь рекорды просто посыпались (если нигде не ошибся):

$x^{36}+1919190.1124-1$ дает $1919190.1924=3692521560$ составных.

$x^{60}+56786730.2090-1$ дает $56786730.3181=180638588130$ составных.

Только вы уже вылезли за дополнительное ограничение.

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

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

[dimkadimon]

zhekas в сообщении #1167213 писал(а):

Только вы уже вылезли за дополнительное ограничение.

Да действительно - я нарушил собственное правило. Ну хорошо, вот мои лучшие результаты в рамках конкурса (коэффициенты < 10М):

$x^{240} + 52296$ дает 567579340 составных.
$x^{180} + 172080$ дает 1321754160 составных.
$x^{60} + 1352064$ дает 1753628304 составных.
$x^{120} + 293600$ дает 2012047652 составных.

Возможно имеет смысл ввести понятие о "красоте" полинома. Например, красота полинома это количество его составных деленное на сумму его коэффициентов.

[dimkadimon]

$f(x)=2x$ принимает простое значение ровно один раз, когда $x=1$. $f(x)=2x^2$ принимает простое значение ровно два раза, когда $x=-1,+1$. Есть ли полином с целыми коэффициентами, который принимает простое значение ровно три раза? Как насчет 4, 5, или 6? Можно ли найти такой полином для любого k количества простых? Могут ли все эти простые быть разными числами?

[g______d]

Вот, как мне кажется, по делу:

http://www.ams.org/journals/proc/1986-0 ... 0840616-4/

[dimkadimon]

g______d в сообщении #1168261 писал(а):

Вот, как мне кажется, по делу:

http://www.ams.org/journals/proc/1986-0 ... 0840616-4/

Спасибо! Даже очень по делу. Автор доказывает что существуют полиномы $f(x)$ с целыми коэффициентами которые дают $\exp(C*\sqrt{L(f)/{\log{L(f)}}})$ составных. $L(f)$ измеряет "сложность" полинома: $L(f) = \sum_{i=0}^n |a_i|$, где $|a_i|=\log_2(a_i)$ количество цифр в бинарном представлении $a_i$. Кажется доказательство чем то похоже на идею zhekas, но я тут плохо разбираюсь. Кстати вот pdf статьи:

http://www.ams.org/journals/proc/1986-0 ... 0616-4.pdf

Полиномы zhekas тоже дают количество составных которое растет экспоненциально.

[dimkadimon]

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

Могут ли все эти простые быть разными числами?

Да могут! Например $f(x)=(x+3)(x-1)^2$. $f(0)=3$ и $f(2)=5$, а все остальные $f(x)$ составные.

[dimkadimon]

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

Да могут! Например $f(x)=(x+3)(x-1)^2$. $f(0)=3$ и $f(2)=5$, а все остальные $f(x)$ составные.

Кстати это работает для любых двух нечетных простых $p_1<p_2$. Если $f(x)=(x+p1)(2x/(p2-p1)-1)^2$ тогда $f(0)=p1$ и $f(p2-p1)=p2$, а остальные должны быть составными. Правда я тут "жульничал" используя нецелые коэффициенты.

[dimkadimon]

Работает даже для целых коэффициентов. Если $f(x)=\frac{p_1+p_2}{2}x^2+\frac{p_1-p_2}{2}x$ тогда $f(1)=p_1$ и $f(-1)=p_2$, а остальные $f(x)$ для целых $x$ составные.