Dozenal Wiki
Advertisement

Kaprekar's routine is an algorithm in recreational mathematics devised by the Indian mathematician D. R. Kaprekar which produces a sequence of numbers which either converges to a constant value or results in a repeating cycle. The algorithm is as follows:

  1. Choose any natural number n in some base (usually base 10). This is the first number of the sequence.
  2. Create a new number n′ by arranging the digits of n in descending order, and another new number n″ by arranging the digits of n in ascending order. These numbers may have leading zeros, which can be discarded (or alternatively, retained). Subtract n′n″ to produce the next number of the sequence.
  3. Repeat step 2.

For example, if we start with 375 then we get:

753 − 357 = 3E8
E83 − 38E = 7E4
E74 − 47E = 6E5
E65 − 56E = 5E6 (this value repeats indefinitely)

A sequence like this is sometimes called a Kaprekar sequence and the function K(n) = n′n″ is the Kaprekar mapping.

Some numbers map to themselves: for instance if n = 0, then 0 − 0 = 0; if n = 5E6, then E65 − 56E = 5E6; if n = 83E74, then E8743 − 3478E = 83E74. These are the fixed points of the Kaprekar mapping. If the sequence reaches one of these numbers, it will repeat indefinitely.

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 n′ and n″ have the same digit sum and hence the same remainder modulo E (if we are using base 10). Therefore, each number in a Kaprekar sequence of base 10 numbers (other than possibly the first) is a multiple of E. In the general case of base b, the numbers in the sequences will be multiples of b − 1.

Cycles[]

Digit length Cycles Cycle lengths Number of cycles
1 {0} 1 1
2 {00}, {0E, X1, 83, 47, 29, 65} 1, 6 2
3 {000}, {5E6} 1, 1 2
4 {0000}, {3EE8, 8284, 6376}, {4198, 8374, 5287, 6196, 7EE4, 7375} 1, 3, 6 3
5 {00000}, {64E66, 6EEE5}, {83E74} 1, 2, 1 3
6 {000000}, {420X98, X73742, 842874, 642876, 62EE86, 951963, 860X54, X40X72, X82832, 864654}, {65EE56} 1, X, 1 3
7 {0000000}, {841E974, X53E762, 971E943, X64E652, 960EX53, E73E741, X82E832, 984E633, 863E754}, {962E853} 1, 9, 1 3
8 {00000000}, {4210XX98, X9737422, 87428744, 64328876, 652EE866, 961EE953, X8428732, 86528654, 6410XX76, X92EE822, 9980X323, X7646542, 8320X984, X7537642, 8430X874, X5428762, 8630X854, X540X762, X830X832, X8546632, 8520X964, X740X742, X8328832, 86546654}, {873EE744}, {X850X632} 1, 20, 1, 1 4
9
X
E
10
Advertisement