2014 dxdy logo

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

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


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


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

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

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

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

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



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


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


что касается корня $-1$, то, имхо, можно вырисовывается критерий: сумма четных коэффициентов = сумме нечетных. Сколько таковых "пар" понятия пока не имею..

Ну а раз так, то можно как-то воспользоваться вот этим: http://www.genfunc.ru/theory/lucky/
Что думаете?

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


18/05/06
13197
с Территории
atlakatl в сообщении #988758 писал(а):
А как оценить число полиномов $ax^2+bx+c=0$, имеющих корнем $-1$, области $(N; N; N)$? - Тут всё гораздо сложнее.

Вы всё правильно говорите, но не то. Надо не оценку, а точно. И полином не квадратный. Да и область-то не до N, а до 10. Разница :!:

hello19 в сообщении #988760 писал(а):
вырисовывается критерий: сумма четных коэффициентов = сумме нечетных.
Вы где-то выше упоминали другое свойство, эквивалентное этому.

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


21/07/11
105
С распределениями ничего не выходит... видимо, стоит больше времени уделять аналитике...

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


21/07/11
105
[quote="ИСН в сообщении #988719"
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?[/quote]

Ну, например, можно взять остаток от деления максимального значения n (назовем его - N) на 11. Столько будет n, для которых соответствующий полином будет иметь корень -1.
Но среди таких n есть и те, полиномы которых имеют корень 0 - 110, например. Думаю, с этим как-то можно справиться.
Вопрос возникает, когда дело доходит до других делителей.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение11.03.2015, 22:01 
Модератор


20/03/14
8218
venco в сообщении #988723 писал(а):
Я думаю не стоит здесь обсуждать задачу 269 с ProjectEuler.


Соглашусь. Тем более, что подсказки уже прозвучали.
 i  Закрыто.

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


20/03/14
8218
 i  Открыто по просьбе ТС.

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


21/07/11
105
venco в сообщении #988723 писал(а):
Я думаю не стоит здесь обсуждать задачу 269 с ProjectEuler.


Погуглив, нашел ответ на эту задачу: https://code.google.com/p/projecteuler- ... rSolutions
Так что вред "олимпиаде" этой я своей темой, как мне кажется, не наношу..
Меня же интересует не ответ, а само решение.

И так, на данный момент дошел до лишь до того, чтобы посчитать сколько есть полиномов, имеющих корень $-1$.
Думал, посчитать количество полиномов, имеющих корни $-1$ и $0$ по формуле включений-исключений, т.е. так: (кол-во полиномов, имеющих корень -1) $+$ (кол-во полиномов, имеющих корень -1) $-$ (кол-во полиномов, имеющих корень -1 и 0)

итого, зная, что для N=100000 (таковых - 14696) рассчитываю:
$\frac{100000}{10} + \frac{100000}{11} - \frac{100000}{110} = 10000 + 9090 - 909 = 18181 > 14696$ (а ведь там еще и другие корни есть)
Где я ошибаюсь?

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


04/05/09
4432
hello19 в сообщении #989040 писал(а):
Где я ошибаюсь?
Возьмите, например, 627.

 Профиль  
                  
 
 Re: Целые корни многочлена
Сообщение12.03.2015, 12:51 


21/07/11
105
venco в сообщении #989064 писал(а):
hello19 в сообщении #989040 писал(а):
Где я ошибаюсь?
Возьмите, например, 627.

Да, попадаются, например, кратные 11, но не имеющие корня -1, такие как 209
Нужно как-то научится обходить это..

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


21/07/11
105
Вот как выглядят n, для корней с $-4$ по $-9$ и только для них... т.е. $-1$ среди корней нет (запускал для $ n  \leqslant 10000000$, само собой тут не все):

$

-9:      19 - 1919 - 190019 - 191919 - 1901919 - 1919019

-8:       18 - 1818 - 1998 - 18198 - 19818 - 180018 - 180198 - 181818 - 181998 

-7:       17 - 1717 - 1887 - 17187 - 18717 - 170017 - 170187 - 171717 - 171887

-6:        16 - 1616 - 1776 - 16176 - 17616 - 160016 - 160176 - 161616 - 161776

-5:       15 - 1515 - 1665 - 15165 - 16515 - 150015 - 150165 - 151515 - 151665 

-4:       14 - 28 - 294 - 1414 - 1428 - 1554 - 1568 - 2814 - 2828 - 2954 - 2968 
$

Пока что-то не осилил найти зависимость того, является ли только одно число (любое от -4 до -9) корнем полинома (не учитываю корни, для которых -1 корень)

знак "-" идет как разделитель.

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

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



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

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


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

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