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]

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

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

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

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

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

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

In the following, we will refer to the fixed points of the Kaprekar Routine not as “Kaprekar's constants” but as “Kaprekar numbers of definition 2”. In addition, the term “Kaprekar's constant α” refers to the case where the number of digits of a number is reduced to 0 or α by the Kaprekar Routine.

In 2005, Y.Hirata calculated all fixed points up to 31 digits and examined their distribution.

In 1981, Pritchett, et al. showed that the Kaprekar constant is limited to two numbers, 495 (3 digits) and 6174 (4 digits). They also classified the Kaprekar numbers into four types, but there was some overlap in this classification.

In 2024, Haruo Iwasaki 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 sets composed of combinations of the seven numbers 495, 6174, 36, 123456789, 27, 124578, and 09, and that this new classification using the five sets includes a correction to the classification by Pritchett, et al.

As a result, the number of n-digit Kaprekar numbers is determined by two types of equations

n=3x (x≥1), n=4+2x (x≥0)

or three types of Diophantene equations

n=9x+2y (x≥1, y≥0),

n=9x+14y (x≥1, y≥1),

n=6x+2y+9z+2u (x≥1, y≥1, z≥0, u≥0)

It was found that the number of integer solutions 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. In addition, there are no Kaprekar numbers for 5-digit and 7-digit numbers because they do not satisfy the above equations. Furthermore, it is clear that even numbers with more than 8 digits, and odd numbers with more than 9 or 15 digits have more than one solution. Although 11-digit and 13-digit numbers have only one solution, these numbers have loop 5 and loop 2 numbers respectively, so Pritchett's result that the “Kapekar's constant” is limited to 495 (3 digits) and 6174 (4 digits) is again verified. In this way, the problem of determining all of the Kaprekar numbers defined in Definition 2 (i.e. fixed points of the Kaprekar transformations) and the number of these was solved.

Following this paper, we will give one example.

Example: In the case of n=23, since n is an odd number that is not a multiple of 3, the number of equations that can be solved is limited to the following three, and if the operation (denoted by f) defined above is applied once to the numbers corresponding to the solutions of these equations, seven Kaprekar numbers can be obtained.

The solution to 23=9x+2y is (x , y)=(1 , 7)

f(123456789 33333336666666)= 86433333331976666666532

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

f(123456789 36 449955 222777)= 87765443219997765543222

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

(x, y , z , u) = (1 , 4 , 1 , 0)

f(124578 00009999 123456789)= 99998765420987543210001

(x , y , z , u) = (1 , 3 , 1 , 1)

f(124578 000999 123456789 36)=99987654320987654321001

(x , y , z , u) = (1 ,2 , 1 , 2)

f(124578 0099 123456789 3366)=99876543320987665432101

(x, y, z, u) = (1, 1, 1, 3)

f(124578 09 123456789 333666) = 98765433320987666543211

(x, y, z, u) = (2, 1, 1, 0)

f(112244557788 09 123456789) = 98776554210988754432211

b = 2k

It can be shown that all natural numbers

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 = 2 k$ for all natural numbers $n$ .

Proof

$\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)$

$\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)$

${\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...$

Citations

^ Hanover 2017, p. 1, Overview.
^ Hanover 2017, p. 3, Methodology.
^ (sequence A099009 in the OEIS)

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.

G. D. Prichett, A. L. Ludington, and J. F. Lapenta, The determination of all decadic Kaprekar constants, The Fibonacci Quaterly, 19.1 (1981), 45–52. Y. Hirata, The Kaprekar transformation for higher-digit numbers, Maebashi Kyoai Gakuen Ronshu, 5 (2005), 21–50. H.Iwasaki “A new classification of the Kaprekar Numbers”. The Fibonacci Quarterly. (2024-11).

^

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

[FOOTNOTEHanover20171Overview-1] Hanover 2017, p. 1, Overview.

[FOOTNOTEHanover20173Methodology-2] Hanover 2017, p. 3, Methodology.

[A099009-3] (sequence A099009 in the OEIS)

[1]

[2]

[3]