Kaprekar's routine

Last updated September 25, 2024

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.

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.

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 )

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In probability theory and statistics, the exponential distribution or negative exponential distribution is the probability distribution of the distance between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate; the distance parameter could be any meaningful mono-dimensional measure of the process, such as time between production errors, or length along a roll of fabric in the weaving manufacturing process. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless. In addition to being used for the analysis of Poisson point processes it is found in various other contexts.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence.

In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals $32$ and can be written as $3 \times 3$ .

In mathematics, a natural number in a given number base is a $- Kaprekar number if the representation of its square in that base can be split into two parts, where the second part has digits, that add up to the original number. For example, in base 10, 45 is a 2-Kaprekar number, because 45² = 2025, and 20 + 25 = 45. The numbers are named after D. R. Kaprekar.$

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

<span class="mw-page-title-main">D. R. Kaprekar</span> Indian recreational mathematician (1905–1986)

Dattatreya Ramchandra Kaprekar was an Indian recreational mathematician who described several classes of natural numbers including the Kaprekar, harshad and self numbers and discovered the Kaprekar's constant, named after him. Despite having no formal postgraduate training and working as a schoolteacher, he published extensively and became well known in recreational mathematics circles.

In mathematics, the Dirichlet beta function is a special function, closely related to the Riemann zeta function. It is a particular Dirichlet L-function, the L-function for the alternating character of period four.

The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers $such that$

A sum-product number in a given number base $is a natural number that is equal to the product of the sum of its digits and the product of its digits.$

In mathematics, the Bessel polynomials are an orthogonal sequence of polynomials. There are a number of different but closely related definitions. The definition favored by mathematicians is given by the series

In number theory and mathematical logic, a Meertens number in a given number base $is a natural number that is its own Gödel number. It was named after Lambert Meertens by Richard S. Bird as a present during the celebration of his 25 years at the CWI, Amsterdam.$

In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation $x 3 = x + 1$ . The Perrin numbers bear the same relationship to the Padovan sequence as the Lucas numbers do to the Fibonacci sequence.

The number 6174 is known as Kaprekar's constant after the Indian mathematician D. R. Kaprekar. This number is renowned for the following rule:

Take any four-digit number, using at least two different digits.
Arrange the digits in descending and then in ascending order to get two four-digit numbers, adding leading zeros if necessary.
Subtract the smaller number from the bigger number.
Go back to step 2 and repeat.

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

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 .

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

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

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

[1]

[2]

[3]