Putnam 2007, Problem A-4

A repunit is a positive integer whose digits in base $10$ are all ones. Find all polynomials $f$ with real coefficients such that if $n$ is a repunit, then so is $f(n)$.

Solution:
Note that $n$ is a repunit if and only if $9n+1 = 10^m$ for some power of 10 greater than 1. Consequently, if we put
$$g(n) = 9f\left(\frac{n-1}{9}\right) + 1,$$
then $f$ takes repunits to repunits if and only if $g$ takes powers of 10 greater than 1 to powers of 10 greater than 1. We will show that the only such functions $g$ are those of the form $g(n) = 10^c n^d$ for $d \geq 0$, $c \geq 1-d$ (all of which clearly work), which will mean that the desired polynomials $f$ are those of the form
$$f(n) = \frac{1}{9}\left(10^c(9n+1)^d - 1\right)$$
for the same $c,d$.

It is convenient to allow "powers of 10" to be of the form $10^k$ for any integer $k$. With this convention, it suffices to check that the polynomials $g$ taking powers of 10 greater than 1 to powers of 10 are of the form $10^c n^d$ for any integers $c,d$ with $d \geq 0$.

**First solution:** Suppose that the leading term of $g(x)$ is $ax^d$, and note that $a > 0$. As $x \to \infty$, we have $g(x)/x^d \to a$; however, for $x$ a power of 10 greater than 1, $g(x)/x^d$ is a power of 10. The set of powers of 10 has no positive limit point, so $g(x)/x^d$ must be equal to $a$ for $x = 10^k$ with $k$ sufficiently large, and we must have $a = 10^c$ for some $c$. The polynomial $g(x) - 10^c x^d$ has infinitely many roots, so must be identically zero.

**Second solution:** We proceed by induction on $d = \deg(g)$. If $d = 0$, we have $g(n) = 10^c$ for some $c$. Otherwise, $g$ has rational coefficients by Lagrange's interpolation formula (this applies to any polynomial of degree $d$ taking at least $d+1$ different rational numbers to rational numbers), so $g(0) = t$ is rational. Moreover, $g$ takes each value only finitely many times, so the sequence $g(10^0), g(10^1), \ldots$ includes arbitrarily large powers of 10. Suppose that $t \neq 0$; then we can choose a positive integer $h$ such that the numerator of $t$ is not divisible by $10^h$. But for $c$ large enough, $g(10^c) - t$ has numerator divisible by $10^b$ for some $b > h$, contradiction.

Consequently, $t = 0$, and we may apply the induction hypothesis to $g(n)/n$ to deduce the claim.

**Remark:** The second solution amounts to the fact that $g$, being a polynomial with rational coefficients, is continuous for the 2-adic and 5-adic topologies on $\mathbb{Q}$. By contrast, the first solution uses the "$\infty$-adic" topology, i.e., the usual real topology.