Целые корни многочлена

[hello19]

Всем доброго дня! Наткнулся вот на такую задачу:
Коэффициентами многочлена 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-ю нулями?

[ИСН]

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

[hello19]

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

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

[ИСН]

hello19 в сообщении #988703 писал(а):

А к чему это сакральное знание?

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

[hello19]

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

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

[ИСН]

hello19 в сообщении #988716 писал(а):

Если вы о том переборе, что для каждого многочлена

В принципе, можете не продолжать. И так понятно, что слова "каждого" и "$10^{16}$" не очень-то уживаются в одной фразе.
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

[venco]

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

[hello19]

ИСН в сообщении #988719 писал(а):

В принципе, можете не продолжать. И так понятно, что слова "каждого" и "$10^{16}$" не очень-то уживаются в одной фразе.

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

ИСН в сообщении #988719 писал(а):

Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

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

[ИСН]

hello19 в сообщении #988725 писал(а):

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

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

[hello19]

близко? Вы о чем?

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

[atlakatl]

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

[ИСН]

atlakatl в сообщении #988746 писал(а):

сколько квадратных многочленов произвольной области

Почему квадратных-то? И каких проблем? То есть проблемы будут, конечно, но после.

[hello19]

atlakatl в сообщении #988746 писал(а):

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

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

[ИСН]

Предложение есть, и я его повторял уже больше раз, чем обычно принято для задач с ProjectEuler:

ИСН в сообщении #988719 писал(а):

Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

[atlakatl]

ИСН в сообщении #988747 писал(а):

Почему квадратных-то? И каких проблем?

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