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. The algorithm runs on any natural number in any given number base.

Definition and properties

The algorithm is as follows:

1. Choose any natural number ${\displaystyle n}$ in a given number base ${\displaystyle b}$. This is the first number of the sequence.
2. Create a new number ${\displaystyle \alpha }$ by sorting the digits of ${\displaystyle n}$ in descending order, and another number ${\displaystyle \beta }$ by sorting the digits of ${\displaystyle n}$ in ascending order. These numbers may have leading zeros, which can be ignored. Subtract ${\displaystyle \alpha -\beta }$ to produce the next number of the sequence.
3. Repeat step 2.

The sequence is called a Kaprekar sequence and the function ${\displaystyle K_{b}(n)=\alpha -\beta }$ 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 ${\displaystyle b}$, 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,

${\displaystyle K_{10}(3524)=5432-2345=3087}$

${\displaystyle K_{10}(3087)=8730-378=8352}$

${\displaystyle K_{10}(8352)=8532-2358=6174}$

${\displaystyle K_{10}(6174)=7641-1467=6174}$

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

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

${\displaystyle 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)}$

are fixed points of the Kaprekar mapping in even base b = 2k for all natural numbers n.

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

All numbers are expressed in base b, using A−Z to represent digit values 10 to 35.

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 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.

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

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 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.

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, 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 (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. 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.

Sometimes these numbers (495, 6174, and their counterparts in other digit lengths or in bases other than 10) are called "Peyush constants" named after Peyush Dixit who solved this routine as a part of his IMO 2000 (International Mathematical Olympiad, Year 2000) thesis.

Programming example

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

See also

• 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

References

External links

• Bowley, Roger (5 December 2011). "6174 is Kaprekar's Constant". Numberphile. University of Nottingham: Brady Haran. Retrieved 2024-01-17.
• Working link to YouTube
• Sample (Perl) code to walk any four-digit number to Kaprekar's Constant