Problem 269

Polynomials with at least one integer root

A root or zero of a polynomial P(`x`) is a solution to the equation P(`x`) = 0.

Define P_{n} as the polynomial whose coefficients are the digits of `n`.

For example, P_{5703}(`x`) = 5`x`^{3} + 7`x`^{2} + 3.

We can see that:

- P
_{n}(0) is the last digit of`n`, - P
_{n}(1) is the sum of the digits of`n`, - P
_{n}(10) is`n`itself.

Define Z(`k`) as the number of positive integers, `n`, not exceeding `k` for which the polynomial P_{n} has at least one integer root.

It can be verified that Z(100 000) is 14696.

What is Z(10^{16})?

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**