XLVII OM - I - Problem 2

A palindromic number is defined as a natural number whose decimal representation read from left to right is the same as when read from right to left. Let $ (x_n) $ be the increasing sequence of all palindromic numbers. Determine all prime numbers that are divisors of at least one of the differences $ x_{n+1}-x_n $.
The decimal representation of the palindromic number $ x_n $ (respectively: ($ 2m $)-digit or ($ 2m-1 $)-digit) looks like this:

or

($ c_i \in \{ 0,1,2,3,4,5,6,7,8,9\} $ for $ i = 1, \ldots ,m;\ c_1 \ne 0 $). There are three possible situations:
Case I. $ c_m \ne 9 $. If $ x_n $ has the form (1), then $ x_{n+1} $ (the smallest palindromic number greater than $ x_n $) has the decimal representation

where $ d_m = c_m + 1 $.
Justification: Example (3) shows that there are palindromic numbers greater than $ x_n $ and having the same initial digits $ c_1,c_2,\ldots,c_{m-1} $ as $ x_n $; thus, $ x_{n+1} $ must be one of these numbers. Its next ($ m $-th) digit cannot be $ c_m $, because then the number would be identical to $ x_n $ (formula (1)). By taking $ d_m= c_m +1 $ as the next digit, we get the only palindromic number with the initial digits $ c_1,c_2,\ldots,c_{m-1},d_m $ (its further digits are already uniquely determined; see formula (3)); and by writing any digit greater than $ d_m $ on the $ m $-th place, we get even larger numbers; therefore, formula (3) indeed represents the number $ x_{n+1} $.
Analogous reasoning shows that if $ x_n $ has the form (2), then $ x_{n+1} $ has the decimal representation

where $ d_m = c_m + 1 $.
We calculate the difference $ x_{n+1} -x_n $ using the usual subtraction algorithm (that is, by writing the digits of the number $ x_n $ under the corresponding digits of the number $ x_{n+1} $ and performing "written subtraction"). The result of the subtraction:

Case II. Not all digits of the number $ x_n $ (given by formula (1) or (2)) are nines, but the digit $ c_m $ is a nine: $ c_m = 9 $. Let $ c_k $ be the last digit different from $ 9 $ in the sequence $ c_1,c_2,\ldots,c_{m-1},c_m $. Then

where $ l = 2m-2k $ or $ l = 2m-1-2k $, depending on whether the number $ x_n $ is expressed by formula (1) or (2). In each of these cases, the smallest palindromic number greater than $ x_n $ has the representation

where $ d_k = c_k + 1 $. (Detailed justification - very similar to the one conducted in Case I.) The subtraction algorithm now gives the result

Case III. All digits of the number $ x_n $ are nines:

Then $ x_{n+1} = \overline{1 \underbrace{00\ldots 0}_{p-1}1} $, so

Cases I, II, III exhaust all possibilities. The results obtained in formulas (5), (6), (7) show that the only prime divisors of the differences $ x_{n+1}-x_n $ are the numbers $ 2 $, $ 5 $, and $ 11 $.