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 four-digit random 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:
6174, known as Kaprekar’s constant, is a fixed point of this algorithm. Any four-digit number 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:- Choose any four-digit natural number in a given number base. This is the first number of the sequence.
- 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.
- Repeat step 2.
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 is a multiple of.
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 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 are fixed points of the Kaprekar mapping.
Determination of Kaprekar numbers
In the following, "Kaprekar’s constant " refers to a number that becomes a positive fixed point as a result of Kaprekar’s routine.In 1981, G. D. Prichett, et al. showed that the Kaprekar’s constants are limited to two numbers, 495 and 6174. 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.
In 2024, Haruo Iwasaki of the Ranzan Mathematics Study Group 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, 875421 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 is considered as a constant, then the number of decimal -digit Kaprekar numbers is determined by two types of equations:
or by three types of Diophantine equations:
It was found that the number of integer solutions of the equations that can be established is the same as the number of solutions that express all of the -digit Kaprekar numbers.
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 through. For six-digit numbers, there are two solutions that satisfy equations and. Furthermore, it is clear that even-digits with greater than or equal to 8, and with 9 digits, or odd-digits with greater than or equal to 15 digits 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. Hence, Prichett’s result that the Kaprekar’s constants are limited to 495 and 6174 is verified.
Therefore, the problem of determining all of the Kaprekar’s constants and the number of these was solved. An example below will explain the Iwasaki’s result.
Example: In the case where decimal digits, since is an odd number and is not a multiple of 3, the equations and do not hold, and the only equations that can hold are, and. And if the operation defined above is applied once to the numbers corresponding to the solutions of these equations, seven Kaprekar numbers can be obtained.
The solution to is
The solution to is
The solutions to are
Families of Kaprekar’s constants
In case where even base (''b'' = 2''k'')
It can be shown that all natural numbersare fixed points of the Kaprekar mapping in even base for all natural numbers.