Take a 4 digit number such that it isn't made out the same digit $(1111, 2222, .. . $ etc$)$ Define an operation on such a four digit number by taking the largest number that can be constructed out of these digits and subtracting the smallest four digit number. For example, given the number $2341$, we have,
$4321 – 1234 = 3087$
Repeating this process with the results (by allowing leading zeroes) we get the following numbers:
$8730 – 0378 = 8352$
$8532 – 2358 = 6174$
What's more interesting is that with $6174$ we get
$7641 – 1467 = 6174$
and taking any four digit number we end up with 6174 after at most 7 iterations. A bit of snooping around the internet told me that this number is called the Kaprekar's constant. A three digit Kaprekar's contant is the number 495 and there's no such constant for two digit numbers.
My question is, how can we go about proving the above properties algebraically? Specifically, starting with any four digit number we arrive at 6174. I know we can simply test all four digit numbers but the reason I ask is, does there exist a 5 digit Kaprekar's constant? Or an $n$-digit Kaprekar's constant for a given $n$?
Best Answer
Note: For fun and curiosity I avoid a programming language and stick to algebraic expressions with the intention to feed this through Gnuplot:
The basic operation is $$ F(n) = F_+(n) - F_-(n) $$ where $F_+$ maps to the maximum digit number and $F_-$ maps to the minimum digit number.
We only consider the case of base $10$ non-negative $4$ digit numbers $$ (d_3 d_2 d_1 d_0)_{10} = \sum_{k=0}^3 d_k \, 10^k $$
To provide $F_+$ and $F_-$ we need a way to sort a set of four digits. This can be done by applying $\min$ and $\max$ functions $$ \begin{align} \min(a, b) &:= \frac{a + b - |a - b|}{2} \\ \max(a, b) &:= \frac{a + b + |a - b|}{2} \end{align} $$ like this: We start with calculating intermediate values $s_k$, $t_k$ $$ \begin{matrix} s_0 = \min(d_0, d_1) \\ s_1 = \max(d_0, d_1) \\ s_2 = \min(d_2, d_3) \\ s_3 = \max(d_2, d_3) \end{matrix} \quad\quad \begin{matrix} t_0 = \min(s_0, s_2) \\ t_1 = \max(s_0, s_2) \\ t_2 = \min(s_1, s_3) \\ t_3 = \max(s_1, s_3) \end{matrix} $$ and then get $$ d^+_0 = t_0 \quad\quad d^-_0 = t_3 \\ d^+_1 = \min(t_1, t_2) \quad\quad d^-_1 = \max(t_1, t_2) \\ d^+_2 = \max(t_1, t_2) \quad\quad d^-_2 = \min(t_1, t_2) \\ d^+_3 = t_3 \quad\quad d^-_3 = t_0 $$ where $d^+_k$ are the digits sorted to maximize and $d^-_k$ are the digits sorted to minimize. One can visualize this as a sorting network
For example $$ \begin{align} d^-_2 &= \min(t_1, t_2) \\ &= \min(\max(s_0, s_2), \min(s_1, s_3)) \\ &= \min(\max(\min(d_0, d_1), \min(d_2, d_3)), \min(\max(d_0, d_1), \max(d_2, d_3))) \end{align} $$ which is a complicated term but otherwise still a function of the $d_k$.
Then we need a way to extract the $k$-th digit: $$ \pi^{(k)}\left( (d_3 d_2 d_1 d_0)_{10} \right) = d_k $$ this can be done by the usual $$ \pi^{(3)}(n) = \left\lfloor \frac{n}{1000} \right\rfloor \\ \pi^{(2)}(n) = \left\lfloor \frac{n - 1000\, \pi^{(3)}(n)}{100} \right\rfloor \\ \pi^{(1)}(n) = \left\lfloor \frac{n - 1000\, \pi^{(3)}(n) - 100\, \pi^{(2)}(n)}{10} \right\rfloor \\ \pi^{(0)}(n) = n - 1000\, \pi^{(3)}(n) - 100\, \pi^{(2)}(n) - 10\, \pi^{(1)}(n) $$ Rewriting this for Gnuplot gives:
This works quite nice:
But it turns out that using the graphics is not precise enough to identify fixed points.
In the end one needs a computer programm to check all numbers $n \in \{ 0, \ldots, 9999 \}$ for a proper fixed point from $\mathbb{N}^2$.
Note: The $\mbox{equ}$ function was used to set the arguments with repeated digits to zero.
Update: Maybe one can do it better, the calculation precision is good enough:
Update: This seems to work:
Note: The algebraic expressions I used made analysis not easier, the terms are too unwieldy to give the insight to determine the fixed points. It boiled down to to trying out every argument and checking the function value via a computer.