Kaprekar's routine

In number theory, Kaprekar's routine is an iterative algorithm named after its inventor, Indian mathematician D. R. Kaprekar. ^{[1] [2]} 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. ^[3] The algorithm runs on any natural number in any given number base.

Definition and properties

The algorithm is as follows: ^{[1] [4]}

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, ^[5] 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 constants 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 (within seven iterations or 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.

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.

Determination of Kaprekar numbers

In the following, "Kaprekar's constant k" refers to a number that become positive fixed point k as result of the Kaprekar's routine.

In 1981, G. D. Prichett, et al. showed that the Kaprekar's constants are limited to two numbers, 495 (3 digits) and 6174 (4 digits). ^[6] They also classified the Kaprekar numbers into four types, but there was some overlap in the classification.

In 2005, Y. Hirata calculated all fixed points up to 31 decimal digits and examined their distribution. ^[7]

In 2024, Haruo Iwasaki ^[8] of the Ranzan Mathematics Study Group (headed by Kenichi Iyanaga) showed that in order for a natural number to be a Kaprekar number, it must belong to one of five mutually disjoint sets composed of combinations of the seven numbers 495, 6174, 36, 123456789, 27, 124578 and 09. Iwasaki also showed that this new classification using the five sets includes a corrected classification by Prichett, et al.

As a result, if n is considered as a constant, then the number of decimal n-digit Kaprekar numbers is determined by two types of equations:

(1) ${\displaystyle n=3x\quad \quad (x\geq 1)\,,}$  ......... For the sequence of x 3-digit constants 495

(2) ${\displaystyle n=4+2x\quad (x\geq 0)\,,}$  ...... Sequence of 4-digit constant 6174 followed by x 2-digit constants 36

or by three types of Diophantine equations:

(3) ${\displaystyle n=9x+2y\quad (x\geq 1,\ y\geq 0)\,,}$  ......... Sequence of x 123456789's and y 36's

(4) ${\displaystyle n=9x+14y\quad (x\geq 1,\ y\geq 1)\,,}$  ...... Sequence of x 123456789's and y (36 495495 272727)s

(5) ${\displaystyle n=6x+2y+9z+2u\quad (x\geq 1,\ y\geq 1,\ z\geq 0,\ u\geq 0)\,.}$  ... Sequence of 124578's, 09's, 123456789's and 36's

It was found that the number of integer solutions (sets of x~u) of the equations that can be established is the same as the number of solutions that express all of the n-digit Kaprekar numbers. ^[8]

The above equations confirm that there are no other Kaprekar's constants than 495 and 6174. There are no Kaprekar numbers for 1, 2, 5, or 7 digits, since they do not satisfy any of equations (1)~(5). For six-digit numbers, there are two solutions that satisfy equations (1) and (2). ^[9] Furthermore, it is clear that even-digits with greater than or equal to 8, ^[10] and with 9 digits, ^[11] or odd-digits with greater than or equal to 15 digits ^[12] have multiple solutions. Although 11-digit and 13-digit numbers have only one solution, it forms a loop of five numbers and a loop of two numbers, respectively. ^[13] Hence, Prichett's result that the Kaprekar's constants are limited to 495 (3 digits) and 6174 (4 digits) ^[14] is verified.

Therefore, the problem of determining all of the Kaprekar's constants and the number of these was solved. ^[8] An example below will explain the Iwasaki's result.

Example: In the case where decimal digits n = 23, since n is an odd number and is not a multiple of 3, the equations (1) and (2) do not hold, and the only equations that can hold are (3), (4) and (5). And if the operation (denoted by K₁₀ ) defined above is applied once to the numbers corresponding to the solutions of these equations, seven Kaprekar numbers can be obtained.

(3) The solution to 23 = 9x + 2y is

(x, y) = (1, 7) :  ...... Sequence of a 123456789 followed by seven 36's

K₁₀ (123456789 36363636363636) = 86433333331976666666532.

(4) The solution to 23 = 9x + 14y is

(x, y) = (1, 1) :  ...... Sequence of 123456789 followed by 36 495495 272727

K₁₀ (123456789 36 495495 272727) = 87765443219997765543222.

(5) The solutions to 23 = 6x + 2y + 9z + 2u are

(x, y, z, u) = (1, 4, 1, 0) :  ...... Sequence of 124578, four 09's and 123456789

K₁₀ (124578 09090909 123456789) = 99998765420987543210001,

(x, y, z, u) = (1, 3, 1, 1) :  ...... Sequence of 124578, three 09's, 123456789 and 36

K₁₀ (124578 090909 123456789 36) = 99987654320987654321001,

(x, y, z, u) = (1, 2, 1, 2) :  ...... Sequence of 124578, two 09's, 123456789 and two 36's

K₁₀ (124578 0909 123456789 3636) = 99876543320987665432101,

(x, y, z, u) = (1, 1, 1, 3) :  ...... Sequence of 124578, 09, 123456789 and three 36's

K₁₀ (124578 09 123456789 363636) = 98765433320987666543211, and

(x, y, z, u) = (2, 1, 1, 0) :  ...... Sequence of two 124578's, 09 and 123456789

K₁₀ (124578124578 09 123456789) = 98776554210988754432211.

Families of Kaprekar's constants

In case where even base (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.

Proof

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

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

${\displaystyle {\begin{aligned}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)\\&=kb^{2n+2}\left(\sum _{i=0}^{n}b^{i}\right)-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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)+kb^{n}-k\left(\sum _{i=0}^{n-1}b^{i}\right)\\&=kb^{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)\\&=kb^{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)\\&=kb^{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\\&=kb^{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\\&=kb^{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{aligned}}}$

Perfect digital invariants

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

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

1. Kaprekar 1955.
2. Kaprekar 1980.
3. Hanover 2017, p. 1, Overview.
4. Hanover 2017, p. 3, Methodology.
5. (sequence A099009 in the OEIS )
6. Prichett 1981.
7. Hirata 2005.
8. Iwasaki 2024.
9. For six-digit numbers, i.e. n=6, (1) 6=3×2 and (2) 6=4+2×1. From these solutions (1) x=2 and (2) x=1, we obtain 495 495 and 6174 36, respectively. Applying f to these solutions gives us the numbers 549945 and 631764, that are Kaprekar numbers. In fact, f (549945)=549945, and f (631764)=631764.
10. For even-digits greater than or equal to 8, there are at least two solutions that satisfy equations (2) and (5).
11. For 9 digits, there are at least two solutions: (1) with x=3, and (3) with (x=1, y=0).
12. For 15 digits, there are at least two solutions: (1) with x=5, and (3) with (x=1, y=3). For odd digits 17 or greater, there are two solutions that satisfy equations (3) and (5).
13. The 11-digit number 86420987532 forms a loop with period of 5, and the 13-digit number 8733209876622 forms a loop with period of 2.
14. For three digits, we get 495 from the solution of (1) with x=1. And for four digits, we get 6174 from the solution of (2) with x=0.

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. Cornell University. arXiv: 1710.06308 .
• G. D. Prichett; A. L. Ludington; J. F. Lapenta (1981). "The determination of all decadic Kaprekar constants" (pdf). The Fibonacci Quarterly . 19 (1): 45–52.
• Hirata, Yumi (2005). "The Kaprekar transformation for higher-digit numbers" (pdf). Maebashi Kyoai Gakuen Ronshu (in Japanese). 5: 21–50.
• Iwasaki, Haruo (2024). "A new classification of the Kaprekar Numbers" (pdf). The Fibonacci Quarterly. 62 (4): 275–281.
• D. R. Kaprekar (1955). "An interesting property of the number 6174". Scripta Mathematica. 21: 244–245.
• D. R. Kaprekar (1980–1981). "On Kaprekar numbers". Journal of Recreational Mathematics. 13: 81–82.

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
• Sample (Python) code to walk any four-digit number to Kaprekar's Constant