View source for Kaprekar's routine

{{Short description|Iterative algorithm}}
In [[Number theory|number theory]], '''Kaprekar's routine''' is an iterative algorithm named after its inventor, Indian mathematician [[Biography:D. R. Kaprekar|D. R. Kaprekar]]. Each iteration starts with a number, sorts the digits into descending and ascending order, and calculates the difference between the two new numbers.

As an example, starting with the number 8991 in base 10:

:{{math|1=9981 – 1899 = 8082}}
:{{math|1=8820 – 0288 = 8532}}
:{{math|1=8532 – 2358 = 6174}}
:{{math|1=7641 – 1467 = 6174}}

[[6174 (number)|6174]], known as '''Kaprekar's constant''', is a [[Fixed point (mathematics)|fixed point]] of this algorithm. Any four-digit number (in base 10) with at least two distinct digits will reach 6174 within seven iterations.{{sfn|Hanover|2017|loc=Overview|p=1}} The algorithm runs on any [[Natural number|natural number]] in any given number base.

==Definition and properties==
The algorithm is as follows:{{sfn|Hanover|2017|loc=Methodology|p=3}}

# Choose any [[Natural number|natural number]] <math>n</math> in a given number base <math>b</math>. This is the first number of the sequence.
# Create a new number <math>\alpha</math> by [[Sorting algorithm|sorting]] the digits of <math>n</math> in descending order, and another number <math>\beta</math>  by sorting the digits of <math>n</math> in ascending order. These numbers may have leading zeros, which can be ignored. Subtract <math>\alpha -\beta</math> to produce the next number of the sequence.
# Repeat step 2.

The sequence is called a '''Kaprekar sequence''' and the [[Function (mathematics)|function]] <math>K_b(n) = \alpha - \beta</math>  is the '''Kaprekar mapping'''. Some numbers map to themselves; these are the [[Fixed point (mathematics)|fixed point]]s of the Kaprekar mapping,<ref name="A099009">{{OEIS|A099009}}</ref> and are called '''Kaprekar's constants'''. Zero is a Kaprekar's constant for all bases <math>b</math>, 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,

: <math>K_{10}(3524) = 5432 - 2345 = 3087</math>

: <math>K_{10}(3087) = 8730 - 378 = 8352</math>

: <math>K_{10}(8352) = 8532 - 2358 = 6174</math>

: <math>K_{10}(6174) = 7641 - 1467 = 6174</math>

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 <math>\alpha</math> and <math>\beta</math> have the same [[Digit sum|digit sum]] and hence the same remainder modulo <math>b - 1</math>. Therefore, each number in a Kaprekar sequence of base <math>b</math> numbers (other than possibly the first) is a multiple of <math>b - 1</math>.

When leading zeroes are retained, only [[Repdigit|repdigit]]s 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 (where the length of the "1" sequence and the length of the "2" sequence are the same) 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 (where the length of the "3" sequence and the length of the "6" sequence are the same) are fixed points of the Kaprekar mapping.

===''b'' = 2''k''===
It can be shown that all natural numbers
:<math>m = (k) b^{2n + 3} \left(\sum_{i = 0}^{n - 1} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b \left(\sum_{i = 0}^{n - 1} b^i\right) + (k)</math>
are fixed points of the Kaprekar mapping in even base {{math|1=''b'' = 2''k''}} for all natural numbers {{mvar|n}}. 
{{Math proof|title=Proof|drop=hidden|proof=
<math>\alpha = (2k - 1) b^{2n + 2} \left(\sum_{i = 0}^{n} b^i\right) + (k) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) \left(\sum_{i = 0}^{n} b^i\right)</math>

<math>\beta = (k - 1) b^{2n + 2} \left(\sum_{i = 0}^{n} b^i\right) + (k) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (2k - 1) \left(\sum_{i = 0}^{n} b^i\right)</math>

<math>
\begin{align}
K_b(m) & = \alpha - \beta \\
& = ((2k - 1) - (k - 1)) b^{2n + 2} \left(\sum_{i = 0}^{n} b^i\right) + (k - k) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + ((k - 1) - (2k - 1)) \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 2} \left(\sum_{i = 0}^{n} b^i\right) - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + b^{2n + 2} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k) b^{2n + 1} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{2n + 1} + b^{2n + 1} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{2n + 1 - 1} \left(\sum_{i = 0}^{1} b^i\right) + b^{2n + 1 - 1} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{2n + 1 - n} \left(\sum_{i = 0}^{n} b^i\right) + b^{2n + 1 - n} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + b^{n + 1} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (2k) b^{n} - k \left(\sum_{i = 0}^{n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + k b^{n} - k \left(\sum_{i = 0}^{n - 1} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{n + 1 - 1} + b^{n + 1 - 1} - k \left(\sum_{i = 0}^{n - n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{n + 1 - n} \left(\sum_{i = 0}^{n} b^i\right) + b^{n + 1 - n} - k \left(\sum_{i = 0}^{n - n} b^i\right) \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b \left(\sum_{i = 0}^{n} b^i\right) + b - k \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b \left(\sum_{i = 0}^{n} b^i\right) + 2k - k \\
& = k b^{2n + 3} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b^{2n + 2} + (2k - 1) b^{n + 1} \left(\sum_{i = 0}^{n} b^i\right) + (k - 1) b \left(\sum_{i = 0}^{n} b^i\right) + k \\
& = m \\
\end{align}
</math>
}}

{| class="wikitable"
|+ Perfect digital invariants
! {{mvar|k}}
! {{mvar|b}}
! {{mvar|m}}
|---
| {{math|1}} || {{math|2}} || {{math|011, 101101, 110111001, 111011110001...}}
|---
| {{math|2}} || {{math|4}} || {{math|132, 213312, 221333112, 222133331112...}}
|---
| {{math|3}} || {{math|6}} || {{math|253, 325523, 332555223, 333255552223...}}
|---
| {{math|4}} || {{math|8}} || {{math|374, 437734, 443777334, 444377773334...}}
|---
| {{math|5}} || {{math|10}} || {{math|495, 549945, 554999445, 555499994445...}}
|---
| {{math|6}} || {{math|12}} || {{math|5B6, 65BB56, 665BBB556, 6665BBBB5556...}}
|---
| {{math|7}} || {{math|14}} || {{math|6D7, 76DD67, 776DDD667, 7776DDDD6667...}}
|---
| {{math|8}} || {{math|16}} || {{math|7F8, 87FF78, 887FFF778, 8887FFeFF7778...}}
|---
| {{math|9}} || {{math|18}} || {{math|8H9, 98HH89, 998HHH889, 9998HHHH8889...}}
|}

==Kaprekar's constants and cycles of the Kaprekar mapping for specific base ''b''==
All numbers are expressed in base {{mvar|b}}, using A−Z to represent digit values 10 to 35. 
{| class="wikitable"
! Base {{mvar|b}}
! Digit length
! Nontrivial (nonzero) Kaprekar's constants
! Cycles
|- 
| rowspan="8" | [[Base 2|2]] || 2 || 01<ref group=note name="retained">Leading zeroes retained.</ref> || &empty;
|- 
| 3 || 011<ref group=note name="retained">Leading zeroes retained.</ref> || &empty;
|- 
| 4 || 0111,<ref group=note name="retained">Leading zeroes retained.</ref> 1001 || &empty;
|- 
| 5 || 01111,<ref group=note name="retained">Leading zeroes retained.</ref> 10101 || &empty;
|- 
| 6 || 011111,<ref group=note name="retained">Leading zeroes retained.</ref> 101101, 110001 || &empty;
|- 
| 7 || 0111111,<ref group=note name="retained">Leading zeroes retained.</ref> 1011101, 1101001 || &empty;
|- 
| 8 || 01111111,<ref group=note name="retained">Leading zeroes retained.</ref> 10111101, 11011001, 11100001 || &empty;
|- 
| 9 || 011111111,<ref group=note name="retained">Leading zeroes retained.</ref> 101111101, 110111001, 111010001 || &empty;
|- 
| rowspan="8" | 3 || 2 || &empty; || &empty;
|- 
| 3 || &empty; || 022 → 121 → 022<ref group=note name="retained" />
|- 
| 4 || &empty; || 1012 → 1221 → 1012
|- 
| 5 || 20211 || &empty;
|- 
| 6 || &empty; || 102212 → 210111 → 122221 → 102212
|- 
| 7 || 2202101 || 2022211 → 2102111 → 2022211
|- 
| 8 || 21022111 || &empty;
|- 
| 9 || 222021001 || 
220222101 → 221021101 → 220222101

202222211 → 210222111 → 211021111 → 202222211
|- 
| rowspan="8" | 4 || 2 || &empty; || 03 → 21 → 03<ref group=note name="retained" />
|- 
| 3 || 132 || &empty;
|- 
| 4 || 3021 || 1332 → 2022 → 1332
|- 
| 5 || &empty; || 20322 → 23331 → 20322
|- 
| 6 || 213312, 310221, 330201 || &empty;
|- 
| 7 || 3203211 || &empty;
|- 
| 8 || 31102221, 33102201, 33302001 || 22033212 → 31333311 → 22133112 → 22033212
|- 
| 9 || 221333112, 321032211, 332032101 || &empty;
|- 
| rowspan="3" | 5 || 2 || 13 || &empty;
|- 
| 3 || &empty; || 143 → 242 → 143
|- 
| 4 || 3032 || &empty;
|- 
| rowspan="7" | 6 || 2 || &empty; || 05 → 41 → 23 → 05<ref group=note name="retained" />
|- 
| 3 || 253 || &empty;
|- 
| 4 || &empty; || 1554 → 4042 → 4132 → 3043 → 3552 → 3133 → 1554
|- 
| 5 || 41532 || 31533 → 35552 → 31533
|- 
| 6 || 325523, 420432, 530421 || 205544 → 525521 → 432222 → 205544
|- 
| 7 || &empty; || 4405412 → 5315321 → 4405412
|- 
| 8 || 43155322, 55304201 || 
31104443 → 43255222 → 33204323 → 41055442 → 54155311 → 44404112 → 43313222 → 31104443

42104432 → 43204322 → 42104432

53104421 → 53304221 → 53104421
|- 
| rowspan="3" | 7 || 2 || &empty; || &empty;
|- 
| 3 || &empty; || 264 → 363 → 264
|- 
| 4 || &empty; || 3054 → 5052 → 5232 → 3054
|- 
| rowspan="5" | 8 || 2 || 25 || 07 → 61 → 43 → 07<ref group=note name="retained" />
|- 
| 3 || 374 || &empty;
|- 
| 4 || &empty; || 
1776 → 6062 → 6332 → 3774 → 4244 → 1776

3065 → 6152 → 5243 → 3065
|- 
| 5 || &empty; || 
42744 → 47773 → 42744

51753 → 61752 → 63732 → 52743 → 51753
|- 
| 6 || 437734, 640632 || 310665 → 651522 → 532443 → 310665
|- 
| rowspan="3" | 9 || 2 || &empty; || 17 → 53 → 17
|- 
| 3 || &empty; || 385 → 484 → 385
|- 
| 4 || &empty; || 
3076 → 7252 → 5254 → 3076

5074 → 7072 → 7432 → 5074
|- 
| rowspan="9" | 10<ref name="sourceforge dec">{{Cite web|url=http://kaprekar.sourceforge.net/output/sample.php|title=Sample Kaprekar Series}}</ref> || 2 || &empty; || 09 → 81 → 63 → 27 → 45 → 09<ref group=note name="retained" />
|- 
| 3 || 495 || &empty;
|- 
| 4 || 6174 || &empty;
|- 
| 5 || &empty; || 
53955 → 59994 → 53955

61974 → 82962 → 75933 → 63954 → 61974

62964 → 71973 → 83952 → 74943 → 62964
|- 
| 6 || 549945, 631764 || 420876 → 851742 → 750843 → 840852 → 860832 → 862632 → 642654 → 420876
|- 
| 7 || &empty; || 7509843 → 9529641 → 8719722 → 8649432 → 7519743 → 8429652 → 7619733 → 8439552 → 7509843
|-
|8
|63317664, 97508421
|43208766 → 85317642 → 75308643 → 84308652 → 86308632 → 86326632 → 64326654 → 43208766
64308654 → 83208762 → 86526432 → 64308654
|- 
| 9 || 554999445, 864197532 ||
865296432 → 763197633 → 844296552 → 762098733 → 964395531 → 863098632 → 965296431 → 873197622 → 865395432 →753098643  → 954197541 → 883098612 → 976494321 → 874197522 → 865296432
|-
|10
|6333176664, 9753086421, 9975084201
|8655264432 → 6431088654 → 8732087622 → 8655264432

8653266432 → 6433086654 → 8332087662 → 8653266432

8765264322 → 6543086544 → 8321088762 → 8765264322

8633086632 → 8633266632 → 6433266654 → 4332087666 → 8533176642 → 7533086643 → 8433086652 → 8633086632

9775084221 → 9755084421 → 9751088421 → 9775084221
|- 
| rowspan="3" | 11 || 2 || 37 || &empty;
|- 
| 3 || &empty;|| 4A6 → 5A5 → 4A6
|- 
| 4 || &empty;||
3098 → 9452 → 7094 → 9272 → 7454 → 3098

5096 → 9092 → 9632 → 7274 → 5276 → 5096
|- 
| rowspan="7" | 12|| 2 || &empty;|| 0B → A1 → 83 → 47 → 29 → 65 → 0B<ref group="note" name="retained" />
|- 
| 3 || 5B6 || &empty;
|- 
| 4 || &empty; ||
3BB8 → 8284 → 6376 → 3BB8

4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198
|- 
| 5 || 83B74 || 64B66 → 6BBB5 → 64B66
|- 
| 6 || 65BB56 || 420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98
|- 
| 7 || 962B853 || 841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974
|- 
| 8 || 873BB744, A850A632 || 4210AA98 → A9737422 → 87428744 → 64328876 → 652BB866 → 961BB953 → A8428732 → 86528654 → 6410AA76 → A92BB822 → 9980A323 → A7646542 → 8320A984 → A7537642 → 8430A874 → A5428762 → 8630A854 → A540X762 → A830A832 → A8546632 → 8520A964 → A740A742 → A8328832 → 86546654
|- 
| rowspan="2" | 13 || 2 || &empty; || 1B → 93 → 57 → 1B
|- 
| 3 || &empty; || 5C7 → 6C6 → 5C7
|- 
| rowspan="2" | 14 || 2 || 49 || 
2B → 85 → 2B

0D → C1 → A3 → 67 → 0D<ref group=note name="retained" />
|- 
| 3 || 6D7 || &empty;
|- 
| rowspan="2" | 15 || 2 || &empty; || &empty;
|- 
| 3 || &empty; || 6E8 → 7E7 → 6E8
|- 
| rowspan="7" | 16<ref name="sourceforge hex">{{Cite web|url=http://kaprekar.sourceforge.net/output/sample_hex.php|title = Sample Kaprekar Series for hexadecimal numbers}}</ref> || 2 || &empty; || 
2D → A5 → 4B → 69 → 2D

0F → E1 → C3 → 87 → 0F<ref group=note name="retained" />
|- 
| 3 || 7F8 || &empty;
|- 
| 4 || &empty; || 
3FFC → C2C4 → A776 → 3FFC

A596 → 52CB → A596

E0E2 → EB32 → C774 → 7FF8 → 8688 → 1FFE → E0E2

E952 → C3B4 → 9687 → 30ED → E952
|- 
| 5 || &empty; || 
86F88 → 8FFF7 → 86F88

A3FB6 → C4FA4 → B7F75 → A3FB6

A4FA6 → B3FB5 → C5F94 → B6F85 → A4FA6
|- 
| 6 || 87FF78 || 
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
|- 
| 7 || C83FB74 ||
B62FC95 → D74FA83 → C92FC64 → D85F973 → C81FD74 → E94FA62 → DA3FB53 → CA5F954 → B74FA85 → B62FC95

B71FD85 → E83FB72 → DB3FB43 → CA6F854 → B73FB85 → C63FB94 → C84FA74 → B82FC75 → D73FB83 → CA3FB54 → C85F974 → B71FD85
|-
| 8 || &empty; || 
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
|}

{{reflist|group=note}}

==Kaprekar's constants in base 10==
===Numbers of length four digits===

In 1949 D. R. Kaprekar discovered<ref name=Kaprekar1955>{{cite journal|author=Kaprekar DR|title=An Interesting Property of the Number 6174 | journal=[[Scripta Mathematica]]|volume=15|pages=244–245|year=1955}}</ref> that if the above process is applied to four-digit numbers in base 10, the sequence converges to [[6174 (number)|6174]] within seven iterations or, more rarely, converges to 0. The number 6174 is the first Kaprekar's constant to be discovered, and thus is sometimes known as '''Kaprekar's constant'''.<ref name="mathworld">{{MathWorld | urlname = KaprekarRoutine | title = Kaprekar Routine}}</ref><ref>Yutaka Nishiyama, [http://plus.maths.org/issue38/features/nishiyama/index.html Mysterious number 6174]</ref><ref name=Kaprekar1980>{{cite journal|author=Kaprekar DR|title=On Kaprekar Numbers | journal=Journal of Recreational Mathematics|volume=13|issue=2|pages=81–82|year=1980}}</ref>

The set of numbers that converge to zero depends on whether leading zeros are  discarded (the usual formulation) or are retained (as in Kaprekar's original formulation). In the usual formulation, there are 77 four-digit numbers that converge to zero,<ref>{{OEIS|A069746}}</ref> for example 2111. However, in Kaprekar's original formulation the leading zeros are retained, and only [[Repdigit|repdigit]]s such as 1111 or 2222 map to zero. This contrast is illustrated below:

{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|- 
! discard leading zeros
! retain leading zeros
|- style="vertical-align: top;"
|
2111 − 1112 = 999<br/>
999 −  999 = 0
|
2111 − 1112 = 0999<br/>
9990 − 0999 = 8991<br/>
9981 − 1899 = 8082<br/>
8820 − 0288 = 8532<br/>
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.

[[File:KaprekarRoutineFlowGraph6174.svg|thumb|center|upright=3.5|Sequence of Kaprekar transformations ending in 6174]]

===Numbers of length three digits===

If the Kaprekar routine is applied to numbers of three digits in base 10, the resulting sequence will almost always converge to the value [[495 (number)|495]] in at most six iterations, except for a small set of initial numbers which converge instead to 0.<ref name="mathworld"/>

The set of numbers that converge to zero depends on whether leading zeros are discarded (the usual formulation) or are retained (as in Kaprekar's original formulation). In the usual formulation, there are 60 three-digit numbers that converge to zero,<ref>{{OEIS|A090429}}</ref> for example 211. However, in Kaprekar's original formulation the leading zeros are retained, and only [[Repdigit|repdigit]]s 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.

[[File:KaprekarRoutineFlowGraph495.svg|thumb|center|upright=3.4|Sequence of three digit Kaprekar transformations ending in 495]]

===Other digit lengths===
For digit lengths other than three or four (in base 10), 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.<ref name="mathworld" /> See the table in the [[Kaprekar's routine#Kaprekar's constants and cycles of the Kaprekar mapping for specific base b|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 (cycles of length one) 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.<ref>{{Cite web|url=http://kaprekar.sourceforge.net/output/sample2.php|title = Sample Kaprekar Series}}</ref><ref>{{Cite web|url=http://kaprekar.sourceforge.net/output/numplay/numplay.php|title=Playing with Numbers}}</ref>

==Programming example==
The example below implements the Kaprekar mapping described in the definition above [[Cycle detection|to search for Kaprekar's constants and cycles]] in [[Python (programming language)|Python]].

<source lang="python">
import string
from collections import deque
from collections.abc import Sequence, Generator


BASE36_DIGITS = f"{string.digits}{string.ascii_uppercase}"


def digit_count(x: int, /, base: int = 10) -> int:
    count = 0
    while x > 0:
        count += 1
        x //= base
    return count


def get_digits(x: int, /, base: int = 10, init_k: int = 0) -> str:
    if init_k > 0:
        k = digit_count(x, base)
    digits = deque()
    while x > 0:
        digits.appendleft(BASE36_DIGITS[x % base])
        x //= base
    if init_k > 0:
        for _ in range(k, init_k):
            digits.appendleft("0")
    return "".join(digits)


def kaprekar_map(x: int, /, base: int = 10, init_k: int = 0) -> int:
    digits = "".join(sorted(get_digits(x, base, init_k)))
    descending = int("".join(reversed(digits)), base)
    ascending = int(digits, base)
    return descending - ascending


def kaprekar_cycle(
    x: int | str | bytes | bytearray, /, base: int = 10
) -> list[int | str]:
    """
    Return Kaprekar's cycles as list

    >>> kaprekar_cycle(8991)
    [6174]
    >>> kaprekar_cycle(865296432)
    [865296432, 763197633, 844296552, 762098733, 964395531, 863098632, 965296431, 873197622, 865395432, 753098643, 954197541, 883098612, 976494321, 874197522]
    >>> kaprekar_cycle('09')
    [9, 81, 63, 27, 45]
    >>> kaprekar_cycle('0F', 16)
    ['0F', 'E1', 'C3', '87']
    >>> kaprekar_cycle('B71FD85', 16)
    ['B71FD85', 'E83FB72', 'DB3FB43', 'CA6F854', 'B73FB85', 'C63FB94', 'C84FA74', 'B82FC75', 'D73FB83', 'CA3FB54', 'C85F974']

    """
    leading_zeroes_retained = not isinstance(x, int)
    init_k = len(x) if leading_zeroes_retained else 0
    x = int(x) if base == 10 else int(x, base)
    seen = []
    while x not in seen:
        seen.append(x)
        x = kaprekar_map(x, base, init_k)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = kaprekar_map(x, base, init_k)
    return cycle if base == 10 else [get_digits(x, base, init_k) for x in cycle]


if __name__ == "__main__":
    import doctest

    doctest.testmod()
</source>

==See also==
* [[Arithmetic dynamics#Other areas in which number theory and dynamics interact|Arithmetic dynamics]]
* [[Collatz conjecture]]
* [[Dudeney number]]
* [[Factorion]]
* [[Happy number]]
* [[Kaprekar number]]
* [[Meertens number]]
* [[Narcissistic number]]
* [[Perfect digit-to-digit invariant]]
* [[Perfect digital invariant]]
* [[Sum-product number]]
* [[Sorting algorithm]]

==Citations==
{{reflist}}

==References==
{{refbegin}}
*{{cite journal |last=Hanover|first=Daniel |title=The Base Dependent Behavior of Kaprekar's Routine: A Theoretical and Computational Study Revealing New Regularities |journal=International Journal of Pure and Applied Mathematics | year = 2017 |arxiv=1710.06308}}
{{refend}}

==External links==
* {{cite web|last=Bowley|first=Roger|title=6174 is Kaprekar's Constant|url=https://www.numberphile.com/videos/6174|work=Numberphile|publisher=[[Biography:Brady Haran|Brady Haran]]|location=[[Organization:University of Nottingham|University of Nottingham]]|access-date=2024-01-17}}
* [https://www.youtube.com/watch?v=d8TRcZklX_Q Working link to YouTube]
* [http://www.panix.com/~baldwin/kaprekar.pl Sample (Perl) code to walk any four-digit number to Kaprekar's Constant]

{{Classes of natural numbers}}

[[Category:Base-dependent integer sequences]]
[[Category:Sorting algorithms]]

{{Sourceattribution|Kaprekar's routine}}