Kaprekar's routine


In number theory, Kaprekar's routine is an iterative algorithm that, with each iteration, takes a natural number in a given number base, creates two new numbers by sorting the digits of its number by descending and ascending order, and subtracts the second from the first to yield the natural number for the next iteration. It is named after its inventor, the Indian mathematician D. R. Kaprekar.

Definition and properties

The algorithm is as follows:
  1. Choose any natural number in a given number base. This is the first number of the sequence.
  2. Create a new number by sorting the digits of in descending order, and another new number by sorting the digits of in ascending order. These numbers may have leading zeros, which are discarded. Subtract to produce the next number of the sequence.
  3. Repeat step 2.
The sequence is called a Kaprekar sequence and the function is the Kaprekar mapping. Some numbers map to themselves; these are the fixed points of the Kaprekar mapping, and are called Kaprekar's constants. Zero is a Kaprekar's constant for all bases, and so is called a trivial Kaprekar's constant. All other Kaprekar's constant are nontrivial Kaprekar's constants.
For example, in base 10, starting with 3524,
with 6174 as a Kaprekar's constant.
All Kaprekar sequences will either reach one of these fixed points or will result in a repeating cycle. Either way, the end result is reached in a fairly small number of steps.
Note that the numbers and have the same digit sum and hence the same remainder modulo. Therefore, each number in a Kaprekar sequence of base numbers is a multiple of.
When leading zeroes are retained, only repdigits lead to the trivial Kaprekar's constant.

Families of Kaprekar's constants

In base 4, it can easily be shown that all numbers of the form 3021, 310221, 31102221, 3...111...02...222...1 are fixed points of the Kaprekar mapping.
In base 10, it can easily be shown that all numbers of the form 6174, 631764, 63317664, 6...333...17...666...4 are fixed points of the Kaprekar mapping.

''b'' = 2''k''

It can be shown that all natural numbers
are fixed points of the Kaprekar mapping in even base for all natural numbers.
12011, 101101, 110111001, 111011110001...
24132, 213312, 221333112, 222133331112...
36253, 325523, 332555223, 333255552223...
48374, 437734, 443777334, 444377773334...
510495, 549945, 554999445, 555499994445...
6125B6, 65BB56, 665BBB556, 6665BBBB5556...
7146D7, 76DD67, 776DDD667, 7776DDDD6667...
8167F8, 87FF78, 887FFF778, 8887FFFF7778...
9188H9, 98HH89, 998HHH889, 9998HHHH8889...

Kaprekar's constants and cycles of the Kaprekar mapping for specific base ''b''

All numbers are expressed in base, using A−Z to represent digit values 10 to 35.
BaseDigit lengthNontrivial Kaprekar's constantsCycles
2201
23011
240111, 1001
2501111, 10101
26011111, 101101, 110001
270111111, 1011101, 1101001
2801111111, 10111101, 11011001, 11100001
29011111111, 101111101, 110111001, 111010001
32
33022 → 121 → 022
341012 → 1221 → 1012
3520211
36102212 → 210111 → 122221 → 102212
3722021012022211 → 2102111 → 2022211
3821022111
39222021001
220222101 → 221021101 → 220222101
202222211 → 210222111 → 211021111 → 202222211
4203 → 21 → 03
43132
4430211332 → 2022 → 1332
4520322 → 23331 → 20322
46213312, 310221, 330201
473203211
4831102221, 33102201, 3330200122033212 → 31333311 → 22133112 → 22033212
49221333112, 321032211, 332032101
5213
53143 → 242 → 143
543032
6205 → 41 → 23 → 05
63253
641554 → 4042 → 4132 → 3043 → 3552 → 3133 → 1554
654153231533 → 35552 → 31533
66325523, 420432, 530421205544 → 525521 → 432222 → 205544
674405412 → 5315321 → 4405412
6843155322, 55304201
31104443 → 43255222 → 33204323 → 41055442 → 54155311 → 44404112 → 43313222 → 31104443
42104432 → 43204322 → 42104432
53104421 → 53304221 → 53104421
72
73264 → 363 → 264
743054 → 5052 → 5232 → 3054
822507 → 61 → 43 → 07
83374
84
1776 → 6062 → 6332 → 3774 → 4244 → 1776
3065 → 6152 → 5243 → 3065
85
42744 → 47773 → 42744
51753 → 61752 → 63732 → 52743 → 51753
86437734, 640632310665 → 651522 → 532443 → 310665
9217 → 53 → 17
93385 → 484 → 385
94
3076 → 7252 → 5254 → 3076
5074 → 7072 → 7432 → 5074
10209 → 81 → 63 → 27 → 45 → 09
103495
1046174
105
53955 → 59994 → 53955
61974 → 82962 → 75933 → 63954 → 61974
62964 → 71973 → 83952 → 74943 → 62964
106549945, 631764420876 → 851742 → 750843 → 840852 → 860832 → 862632 → 642654 → 420876
1077509843 → 9529641 → 8719722 → 8649432 → 7519743 → 8429652 → 7619733 → 8439552 → 7509843
10863317664, 97508421
43208766 → 85317642 → 75308643 → 84308652 → 86308632 → 86326632 → 64326654 → 43208766
64308654 → 83208762 → 86526432 → 64308654
11237
1134A6 → 5A5 → 4A6
114
3098 → 9452 → 7094 → 9272 → 7454 → 3098
5096 → 9092 → 9632 → 7274 → 5276 → 5096
1220B → A1 → 83 → 47 → 29 → 65 → 0B
1235B6
124
3BB8 → 8284 → 6376 → 3BB8
4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198
12583B7464B66 → 6BBB5 → 64B66
12665BB56420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98
127962B853841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974
128873BB744, A850A6324210AA98 → A9737422 → 87428744 → 64328876 → 652BB866 → 961BB953 → A8428732 → 86528654 → 6410AA76 → A92BB822 → 9980A323 → A7646542 → 8320A984 → A7537642 → 8430A874 → A5428762 → 8630A854 → A540X762 → A830A832 → A8546632 → 8520A964 → A740A742 → A8328832 → 86546654
1321B → 93 → 57 → 1B
1335C7 → 6C6 → 5C7
14249
2B → 85 → 2B
0D → C1 → A3 → 67 → 0D
1436D7
152
1536E8 → 7E7 → 6E8
162
2D → A5 → 4B → 69 → 2D
0F → E1 → C3 → 87 → 0F
1637F8
164
3FFC → C2C4 → A776 → 3FFC
A596 → 52CB → A596
E0E2 → EB32 → C774 → 7FF8 → 8688 → 1FFE → E0E2
E952 → C3B4 → 9687 → 30ED → E952
165
86F88 → 8FFF7 → 86F88
A3FB6 → C4FA4 → B7F75 → A3FB6
A4FA6 → B3FB5 → C5F94 → B6F85 → A4FA6
16687FF78
310EED → ED9522 → CB3B44 → 976887 → 310EED
532CCB → A95966 → 532CCB
840EB8 → E6FF82 → D95963 → A42CB6 → A73B86 → 840EB8
A80E76 → E40EB2 → EC6832 → C91D64 → C82C74 → A80E76
C60E94 → E82C72 → CA0E54 → E84A72 → C60E94
167C83FB74
B62FC95 → D74FA83 → C92FC64 → D85F973 → C81FD74 → E94fA62 → DA3FB53 → CA5F954 → B74FA85 → B62FC95
B71FD85 → E83FB72 → DB3FB43 → CA6F854 → B73FB85 → C63FB94 → C84FA74 → B82FC75 → D73FB83 → CA3FB54 → C85F974 → B71FD85
168
3110EEED → EDD95222 → CBB3B444 → 97768887 → 3110EEED
5332CCCB → A9959666 → 5332CCCB
7530ECA9 → E951DA62 → DB52CA43 → B974A865 → 7530ECA9
A832CC76 → A940EB66 → E742CB82 → CA70E854 → E850EA72 → EC50EA32 → EC94A632 → C962C964 → A832CC76
C610EE94 → ED82C722 → CBA0E544 → E874A872 → C610EE94
C630EC94 → E982C762 → CA30EC54 → E984A762 → C630EC94
C650EA94 → E852CA72 → CA50EA54 → E854AA72 → C650EA94
CA10EE54 → ED84A722 → CB60E944 → E872C872 → CA10EE54

Kaprekar's constants in base 10

Numbers of length four digits

In 1949 D. R. Kaprekar discovered that if the above process is applied to base 10 numbers of 4 digits, the resulting sequence will almost always converge to the value 6174 in at most 8 iterations, except for a small set of initial numbers which converge instead to 0. The number 6174 is the first Kaprekar's constant to be discovered, and thus is sometimes known as Kaprekar's constant.
The set of numbers that converge to zero depends on whether leading zeros are retained or are discarded.
In the usual formulation, there are 77 four-digit numbers that converge to zero, for example 2111. However, in Kaprekar's original formulation the leading zeros are retained, and only repdigits such as 1111 or 2222 map to zero. This contrast is illustrated below:
discard leading zerosretain leading zeros

2111 − 1112 = 999

999 − 999 = 0
2111 − 1112 = 0999

9990 − 0999 = 8991

9981 − 1899 = 8082

8820 − 0288 = 8532

8532 − 2358 = 6174

Below is a flowchart. Leading zeros are retained, however the only difference when leading zeros are discarded is that instead of 0999 connecting to 8991, we get 999 connecting to 0.

Numbers of length three digits

If the Kaprekar routine is applied to numbers of 3 digits in base 10, the resulting sequence will almost always converge to the value 495 in at most 6 iterations, except for a small set of initial numbers which converge instead to 0.
The set of numbers that converge to zero depends on whether leading zeros are discarded or are retained. In the usual formulation, there are 60 three-digit numbers that converge to zero, for example 211. However, in Kaprekar's original formulation the leading zeros are retained, and only repdigits such as 111 or 222 map to zero.
Below is a flowchart. Leading zeros are retained, however the only difference when leading zeros are discarded is that instead of 099 connecting to 891, we get 99 connecting to 0.

Other digit lengths

For digit lengths other than three or four, the routine may terminate at one of several fixed points or may enter one of several cycles instead, depending on the starting value of the sequence. See the table in the section above for base 10 fixed points and cycles.
The number of cycles increases rapidly with larger digit lengths, and all but a small handful of these cycles are of length three. For example, for 20-digit numbers in base 10, there are fourteen constants and ninety-six cycles of length greater than one, all but two of which are of length three. Odd digit lengths produce fewer different end results than even digit lengths.

Programming example

The example below implements the Kaprekar mapping described in the definition above to search for Kaprekar's constants and cycles in Python.

Leading zeroes discarded


def get_digits:
digits =
while x > 0:
digits.append
x = x // b
return digits

def form_number:
result = 0
for i in range:
result = result * b + digits
return result
def kaprekar_map:
descending = form_number
ascending = form_number
return descending - ascending

def kaprekar_cycle:
x = int
seen =
while x not in seen:
seen.append
x = kaprekar_map
cycle =
while x not in cycle:
cycle.append
x = kaprekar_map
return cycle

Leading zeroes retained


def digit_count:
count = 0
while x > 0:
count = count + 1
x = x // b
return count

def get_digits:
k = digit_count
digits =
while x > 0:
digits.append
x = x // b
for i in range:
digits.append
return digits

def form_number:
result = 0
for i in range:
result = result * b + digits
return result

def kaprekar_map:
descending = form_number
ascending = form_number
return descending - ascending

def kaprekar_cycle:
x = int
init_k = digit_count
seen =
while x not in seen:
seen.append
x = kaprekar_map
cycle =
while x not in cycle:
cycle.append
x = kaprekar_map
return cycle