Kaprekar's Routine
Table of Contents
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. I'm also using this post to try out Klipse for in-blog code execution.
Heads up!
This post is highly recommended to view on a desktop. The python code snippets are editable and runnable and (most of) the plots are interactive.
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:
- Choose a 4 digit number (in base 10) in which there are at least 2 unique digits
- Rearrange the digits in descending order to obtain a number \(\alpha\)
- Rearrange the digits in ascending order to obtain a number \(\beta\)
- Find the difference \(\gamma = \alpha - \beta\)
- 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:
- \(\gamma_1: 8989 \to (\alpha: 9988, \beta: 8899, \gamma_{2}: 1089)\)
- \(\gamma_2: 1089 \to (\alpha: 9810, \beta: 0189, \gamma_{3}: 9621)\)
- \(\gamma_3: 9621 \to (\alpha: 9621, \beta: 1269, \gamma_{4}: 8352)\)
- \(\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:
- \(\gamma_1: 221 \to (\alpha: 221, \beta: 122, \gamma_2: 099)\)
- \(\gamma_2: 099 \to (\alpha: 990, \beta: 099, \gamma_3: 891)\)
- \(\gamma_3: 891 \to (\alpha: 981, \beta: 189, \gamma_4: 792)\)
- \(\gamma_4: 792 \to (\alpha: 972, \beta: 279, \gamma_5: 693)\)
- \(\gamma_5: 693 \to (\alpha: 963, \beta: 369, \gamma_6: 594)\)
- \(\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 (click for full size):
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:
\[\begin{alignat*}{4} &a&b&&c&&d\\ -\hspace{.5cm}&d&c&&b&&a\\ \hline &A&B&&C&&D \end{alignat*}\]
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:
Digits Kernel 2 None 3 495 4 6174 5 None 6 549945, 631764 7 None 8 63317664, 97508421 9 554999445, 864197532 10 6333176664, 9753086421, 9975084201 - [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