Misplaced Pages

Kaprekar's routine

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Kaprekar's constant) Iterative algorithm

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 n {\displaystyle n} in a given number base b {\displaystyle b} . This is the first number of the sequence.
  2. Create a new number α {\displaystyle \alpha } by sorting the digits of n {\displaystyle n} in descending order, and another number β {\displaystyle \beta } by sorting the digits of n {\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 K b ( n ) = α β {\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 b {\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,

K 10 ( 3524 ) = 5432 2345 = 3087 {\displaystyle K_{10}(3524)=5432-2345=3087}
K 10 ( 3087 ) = 8730 378 = 8352 {\displaystyle K_{10}(3087)=8730-378=8352}
K 10 ( 8352 ) = 8532 2358 = 6174 {\displaystyle K_{10}(8352)=8532-2358=6174}
K 10 ( 6174 ) = 7641 1467 = 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 b 1 {\displaystyle b-1} . Therefore, each number in a Kaprekar sequence of base b {\displaystyle b} numbers (other than possibly the first) is a multiple of b 1 {\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

m = ( k ) b 2 n + 3 ( i = 0 n 1 b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b ( i = 0 n 1 b i ) + ( k ) {\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

α = ( 2 k 1 ) b 2 n + 2 ( i = 0 n b i ) + ( k ) b n + 1 ( i = 0 n b i ) + ( k 1 ) ( i = 0 n b i ) {\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)}

β = ( k 1 ) b 2 n + 2 ( i = 0 n b i ) + ( k ) b n + 1 ( i = 0 n b i ) + ( 2 k 1 ) ( i = 0 n b i ) {\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)}

K b ( m ) = α β = ( ( 2 k 1 ) ( k 1 ) ) b 2 n + 2 ( i = 0 n b i ) + ( k k ) b n + 1 ( i = 0 n b i ) + ( ( k 1 ) ( 2 k 1 ) ) ( i = 0 n b i ) = k b 2 n + 2 ( i = 0 n b i ) k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + b 2 n + 2 k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k ) b 2 n + 1 k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b 2 n + 1 + b 2 n + 1 k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b 2 n + 1 1 ( i = 0 1 b i ) + b 2 n + 1 1 k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b 2 n + 1 n ( i = 0 n b i ) + b 2 n + 1 n k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + b n + 1 k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( 2 k ) b n k ( i = 0 n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + k b n k ( i = 0 n 1 b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b n + 1 1 + b n + 1 1 k ( i = 0 n n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b n + 1 n ( i = 0 n b i ) + b n + 1 n k ( i = 0 n n b i ) = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b ( i = 0 n b i ) + b k = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b ( i = 0 n b i ) + 2 k k = k b 2 n + 3 ( i = 0 n b i ) + ( k 1 ) b 2 n + 2 + ( 2 k 1 ) b n + 1 ( i = 0 n b i ) + ( k 1 ) b ( i = 0 n b i ) + k = m {\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

Citations

  1. Hanover 2017, p. 1, Overview.
  2. Hanover 2017, p. 3, Methodology.
  3. (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.

External links

Classes of natural numbers
Powers and related numbers
Of the form a × 2 ± 1
Other polynomial numbers
Recursively defined numbers
Possessing a specific set of other numbers
Expressible via specific sums
Figurate numbers
2-dimensional
centered
non-centered
3-dimensional
centered
non-centered
pyramidal
4-dimensional
non-centered
Combinatorial numbers
Primes
Pseudoprimes
Arithmetic functions and dynamics
Divisor functions
Prime omega functions
Euler's totient function
Aliquot sequences
Primorial
Other prime factor or divisor related numbers
Numeral system-dependent numbers
Arithmetic functions
and dynamics
Digit sum
Digit product
Coding-related
Other
P-adic numbers-related
Digit-composition related
Digit-permutation related
Divisor-related
Other
Binary numbers
Generated via a sieve
Sorting related
Natural language related
Graphemics related
Categories: