Kaprekar's routine

In number theory, Kaprekar's routine is an iterative algorithm named after its inventor, Indian mathematician 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:

9981 – 1899 = 8082
8820 – 0288 = 8532
8532 – 2358 = 6174
7641 – 1467 = 6174

6174, known as Kaprekar's constant, is a fixed point of this algorithm. Any four-digit number (in base 10) with at least two distinct digits will reach 6174 within seven iterations.[1] The algorithm runs on any natural number in any given number base.

Definition and properties

The algorithm is as follows:[2]

  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 number by sorting the digits of in ascending order. These numbers may have leading zeros, which can be ignored. 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,[3] 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 (other than possibly the first) 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 (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 = 2k

It can be shown that all natural numbers

are fixed points of the Kaprekar mapping in even base for all natural numbers .

Proof

Perfect digital invariants
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.

Base Digit length Nontrivial (nonzero) Kaprekar's constants Cycles
2201[note 1]
3011[note 1]
40111,[note 1] 1001
501111,[note 1] 10101
6011111,[note 1] 101101, 110001
70111111,[note 1] 1011101, 1101001
801111111,[note 1] 10111101, 11011001, 11100001
9011111111,[note 1] 101111101, 110111001, 111010001
32
3022 → 121 → 022[note 1]
41012 → 1221 → 1012
520211
6102212 → 210111 → 122221 → 102212
722021012022211 → 2102111 → 2022211
821022111
9222021001

220222101 → 221021101 → 220222101

202222211 → 210222111 → 211021111 → 202222211

4203 → 21 → 03[note 1]
3132
430211332 → 2022 → 1332
520322 → 23331 → 20322
6213312, 310221, 330201
73203211
831102221, 33102201, 3330200122033212 → 31333311 → 22133112 → 22033212
9221333112, 321032211, 332032101
5213
3143 → 242 → 143
43032
6205 → 41 → 23 → 05[note 1]
3253
41554 → 4042 → 4132 → 3043 → 3552 → 3133 → 1554
54153231533 → 35552 → 31533
6325523, 420432, 530421205544 → 525521 → 432222 → 205544
74405412 → 5315321 → 4405412
843155322, 55304201

31104443 → 43255222 → 33204323 → 41055442 → 54155311 → 44404112 → 43313222 → 31104443

42104432 → 43204322 → 42104432

53104421 → 53304221 → 53104421

72
3264 → 363 → 264
43054 → 5052 → 5232 → 3054
822507 → 61 → 43 → 07[note 1]
3374
4

1776 → 6062 → 6332 → 3774 → 4244 → 1776

3065 → 6152 → 5243 → 3065

5

42744 → 47773 → 42744

51753 → 61752 → 63732 → 52743 → 51753

6437734, 640632310665 → 651522 → 532443 → 310665
9217 → 53 → 17
3385 → 484 → 385
4

3076 → 7252 → 5254 → 3076

5074 → 7072 → 7432 → 5074

10[4]209 → 81 → 63 → 27 → 45 → 09[note 1]
3495
46174
5

53955 → 59994 → 53955

61974 → 82962 → 75933 → 63954 → 61974

62964 → 71973 → 83952 → 74943 → 62964

6549945, 631764420876 → 851742 → 750843 → 840852 → 860832 → 862632 → 642654 → 420876
77509843 → 9529641 → 8719722 → 8649432 → 7519743 → 8429652 → 7619733 → 8439552 → 7509843
8 63317664, 97508421 43208766 → 85317642 → 75308643 → 84308652 → 86308632 → 86326632 → 64326654 → 43208766

64308654 → 83208762 → 86526432 → 64308654

9554999445, 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

11237
34A6 → 5A5 → 4A6
4

3098 → 9452 → 7094 → 9272 → 7454 → 3098

5096 → 9092 → 9632 → 7274 → 5276 → 5096

1220B → A1 → 83 → 47 → 29 → 65 → 0B[note 1]
35B6
4

3BB8 → 8284 → 6376 → 3BB8

4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198

583B7464B66 → 6BBB5 → 64B66
665BB56420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98
7962B853841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974
8873BB744, 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
35C7 → 6C6 → 5C7
14249

2B → 85 → 2B

0D → C1 → A3 → 67 → 0D[note 1]

36D7
152
36E8 → 7E7 → 6E8
16[5]2

2D → A5 → 4B → 69 → 2D

0F → E1 → C3 → 87 → 0F[note 1]

37F8
4

3FFC → C2C4 → A776 → 3FFC

A596 → 52CB → A596

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

E952 → C3B4 → 9687 → 30ED → E952

5

86F88 → 8FFF7 → 86F88

A3FB6 → C4FA4 → B7F75 → A3FB6

A4FA6 → B3FB5 → C5F94 → B6F85 → A4FA6

687FF78

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

7C83FB74

B62FC95 → D74FA83 → C92FC64 → D85F973 → C81FD74 → E94FA62 → DA3FB53 → CA5F954 → B74FA85 → B62FC95

B71FD85 → E83FB72 → DB3FB43 → CA6F854 → B73FB85 → C63FB94 → C84FA74 → B82FC75 → D73FB83 → CA3FB54 → C85F974 → B71FD85

8

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

  1. Leading zeroes retained.

Kaprekar's constants in base 10

Numbers of length four digits

In 1949 D. R. Kaprekar discovered[6] that if the above process is applied to four-digit numbers in base 10, the sequence converges to 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.[7][8][9]

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,[10] 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 zeros retain 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.

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 in at most six iterations, except for a small set of initial numbers which converge instead to 0.[7]

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,[11] 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.

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.[7] 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 (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.[12][13]

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(x, b):
    digits = []
    while x > 0:
        digits.append(x % b)
        x = x // b
    return digits
    
def form_number(digits, b):
    result = 0
    for i in range(0, len(digits)):
        result = result * b + digits[i]
    return result

def kaprekar_map(x, b):
    descending = form_number(sorted(get_digits(x, b), reverse=True), b)
    ascending = form_number(sorted(get_digits(x, b)), b)
    return descending - ascending
    
def kaprekar_cycle(x, b):
    x = int (str(x), b)
    seen = []
    while x not in seen:
        seen.append(x)
        x = kaprekar_map(x, b)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = kaprekar_map(x, b)
    return cycle

Leading zeroes retained

 
def digit_count(x, b):
    count = 0
    while x > 0:
        count = count + 1
        x = x // b
    return count
    
def get_digits(x, b, init_k):
    k = digit_count(x, b)
    digits = []
    while x > 0:
        digits.append(x % b)
        x = x // b
    for i in range(k, init_k):
        digits.append(0)
    return digits
    
def form_number(digits, b):
    result = 0
    for i in range(0, len(digits)):
        result = result * b + digits[i]
    return result
    
def kaprekar_map(x, b, init_k):
    descending = form_number(sorted(get_digits(x, b, init_k), reverse=True), b)
    ascending = form_number(sorted(get_digits(x, b, init_k)), b)
    return descending - ascending
    
def kaprekar_cycle(x, b):
    x = int (str(x), b)
    init_k = digit_count(x, b)
    seen = []
    while x not in seen:
        seen.append(x)
        x = kaprekar_map(x, b, init_k)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = kaprekar_map(x, b, init_k)
    return cycle

See also

Citations
  1. Hanover 2017, p. 1, Overview.
  2. Hanover 2017, p. 3, Methodology.
  3. (sequence A099009 in the OEIS)
  4. "Sample Kaprekar Series".
  5. "Sample Kaprekar Series for hexadecimal numbers".
  6. Kaprekar DR (1955). "An Interesting Property of the Number 6174". Scripta Mathematica. 15: 244–245.
  7. Weisstein, Eric W. "Kaprekar Routine". MathWorld.
  8. Yutaka Nishiyama, Mysterious number 6174
  9. Kaprekar DR (1980). "On Kaprekar Numbers". Journal of Recreational Mathematics. 13 (2): 81–82.
  10. (sequence A069746 in the OEIS)
  11. (sequence A090429 in the OEIS)
  12. "Sample Kaprekar Series".
  13. "Playing with Numbers".

References
  • Hanover, Daniel (2017). "The Base Dependent Behavior of Kaprekar's Routine: A Theoretical and Computational Study Revealing New Regularities". International Journal of Pure and Applied Mathematics. arXiv:1710.06308.
Wikimedia Commons has media related to Kaprekar's constant.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.