## Polynomials with at least one integer root

### Problem 269

Published on Saturday, 19th December 2009, 09:00 am; Solved by 437; Difficulty rating: 80%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})?