Задача 269
Полиномы, имеющие хотя бы одно целое решение

Корнем или нулем полинома P(x) является решение уравнения P(x) = 0.
Определим P_(n) как полином, коэффициентами которого являются цифры числа n.
К примеру, P_(5703)(x) = 5x^(3) + 7x^(2) + 3.

Нетрудно увидеть, что:

  • P_(n)(0) является последней цифрой n,
  • P_(n)(1) является суммой всех цифр n,
  • P_(n)(10) является самим числом n.

Определим Z(k) как количество положительных целых чисел n, не превышающее k, для которого у полинома P_(n) есть по крайней мере одно целое решение.

Можно показать, что Z(100 000) равно 14696.

Чему равно Z(10^(16))?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net