Attention Conservation Notice

A quick look at an iterative algorithm that leads to a fixed cycle. I have no idea if there exist any applications outside of recreation. This is probably a little light/hand-wavey for a mathematician and not useful enough for a pragmatist.

Kaprekar's Routine

Kaprekar's routine is a simple iterative algorithm that leads to a fixed point. It is so simple that anyone can play with it and have fun. In that respect, it reminds me a bit of the Collatz conjecture.

A simple version of Kaprekar's Routine:

1. Choose a 4 digit number (in base 10) in which there are at least 2 unique digits
2. Rearrange the digits in descending order to obtain a number $\alpha$
3. Rearrange the digits in ascending order to obtain a number $\beta$
4. Find the difference $\gamma = \alpha - \beta$
5. Repeat the process starting from $\gamma$, adding leading 0 if the number goes below 1000.

By running this routine, every starting 4 digit number converges to the number 6174 in at most 7 iterations. 6174 is known as Kaprekar's Constant.

Here is an example with the starting number 8989:

1. $\gamma_1: 8989 \to (\alpha: 9988, \beta: 8899, \gamma_{2}: 1089)$
2. $\gamma_2: 1089 \to (\alpha: 9810, \beta: 0189, \gamma_{3}: 9621)$
3. $\gamma_3: 9621 \to (\alpha: 9621, \beta: 1269, \gamma_{4}: 8352)$
4. $\gamma_4: 8352 \to (\alpha: 8532, \beta: 2358, \gamma_{5}: 6174)$

↪ 6174 found! Took 4 iterations

This relationship exists for 3 digit numbers as well, except the fixed point is the number 495. Interestingly, for 3 digits the starting number converges in <= 6 iterations. Here is an example:

1. $\gamma_1: 221 \to (\alpha: 221, \beta: 122, \gamma_2: 099)$
2. $\gamma_2: 099 \to (\alpha: 990, \beta: 099, \gamma_3: 891)$
3. $\gamma_3: 891 \to (\alpha: 981, \beta: 189, \gamma_4: 792)$
4. $\gamma_4: 792 \to (\alpha: 972, \beta: 279, \gamma_5: 693)$
5. $\gamma_5: 693 \to (\alpha: 963, \beta: 369, \gamma_6: 594)$
6. $\gamma_6: 594 \to (\alpha: 954, \beta: 459, \gamma_{7}: 495)$

↪ 495 found! Took 6 iterations

This is a recursive map: $\mathcal{K}(\gamma_n) \mapsto \gamma_{n + 1}$ where $\mathcal{K}(n)$ is the Kaprekar Operation that maps the input $n$ to steps 2, 3, 4 above, i.e. $\mathcal{K}(\gamma_n) = F_2(\gamma_n) - F_3(\gamma_n)$ where $F_n$ is the $n$ th step at the beginning of this section.

Once the fixed point is found, it cycles:

4 Digit Version: $\gamma_1: 6174 \to (\alpha: 7641, \beta: 1467, \gamma_{2}: 6174)$

3 Digit Version: $\gamma_1: 495 \to (\alpha: 954, \beta: 459, \gamma_{2}: 495)$

Try it yourself:

from cytoolz import reduce
from operator import add

def kaprekar_routine(num: int, iterations: int = 0, num_digits: int = 4) -> int:
    """
    Shows the path to Kaprekar's Constant given a number.
    For 4 digits, simply pass a number. For 3 digits, run
    kaprekar_routine(3_digit_number, num_digits=3)
    """
    if num_digits == 4:
        goal, lower_bound = 6174, 1000
    elif num_digits == 3:
        goal, lower_bound = 495, 100
    else:
        return 0
    if num == goal:
        print(f'{goal} found! Took {iterations} iterations')
        return iterations
    else:
        print(f'Working on number: {num}')
        num_list = list(str(num))   # convert number to list of digits
        if num < lower_bound:       # add left 0 padding if needed
            num_list += ['0']
        if len(set(num_list)) < 2:  # check that number has more than 1 unique digit
            print(f'distinct digit condition not met for {num}')
            return 0
        num_str_list_to_int = lambda ls: int(reduce(add, ls))
        desc = num_str_list_to_int(sorted(num_list, reverse=True))  # alpha
        asc = num_str_list_to_int(sorted(num_list))                 # beta
        diff = desc - asc                                           # gamma
        return kaprekar_routine(diff, iterations := iterations + 1, num_digits)

kaprekar_routine(8989)  # change this number to see the results!

Iteration Counting

A reasonable next question: What is the likelihood that a given starting number will take $n$ iterations to reach the fixed point?

I generated the iteration lengths for each starting number in the range 1000 to 9999. Here is a histogram of the results:

Interestingly 3 steps is the most likely number of steps for any given number. This also shows that aside from 3, it is more likely that the iterations will be higher (closer to 7) than smaller. This gives us a sense of the tree that leads to our fixed point. It is bushy around the 3rd level and has many longer branches beyond iteration 3.

The Wiki article has a nice image of the decision tree:

We can also look at the indexed distribution:

This plot was made by reshaping the 9000 starting numbers into a $(90, 100)$ matrix. With this "coiling" a nice picture shows up and symmetry becomes apparent.

Uniqueness of the 4-Digit Case

Consider the operation that is performed by $K(\gamma_n)$. We can write steps 2 and 3 (putting numbers in descending/ascending order) like so:

For four integers $a, b, c, d$ where $9 \geq a \geq b \geq c \geq d \geq 0$ and they are not all the same digit, the max ordering is $abcd$ and the min ordering is $dcba$. Subtracting the two (step 4), gives us:

which leads to the following relations:

• $D = 10 + (d - a)$
• $C = 9 + c - b$
• $B = b - 1 - c$
• $A = a - d$

We can say we have found a kernel of Kaprekar's operation if $ABCD$ is equal to some combination of $a, b, c, d$ and the inequality constraint holds [2]. If this happens, then the sorting steps will make it such that applying Kaprekar's operation again will lead to our fixed point.

Since there are only $4! = 24$ possible permutations of $a,b,c,d$ we can generate all the permutations and swap $A,B,C,D$ with them. This will leave us with a system of 4 equations with 4 unknowns, which we can then solve for.

It turns out that there is only one combination that has an integer solution and follows the constraint,

• $ABCD = bdac$
• $a=7, b=6, c=4, d=1$

therefore, $ABCD = 6741$ and 6741 is the only number unchanged by Kaprekar's operation with 4 digits.

You can tinker with this yourself below:

import numpy as np
from itertools import permutations
from cytoolz import compose, curry, flip, nth

possible_permutations = permutations(['a', 'b', 'c', 'd'], 4)

letter_to_digit = lambda l: (ord(l) - 96) - 1

default_equation_lhs = lambda: [[-1, 0, 0, 1],
                                [0, -1, 1, 0],
                                [0, 1, -1, 0],
                                [1, 0, 0, -1]]

rhs = np.array([0, -1, 9, 10])

def valid_results(results):
    """checks 0 <= d <= c <= b <= a <= 9"""
    inbounds = all(0 <= r <= 9 for r in result)
    decreasing = all(np.diff(result) < 0)
    return inbounds and decreasing


table_printer = lambda ls: print("| {:20} | {:20} | {:20} |".format(*map(str, ls)))
separator = lambda: table_printer(['-' * 20] * 3)

table_printer(['Validity', 'Roots', 'Permutation'])
separator()
for perm in possible_permutations:
    equation_set = default_equation_lhs()
    for letter, equation in zip(perm, equation_set):
        equation[letter_to_digit(letter)] += 1
    try:
        result = np.linalg.solve(equation_set, rhs)
        result_sort = compose(int, curry(flip(nth), result), letter_to_digit)
        sorted_result = [result_sort(v) for v in perm]
        if valid_results(sorted_result):
            separator()
            table_printer(['Valid Set!', sorted_result, perm])
            separator()
        else:
            table_printer(['Invalid Set', sorted_result, perm])
    except np.linalg.LinAlgError:
        pass

Is this special?

Let's consider this problem in a different light. Suppose there are n people at a party, each of which has a hat. At the end of the night, everyone grabs a hat off the hat rack and leaves. What is the probability that no one left without their hat?

This problem is equivalent to counting permutations with no fixed points (called derangements).

The solution to the hat problem above is given on Wikipedia here. The key result is that the total number of derangements, $D(n)$, is given by:

$D(n) \approx \frac{n!}{e}$

i.e. there are about $n!/e$ derangements and the probability that a random permutation is a derangement is

$\frac{1}{e} \approx 0.37$

Therefore, the probability that a random permutation isn't a derangement (i.e. that there is at least 1 fixed point) is

$1 - \frac{1}{e} \approx 0.63$

We can think of Kaprekar's routine as a permutation group whose elements are permutations of the natural numbers and whose group operation is a composition of $K(\gamma)$ that finds a fixed point, i.e. for some $n$, $K^n(\gamma) = 6174$, $\gamma \in [1000, 9999], \gamma \in \mathbb{N}$.

Even though Kaprekar's Routine is interesting, it probably isn't that special. There are uncountably many routines that lead to a fixed point [5], so there are likely many more digit lengths/bases in which Kaprekar's Routine gives an interesting result.

Sources/Notes

[1] https://en.wikipedia.org/wiki/Kaprekar's_routine

Good examples, a nice formal specification, a flow chart and an alternative base table

[2] https://ijpam.eu/contents/2012-80-3/8/8.pdf

Cool little discussion of the uniqueness of Kaprekar's constant for n = 4

There are kernels for some other numbers as well:

[3] https://arxiv.org/pdf/1710.06308.pdf

Some proofs about the composition of intermediate numbers in Kaprekar cycles.

Exploration of Kaprekar's in other bases

Turns out that in base 3, on average it takes 3 iterations to reach a fixed point

[4] https://scholarscompass.vcu.edu/cgi/viewcontent.cgi?article=1287&context=jmsce_vamsc

Different ordering types for these routines, i.e. instead of 123, 321 there is also analogues of Kaprekar's permutation step like 123, 312.

[5] https://math.stackexchange.com/questions/4183370/what-is-the-logic-behind-kaprekars-constant

The way I see it: imagine all the possible procedures you could do on all the possible intervals of numbers. You're looking for one reasonably simple procedure on an easily described interval which has the property that it has a unique fixed point. Loads of procedures have fixed points (e.g. Brouwer's theorem; 1−1/e≈63% of all permutations are not derangements and therefore have at least one fixed point; etc.). Some of them will have unique fixed points. Finding a particularly nice procedure with a unique fixed point is probably going to be challenging, but when crowd-sourced it's not too surprising that somebody found one.

• Joshua P. Swanson