Searching for Kaprekar's constants: algorithms and results (Q2368417)

Let \(c_0\leq c_1 \leq c_2\leq c_3\) be decimal digits. Calculate in the decimal number system the difference \(\overline{c_3c_2c_1c_0}_{(10)} - \overline {c_0c_1c_2c_3}_{(10)} = \overline {d_3d_2d_1d_0}_{(10)}\). Designate \(c^{(1)}_i=d_j, i, j \in \{0,1,2,3\}\) such that \(c^{(1)}_0\leq c^{(1)}_1\leq c^{(1)}_2\leq c^{(1)}_3\). In 1955 D. R. Kaprekar showed that this procedure ends after no more than 7 steps with the number 6174 -- Kaprekar's constant. Many authors, such as J. H. Jordan (1964), H. Hasse (1978), H. Hasse and G. D. Prichett (1978), G. D. Prichett (1978), A. L. Ludington (1979), G. D. Prichett, A. L. Ludington and J. F. Lapenta (1981), K. E. Eldridge and S. Sagong (1988), cited in the paper, studied and generalized the above procedure about the system base and the number of digits of the respective Kaprekar constant. The author of the present paper starts with the following identity in an arbitrary number system base \(b:\) \[ \begin{multlined}\overline {d_{N-1} d_{N-2} \dots d_1 d_0}_{(b)} - \overline{d_0 d_1 \dots d_{N-2} d_{N-1}}_{(b)}\\ = \overline{d_{N-1}- d_0 d_{N-2} -d_1 \dots 0\,0}_{(b)}- \overline{0\,0 \dots d_{N-2} -d_1 d_{N-1}- d_0}_{(b)},\end{multlined} \] where \(d_{N-1}\geq d_{N-2} \geq \dots \geq d_1 \geq d_0\) are digits in base \(b\). The numbers in the right hand side of this equation contain zeros and \([N / 2]\) leading digits \(d_{N-1} - d_0,d_{N-2} -d_1 \dots\), which define directed edges of nodes, written in node notation \(\langle d_{N-1} - d_0 : d_{N-2} - d_1 : \dots\rangle\) (for the Kaprekar's number 6174 we have \(\langle 7 - 1 : 6 - 4\rangle\) or \(\langle 6 : 2 \rangle\)). The above procedure generates a graph with a path of directed edges which forms a 1-cycle. If in a given base the graph of \(N\)-digit numbers has only one 1-cycle, then we have a Kaprekar's constant. The author proposes a computer program that can be found at \url{http://math.scu.edu/~bwalden/kaprekar} and by which he deduces some assertions, as for instance the following Lemma 4.1: Let \(k \geq 6\). (a) In base \(b = 4k\), \(\langle 3k : 2k : k\rangle\) is a 1-cycle and \(\langle 3k : 2k : k +1\rangle\) starts a 19-cycle. (b) In base \(b=4k + 1\), \(\langle 3k + 1:2k+1 : k-1\rangle\) starts a 2-cycle, \(\langle 3k : 2k + 1 : k\rangle\) starts a 2-cycle, and \(\langle3k:2k+1:k+2 \rangle\) starts a 4-cycle. (c) In base \(b=4k-1\), \(\langle3k:2k-1:k \rangle\) starts an 8-cycle. (d) In base \(b=4k-2\), \(\langle3k:2k-1:k \rangle\) starts a 4-cycle. By using this lemma, the author deduces the following Theorem 4.2: The only 7-digit Kaprekar's constant is 3 203 211 in base \(b=4\) (J. H. Jordan knew this constant). He states Conjecture 4.3: The only cycles for bases \(b>21\) are those listed in Lemma 4.1. The author proves three theorems as follows. Theorem 5.1: Let \(N=6k+3\) and suppose \(b=(3k+2)a+d\), where \(-1\leq d\leq a-1\). Then \(\langle(3k+1)a+d:3ka+d:(3k-1)a+d:\dots:(k+1)a+d:ka:(k-1)a:(k-2)a: \dots:2a:a\rangle\) is a 1-cycle. Corollary 5.2. If \(N=6k+3\) has a Kaprekar's constant in base \(b\), then \(\lfloor\frac{b+1}{3k+2}\rfloor\leq\lceil\frac{b+1}{3k+3}\rceil\). Theorem 5.3. If \(N=6k+3\) has a Kaprekar's constant in base \(b\), then \(b\leq(6k+2)(3k+3)=(N+3)(N-1)/2\). Theorem 5.4. The only 9-digit Kaprekar's constant is 432 043 211 \(\langle4:3:2:1\rangle\) in base 5. There are no Kaprekar's constants with 15, 21, 27, or 33 digits.