Kaprekar’s constant, $6174$, is one of the most famous constants in recreational mathematics. It comes out of the following procedure that looks a bit like a magic trick:
Start with a four-digit positive integer, and sort its digits in decreasing and increasing order.
Subtract the two numbers to get a new four-digit number.
Repeat forever.
For example, if we start with the number $1729$, the process goes
\[9721 − 1279 = 8442\]
\[8442 − 2448 = 5994\]
\[9954 − 4599 = 5355\]
\[5553 − 3555 = 1998\]
\[9981 − 1899 = 8082\]
\[8820 − 0288 = 8532\]
\[8532 − 2358 = 6174\]
\[7641 − 1467 = 6174\]
\[7641 − 1467 = 6174\]
\[\vdots\]
after which one gets $6174$ forever. If we start with another number like $8500$, we get
\[8500 − 0058 = 8442\]
\[8442 − 2448 = 5994\]
\[9954 − 4599 = 5355\]
\[5553 − 3555 = 1998\]
\[9981 − 1899 = 8082\]
\[8820 − 0288 = 8532\]
\[8532 − 2358 = 6174.\]
Surprise! We still get the same number $6174$ again. And in fact, in 1949, Indian schoolteacher Dattatreya Ramchandra Kaprekar found that no matter what four-digit number you start with, as long as not all four digits are identical, the process will always end with $6174$.
Kaprekar’s paper titled An Interesting Property of the Number 6174 formally appeared in Scripta Mathematica in 1955. The result entered popular culture when Martin Gardner covered it in Mathematical Games in the 1970′s, and since then the result has become immortal.
What about other bases 𝐵?
But a mathematician’s first instinct upon seeing this result is likely to ask more questions. How long does it take for us to enter a cycle? What if we change the number of digits? Or change the base that we’re working with? The original Kaprekar routine is just a starting point of a huge number of questions to explore.
For the rest of this blog post, we’re going to follow just one particular lead: we’re going to zoom in on just four-digit numbers, but in any base $B$. (For results known when we change the number of digits, see e.g. Thakur 2019.) Because there are only finitely many possible numbers, the process must surely start repeating itself eventually. So the first few natural questions might be:
How many different eventual cycles are there?
How long are those eventual cycles?
How long does it take to enter a cycle?
For example, when $B = 10$, the answer is that there is only 1 cycle of length 1, and it turns out that 7 steps is the longest possible delay before reaching $6174$.
But for other bases $B$, the picture can look quite different. For example, for $2 \leq B \leq 5$:
In binary (base $2$), there are two fixed points, not just one: $0111_2$ and $1001_2$.
In ternary (base $3$), one gets an oscillation between two numbers: $1012_3 \leftrightarrow 1221_3$.
For $B = 4$, there are two possible final trajectories: a fixed point at $3021_4$ or an oscillation $1332_4 \leftrightarrow 2022_4$.
But the $B = 5$ case is a lot like $B = 10$: there is a single final destination, $3032_5$.
One can also work out the same picture for other bases $B$. Here’s a picture of the ending situations for all $2 \leq B \leq 10$.
The labeling trick
Our recent paper with Richard Schwartz and Dinesh Thakur tackles the four-digit base $B$ problem and centers around this one weird trick. Given a four-digit number $n$ in any base $B$, if we sort its digits as $a_1 \geq a_2 \geq a_3 \geq a_4$, we define its label $L(n)$ to be the two numbers
\[L(n) := \left\{ \frac{a_1 + a_2 - a_3 - a_4}{2}, \frac{a_1 - a_2 + a_3 - a_4}{2} \right\}.\]
For example, if $n = 1998$, then
\[L(1998) = \left\{ \frac{9 + 9 - 8 - 1}{2}, \frac{9 - 9 + 8 - 1}{2} \right\} = \left\{ \frac{9}{2}, \frac{7}{2} \right\}.\]
The main idea of our paper is to ignore all the actual numbers and only look at the labels instead. How does the Kaprekar operation behave on the labels? In fact, the definition of label has been carefully choreographed so that the following theorem is true:
Theorem. Let $n$ be a four-digit number in base $B$, and $n'$ the next step in the Kaprekar process. Suppose that $L(n) = \{r, s\}$ where $r > s > 0$ and $B \neq 2r$. Then
\[L(n') = \{|2r - B|, 2s\}.\]
Continuing our earlier example of $n = 1998$ (so $r = \frac{9}{2}$ and $s = \frac{7}{2}$), the theorem predicts our next label should be $|10 - 2r| = 1$ and $2s = 7$. And indeed, as $n' = 9981-1899=8082$, the prediction holds:
\[L(8082) = \left\{ \frac{8 + 8 - 2 - 0}{2}, \frac{8 - 8 + 2 - 0}{2} \right\} = \{7,1\}.\]
This theorem already makes the Kaprekar process look a lot simpler. But going further, if you squint so that you can’t see the absolute value signs or the $B$, then $L(n')$ looks a whole lot like $\{2r, 2s\}$. To make the squinting precise, our paper uses a bookkeeping object called projective residue classes modulo $B$. So in these coordinates, the Kaprekar operation is just doubling the label, and that’s easy to understand! This gives us a foothold into the Kaprekar problem.
Applying the engine to odd bases 𝐵
The earlier theorem has some hypotheses necessary to fly: both $r > s > 0$ and $B \neq 2r$ are critical. However, in the cases where $B$ is odd, we’re able to prove that $r$ and $s$ become different positive integers after a short time, and stay that way forever after. That means $r > s > 0$ is automatically true, and $B \neq 2r$ is also free because we are assuming $B$ is odd! So our labeling theorem always applies, and gives us an engine to control Kaprekar’s process.
This gives us solid answers to most of the questions we asked earlier for odd $B$. With a bit more calculation, we’re able to prove the following results:
Theorem: When the base $B$ is odd, in the four-digit Kaprekar process:
At most four steps are required before entering a cycle.
If $B \geq 7$, then the length of the longest cycle is the smallest positive integer $m$ such that $2^m \pm 1$ is a multiple of $B$. In particular, the cycle length is always at most $\frac{B-1}{2}$.
The only odd values of $B$ with exactly one cycle are $B = 3$, $B = 5$, and $B = 7$. Moreover, our paper gives a full formula for the number of cycles of each length $L$.
The AxiomProver story
Of course, we didn’t go into the problem knowing what our results were going to look like. In fact, the original goal was much more modest. Schwartz and Thakur had approached us with numerical evidence suggesting that the cycle length should be no more than $\frac{B-1}{2}$ for odd $B$, and we had AxiomProver investigate this conjecture.
During this initial investigation, AxiomProver came up with the labeling idea.
Once we saw AxiomProver’s labeling idea, we realized it could do far more than just prove that every cycle length was at most $\frac{B-1}{2}$. So we wrote down a more precise conjecture based on the labels instead, which later became the main theorem of our paper. This theorem looks a bit more technical — for example, what we called $L(n)$ in this blog post is instead named $\Phi(d_1, d_2)$ with bookkeeping built-in — but the core insight remains the same.
Once our more ambitious goal was set, we ran AxiomProver again on the new objective. This time, we gave it only the upgraded problem statement, without a solution or backstory. We were happy to see that AxiomProver was able to autonomously construct the entire proof from scratch, and formalize it in Lean.
Paper and code
Paper: Four-digit Kaprekar dynamics in odd bases, by Evan Chen, Ken Ono, Richard E. Schwartz, Dinesh S. Thakur