2014 dxdy logo

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

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





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


01/06/12
734
Adelaide, Australia
gris в сообщении #1166881 писал(а):
То есть цель — оптимизация алгоритма перебора и проверок?

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

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

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

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

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение08.11.2016, 10:27 


15/03/11
116
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 составных чисел,

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение08.11.2016, 11:44 


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

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение08.11.2016, 13:32 


15/03/11
116
Сейчас в 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$ образует составные числа.

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


01/06/12
734
Adelaide, Australia
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$ образует составные числа.

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

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение08.11.2016, 14:29 


15/03/11
116
Малая теорема ферма гласит, что для простого 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$ на простоту

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


01/06/12
734
Adelaide, Australia
Очень красиво!!! Именно такой изящный подход я искал! Спасибо за подробное объяснение. Нашел что $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

 Профиль  
                  
 
 Re: Составные полиномы
Сообщение08.11.2016, 17:34 


15/03/11
116
dimkadimon в сообщении #1167156 писал(а):
Теперь рекорды просто посыпались (если нигде не ошибся):

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

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


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

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

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


01/06/12
734
Adelaide, Australia
zhekas в сообщении #1167213 писал(а):
Только вы уже вылезли за дополнительное ограничение.

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

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

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

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


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

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


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

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

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


01/06/12
734
Adelaide, Australia
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 тоже дают количество составных которое растет экспоненциально.

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


01/06/12
734
Adelaide, Australia
dimkadimon в сообщении #1168259 писал(а):
Могут ли все эти простые быть разными числами?

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

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


01/06/12
734
Adelaide, Australia
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$, а остальные должны быть составными. Правда я тут "жульничал" используя нецелые коэффициенты.

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


01/06/12
734
Adelaide, Australia
Работает даже для целых коэффициентов. Если $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$ составные.

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

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



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

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


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

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