Fifty-four numbers funnel into 6174

Start with 3524. Its digits in decreasing order make 5432 and in increasing order 2345, and $5432 - 2345 = 3087$. Do the same to 3087: $8730 - 0378 = 8352$. Then $8532 - 2358 = 6174$. And then $7641 - 1467 = 6174$ again: the number reproduces itself. Dattatreya Ramchandra Kaprekar, a schoolteacher in Devlali, published this in 1955, and the striking part is not that 6174 is fixed but that every four-digit start — any four digits, leading zeros allowed, as long as they are not all equal — arrives there, and in at most seven steps.

This is iteration of a function in the purest form the staircase drawing was invented for: feed a number to a rule, feed the answer back in, and ask where the orbit goes. It is a map on a finite set, so every orbit must eventually repeat, as the orbit that must come back explained. That alone guarantees a cycle. What it does not explain is why there is only one, why it is a single point, and why the journey is so short.

The first step forgets almost everything #

Sort the digits of a four-digit string so that $a \ge b \ge c \ge d$. The large arrangement is $1000a + 100b + 10c + d$ and the small one $1000d + 100c + 10b + a$, so the routine gives

$$K = 999(a - d) + 90(b - c).$$

That is the whole explanation, in one line. The result does not depend on the four digits but only on two differences: the largest digit minus the smallest, which can be anything from 1 to 9 once a repdigit is excluded, and the middle two digits’ difference, which lies between 0 and the first. That allows $1 + 2 + \cdots + 10 - 1 = 54$ pairs, and so exactly 54 possible results. Ten thousand starting strings are reduced, after one subtraction, to fifty-four.

The computation confirms it: iterating the routine once on all ten thousand strings produces exactly 54 nonzero values, each of the form $999p + 90q$ with $1 \le p \le 9$ and $0 \le q \le p$. The ten repdigits 0000, 1111, …, 9999 go to zero and stay there; they are the only starts the theorem must exclude.

Now the dynamics is a map on 54 points, small enough to draw in full, and that is what the opening figure is. Apply the routine to each of the 54 and draw an arrow to the result. The arrows form a tree: every value leads, by a chain of at most six arrows, to 6174, which points to itself. There are three values one step away, twelve two steps away, ten at three, four and five, and eight at the maximum depth of six. No value leads anywhere else, there is no other cycle, and so there is nowhere else for an orbit to go.

The grid of pairs shows the same tree in a different arrangement. Each cell is labelled with how far it is from the root, and the root sits at $a - d = 6$, $b - c = 2$. It is the root because 6174’s own digits, sorted, are 7, 6, 4, 1, and $7 - 1 = 6$, $6 - 4 = 2$: the number is a cell whose value has the differences that index it. That is the whole content of being a fixed point, and a search of the 54 cells finds only one cell with the property.

The three-digit case by hand #

The same reasoning, one digit shorter, can be carried through without a computer, and it shows the mechanism at its barest. With three digits sorted as $a \ge b \ge c$, the routine gives $(100a + 10b + c) - (100c + 10b + a) = 99(a - c)$. The middle digit cancels completely, and the result is a multiple of 99 from 099 up to 891 — nine possible values. Three-digit strings collapse in one step to nine numbers.

Those nine can simply be followed. 099 becomes $990 - 099 = 891$; 891 becomes $981 - 189 = 792$; then $972 - 279 = 693$, $963 - 369 = 594$, $954 - 459 = 495$, and $954 - 459 = 495$ again. The other multiples lie along the same chain: 198 goes to 792, 297 to 693, 396 to 594. Every one of the nine is on a single path ending at 495, and the longest path, from 099, takes five further steps, so no three-digit start takes more than six. The tree for three digits is a line with three short branches.

What makes 495 fixed is visible in the same way: its digits sorted are 9, 5, 4, the difference of the outer two is 5, and $99 \times 5 = 495$. A three-digit fixed point is a multiple of 99 whose largest digit minus its smallest digit is its own multiplier, and running through the nine candidates shows that only 495 has the property. The four-digit argument is identical in shape and only longer, with 54 candidates in place of nine.

Seven steps at most, and three most often #

Every start takes one step to reach one of the 54 cells and then follows the tree. So a start needs one more step than the depth of the cell it lands on, and the deepest cells, six steps from the root, give the longest journeys: seven steps. The histogram counts every one of the 9,990 starts.

The counts are 1 (6174 itself), 383, 576, 2,400, 1,272, 1,518, 1,656 and 2,184 for zero to seven steps, averaging 4.668. The maximum, seven, is also the second most common, and the reason is that the depth of a cell in the tree has nothing to do with how many starts land on it. How many starts land on the cell $(p, q)$ is a count of four-digit strings whose sorted digits have those two differences — large for middling differences, small for extreme ones — and the deepest cells happen to collect a great many. The single most common count, three steps, comes from the twelve cells at depth two, which include several heavily populated ones.

Nothing in that explanation is specific to 6174 except the shape of the tree, and the shape of the tree is an accident of arithmetic: which cell’s value has which differences. Kaprekar’s discovery is that, for four decimal digits, the accident is as tidy as it could be.

Every start at once #

The figure of all ten thousand starts, each a cell in a hundred-by-hundred grid shaded by the number of steps, shows how the collapse looks from the starting side. Starts that are rearrangements of one another have the same sorted digits, so they take the same first step and the same number of steps overall. The grid therefore has the symmetries of rearranging digits: reading a start’s digits backwards, or swapping two of them, does not change its shade.

The picture is far less regular than the tree that produced it. The shade of a start depends on its two digit differences through the tree, and the differences of the digits of $100r + c$ jump about irregularly as $r$ and $c$ change. A map that is simple on the 54 cells looks complicated on the ten thousand starts, because the first step is a projection that scrambles which starts share a cell. That is a pattern well beyond this example: the long-run behaviour of an iterated map is decided on a small set the map quickly falls into, and the complexity of the transient is the complexity of how the map projects onto that set.

Two, three, five, six and seven digits #

The same routine can be run with any number of digits, and the computation iterates every string of two to seven digits until it repeats. For three digits the answer resembles four: every start with two different digits reaches 495, since $954 - 459 = 495$. For two digits there is no fixed point at all; the starts fall into the cycle $09 \to 81 \to 63 \to 27 \to 45 \to 09$, all ninety of them.

Five digits break the pattern entirely. The 99,990 non-repdigit starts split among three cycles: a two-cycle through 59994 and 53955, catching 3,190 starts, and two four-cycles, through 61974, 82962, 75933 and 63954, and through 62964, 71973, 83952 and 74943, catching 48,480 and 48,320. Six digits give two fixed points, 549945 and 631764, and a cycle of seven, which catches 935,520 of the 999,990 starts. Seven digits fall, every one, into a single cycle of eight numbers beginning 9529641.

So the uniqueness of 6174 is not a law of the routine. What is general is the collapse: with $d$ digits the result depends only on the differences of the digits paired from the outside in — largest with smallest, second-largest with second-smallest, and so on — so the number of possible results is the number of decreasing sequences of about $d/2$ differences, a few dozen or a few hundred, and the dynamics on those is a small directed graph. Whether that graph is one tree, several trees, or trees feeding cycles is decided case by case.

Other bases #

The routine makes sense in any base, and running it on every four-digit string in bases 3 to 16 shows how rare the base-ten behaviour is. In most bases the strings settle into two or more attractors, often cycles of length three to six. Base 15 has seven distinct attractors for four digits, among them a fixed point and six cycles.

Only two of the fourteen bases behave like base ten, with a single fixed point catching every start: base 10 itself, and base 5, where the fixed point is written 3032 in base-five digits — the number 392. Nobody has found a rule that predicts from the base which kind of behaviour four digits will show. Results exist for particular families of bases and digit counts — when a base is even, for instance, the fixed points of the two-digit and three-digit routines can be written down — but the general question is a matter of computing each case.

This is the surprising connection in a small example: a recreational curiosity about one number is really a statement about how a projection interacts with a base, and it belongs with problems like the differences round a ring, where repeated subtraction around a square of four numbers always reaches zero, and like the Collatz map, where a rule of comparable simplicity has defeated all attempts at a proof. The difference is the finiteness. Kaprekar’s routine on four digits lives on ten thousand states, so the question of where every orbit goes is settled by listing them. The Collatz map lives on all the whole numbers, and listing does not end.

Finite maps and their trees #

The structure the tree shows is universal for maps of a finite set to itself. Draw an arrow from each point to its image; every point has exactly one arrow out, so following arrows from any point must eventually revisit a point, and from then on it cycles. The whole picture is a set of cycles with trees hanging into them, a functional graph, and every function on a finite set is a tree with two marks turns exactly this structure into a counting argument. A random map on $N$ points has, on average, about $\tfrac12 \log N$ cycles and its typical orbit takes about $\sqrt{\pi N/8}$ steps to start repeating.

Kaprekar’s routine on ten thousand points is far from random by those standards. A random map on 10,000 points would usually have several cycles and paths of a hundred or so steps before repeating. Kaprekar’s has one cycle, a single point, and paths of at most seven steps. The difference is the projection onto 54 cells, which is a contraction of the state space by a factor of nearly two hundred in one step, and contraction is what makes iterated maps converge — the finite, arithmetic version of the contraction that pulls every orbit to a fixed point in continuous dynamics.

Every computer orbit is a Kaprekar routine #

There is a less recreational reason the finite case matters. A computer represents numbers with finitely many digits, so any map iterated on a computer is, in fact, a map on a finite set, and every orbit it computes must eventually repeat. The orbit a computer draws is therefore never the chaotic orbit of the real map; it is an orbit of a finite map that shadows it for a while and then, eventually, cycles. For the logistic map in double precision the cycles are enormously long and the question rarely matters. For a map rounded to a few digits, the computed dynamics is exactly a Kaprekar-style funnel into a few cycles.

The same thing happens on purpose in a chaotic map that always comes back: Arnold’s cat map, run on a grid of pixels, scrambles an image beyond recognition and then, because the grid is finite and the map is one-to-one, returns it exactly. Kaprekar’s routine is the opposite kind of finite map, many-to-one rather than one-to-one, and so instead of returning every state it discards almost all of them. A one-to-one map on a finite set is a permutation and every point lies on a cycle; a many-to-one map has trees hanging into its cycles, and Kaprekar’s has a single tree with one point at the root.

Seen from that angle, the speed of convergence is also unsurprising. A contracting map on the real line approaches its fixed point geometrically, and how fast the staircase arrives is set by the slope at the fixed point. A finite map cannot approach anything gradually; it arrives in a definite number of steps, and seven is simply the height of the tree. The finite version of a convergence rate is a depth.

Every case shown, and no case beyond #

The figures settle every case they show by exhaustion: every four-digit string, every string of two to seven decimal digits, every four-digit string in bases 3 to 16. They say nothing about eight or more digits, or about other bases, beyond what was run. In particular the claim that the general case is “decided case by case” is a statement about the absence of a known rule; it is not a theorem that no rule exists.

The tree in the first figure is drawn on the 54 values, not on the ten thousand starts, and the lines join each value to its image under one further step. The grid of all starts is accurate cell by cell, but the eye reads patterns into it that are partly the arrangement of the grid — rows of a hundred — rather than anything about the routine.

Ten million starts, and a schoolteacher’s paper #

Computed here: the routine on all ten thousand four-digit strings, the 54 values after one step and their identification as $999p + 90q$, the tree of those values with its depths, the histogram of steps with its average, the attractors for two to seven digits with the number of starts in each — 9,999,990 starts for seven digits — and the attractors for four digits in every base from 3 to 16.

Quoted: Kaprekar’s publication of 1955 and his biography, the general shape of known results for other bases and digit counts, and the statistics of random maps on finite sets.

Still open: a rule for which routines have one fixed point #

For which bases $b$ and digit counts $d$ does the routine have a single nonzero fixed point that every non-repdigit start reaches? Four decimal digits and three decimal digits do; so do four digits in base 5. The question has been studied by Klaus Eldridge and Seok Sagong, by Anne Ludington Young and others, who determined the fixed points and cycles for many families — two and three digits in every base, for instance — and the computations extend far beyond the table here. A complete description, giving the attractors for every base and every number of digits, is not known, and it is not clear that one exists in any simple form.

A more modest question is about the transient. The longest journey to the attractor is seven steps for four decimal digits; how does the longest journey grow with the number of digits, in base ten or in general? The collapse to the cells of digit differences bounds it by the number of cells, which grows only polynomially in $d$, but the actual depths are much smaller than that bound, and how much smaller is a question about the routine’s arithmetic that the tables answer only one case at a time.

A projection, then a tree #

Kaprekar’s routine on four digits gives $999(a - d) + 90(b - c)$, which depends on two digit differences only, so ten thousand starts collapse in one step to 54 values; those 54 form a single tree rooted at 6174, six levels deep, so every start reaches 6174 in at most seven steps. Iterated on two to seven digits and in other bases, the same collapse ends in cycles as often as in fixed points.

The story is a model of how iteration works on a finite set. Every orbit must repeat; a strong contraction in the first step makes the set it repeats on small; and once that set is small enough to draw, where every orbit goes is a matter of reading a picture. The surprise of 6174 is not that the routine converges but that, for four decimal digits, the small picture happens to be a tree with one root.