2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Целые корни многочлена
Сообщение11.03.2015, 14:06 


21/07/11
105
Всем доброго дня! Наткнулся вот на такую задачу:
Коэффициентами многочлена Pn являются цифры числа n, т.е. $$P_{456} = 4x^{2} + 5x + 6$$
Хочу понять сколько таких n есть, которые не больше наперед заданного числа и у которых Pn имеет хотя бы один целый корень.

Для начала хочу научиться понимать, если ли у конкретного полинома, построенного по n корень. Дальше перебор и дело в шляпе.

В том случае, если n заканчивается на 0, то сразу помечаем многочлен как имеющий целый корень (в данном случае нулевой). Если нет, то смотрю на отрицательные делители (положительные не подойдут, т.к. коэффициенты многочлена положительные) свободного члена и просто подставляю в многочлен.

При n от 1 до 100000 получается как в тестовом примере - 14696 полиномов с целыми корнями.
Теперь стоит задача узнать, сколько будет таких полиномов для n до $$ 10^{16}$$
Проблема в том, что это может занимать слишком много времени, даже при многопоточном коде.

Решил посмотреть на распределение количества корней с периодом в 1000. Т.е. смотрю сколько корней было для n от 1 до 1000, от 1001 до 2000 и так до 500000. Наблюдается несколько периодичная структура - http://prntscr.com/6fe5ox
Вот результат для периода 10000 - http://prntscr.com/6fe6b8
Как думаете, можно ли из этого как-то оценить сколько корней для n ограниченного 10 с 16-ю нулями?

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


18/05/06
13197
с Территории
ProjectEuler опять, что ли?
Там надо как-то... не помню... для начала описать, кажется, у каких многочленов есть корень -1.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 14:23 


21/07/11
105
Ну тут просто, если n делится на 11, то -1 будет корнем (ну и условие, что свободный член не нулевой). А к чему это сакральное знание?

Про ProjectEuler только что прочел... нет, это не из этой оперы

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


18/05/06
13197
с Территории
hello19 в сообщении #988703 писал(а):
А к чему это сакральное знание?

Очень ли много различных целых отрицательных значений, в принципе подходящих на роль корней хоть какого-то из таких многочленов? Не перебрать ли нам их все?

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 14:57 


21/07/11
105
Их само собой не очень много, всего 9. В зависимости от свободного члена варьируется от 2-х до 4-х.

Если вы о том переборе, что для каждого многочлена (которых 10 в 16-ой) смотреть является ли корнем "потенциальное" число среди тех 9-ти, о которых выше писал или нет, то это плохой вариант

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


18/05/06
13197
с Территории
hello19 в сообщении #988716 писал(а):
Если вы о том переборе, что для каждого многочлена
В принципе, можете не продолжать. И так понятно, что слова "каждого" и "$10^{16}$" не очень-то уживаются в одной фразе.
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:15 
Заслуженный участник


04/05/09
4432
Я думаю не стоит здесь обсуждать задачу 269 с ProjectEuler.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:16 


21/07/11
105
ИСН в сообщении #988719 писал(а):
В принципе, можете не продолжать. И так понятно, что слова "каждого" и "$10^{16}$" не очень-то уживаются в одной фразе.

Об этом я еще в описании топика писал...

ИСН в сообщении #988719 писал(а):
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

Есть предложения? И почему смотрите именно на корень -1?

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:22 
Заслуженный участник
Аватара пользователя


18/05/06
13197
с Территории
hello19 в сообщении #988725 писал(а):
Есть предложения? И почему смотрите именно на корень -1?

Смотрю на этот корень, потому что он близко. Потом буду смотреть на другие. Вот это и есть моё предложение.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:31 


21/07/11
105
близко? Вы о чем?

Сейчас посмотрел на распределение количества корней в разбиениях по 10000 для n от 1 до 500000. Сильных выбросов не нашел:
11405
11342
11279
11219
11165
11120
...
Думаю, можно ли как-то учесть это..
Могу еще посмотреть как часто встречается корень -1, если надо..

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:48 
Аватара пользователя


21/09/12

1871
hello19
Численно перебирать значения и строить графики можно по массе задумок. И очень часто при графическом отображении наблюдаем интересные тенденции. Но аналитика в теории чисел гораздо сложнее численного эксперимента.
ИСН предлагает Вам попробовать аналитически подойти к задаче более простой и узкой: сколько квадратных многочленов произвольной области имеют корень $-1$. Просто попробуйте, - вылезет масса проблем. И столь глобальные вопросы задавать охота уменьшится.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:50 
Заслуженный участник
Аватара пользователя


18/05/06
13197
с Территории
atlakatl в сообщении #988746 писал(а):
сколько квадратных многочленов произвольной области
Почему квадратных-то? И каких проблем? То есть проблемы будут, конечно, но после.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 15:59 


21/07/11
105
atlakatl в сообщении #988746 писал(а):
hello19
Численно перебирать значения и строить графики можно по массе задумок. И очень часто при графическом отображении наблюдаем интересные тенденции. Но аналитика в теории чисел гораздо сложнее численного эксперимента.
ИСН предлагает Вам попробовать аналитически подойти к задаче более простой и узкой: сколько квадратных многочленов произвольной области имеют корень $-1$. Просто попробуйте, - вылезет масса проблем. И столь глобальные вопросы задавать охота уменьшится.


Я не говорю, что аналитика куска области может сразу сказать как решить задачу... тут скорее мысли в слух.
Критику поняли... есть ли какие-то предложения к решению задачи?

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


18/05/06
13197
с Территории
Предложение есть, и я его повторял уже больше раз, чем обычно принято для задач с ProjectEuler:
ИСН в сообщении #988719 писал(а):
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 16:04 
Аватара пользователя


21/09/12

1871
ИСН в сообщении #988747 писал(а):
Почему квадратных-то? И каких проблем?

Для $ax+b=0$ есть готовая вероятность взаимной простоты $\frac{6}{\pi^2}$.
А как оценить число полиномов $ax^2+bx+c=0$, имеющих корнем $-1$, области $(N; N; N)$? - Тут всё гораздо сложнее.

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

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



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

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


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

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