HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
, Kaprekar's routine is an iterative algorithm that, with each iteration, takes a
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
in a given number base, creates two new numbers by sorting the digits of its number by descending and ascending order, and subtracts the second from the first to yield the natural number for the next iteration. It is named after its inventor, the
India India, officially the Republic of India ( Hindi: ), is a country in South Asia. It is the seventh-largest country by area, the second-most populous country, and the most populous democracy in the world. Bounded by the Indian Ocean on the ...
n
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
D. R. Kaprekar Dattatreya Ramchandra Kaprekar ( mr, दत्तात्रेय रामचंद्र कापरेकर; 17 January 1905 – 1986) was an Indian recreational mathematician who described several classes of natural numbers incl ...
. Kaprekar showed that in the case of four-digit numbers in base 10, if the initial number has at least two distinct digits, after seven iterations this process always yields the number
6174 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 (leading zeros are allowed). # Arrange the digit ...
, which is now known as Kaprekar's constant.


Definition and properties

The algorithm is as follows: # Choose any
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
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 new number \beta by sorting the digits of n in ascending order. These numbers may have leading zeros, which are discarded (or alternatively, retained). 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, and are called Kaprekar's constants.
Zero 0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usu ...
is a Kaprekar's constant for all bases b, and so is called a trivial Kaprekar's constants. All other Kaprekar's constant are nontrivial Kaprekar's constants. For example, in
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
, starting with 3524, : K_(3524) = 5432 - 2345 = 3087 : K_(3087) = 8730 - 378 = 8352 : K_(8352) = 8532 - 2358 = 6174 : K_(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 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
, 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'' = 2''k''

It can be shown that all natural numbers :m = (k) b^ \left(\sum_^ b^i\right) + (k - 1) b^ + (2k - 1) b^ \left(\sum_^ b^i\right) + (k - 1) b \left(\sum_^ b^i\right) + (k) are fixed points of the Kaprekar mapping in even base b = 2k for all natural numbers n.


Kaprekar's constants and cycles of the Kaprekar mapping for specific base ''b''

All numbers are expressed in base b, using A−Z to represent digit values 10 to 35.


Kaprekar's constants in base 10


Numbers of length four digits

In 1949 D. R. Kaprekar discovered that if the above process is applied to
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
numbers of four digits, the resulting sequence will almost always converge to the value
6174 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 (leading zeros are allowed). # Arrange the digit ...
in at most eight iterations, except for a small set of initial numbers which converge instead to 0. The number 6174 is the first Kaprekar's constant to be discovered, and thus is sometimes known as Kaprekar's constant. The set of numbers that converge to zero depends on whether leading zeros are discarded (the usual formulation) or are retained (as in Kaprekar's original formulation). In the usual formulation, there are 77 four-digit numbers that converge to zero, for example 2111. However, in Kaprekar's original formulation the leading zeros are retained, and only repdigits such as 1111 or 2222 map to zero. This contrast is illustrated below: Below is a flowchart. Leading zeros are retained, however the only difference when leading zeros are discarded is that instead of 0999 connecting to 8991, we get 999 connecting to 0.


Numbers of length three digits

If the Kaprekar routine is applied to numbers of three digits in base 10, the resulting sequence will almost always converge to the value 495 in at most six iterations, except for a small set of initial numbers which converge instead to 0. The set of numbers that converge to zero depends on whether leading zeros are discarded (the usual formulation) or are retained (as in Kaprekar's original formulation). In the usual formulation, there are 60 three-digit numbers that converge to zero, for example 211. However, in Kaprekar's original formulation the leading zeros are retained, and only repdigits such as 111 or 222 map to zero. Below is a flowchart. Leading zeros are retained, however the only difference when leading zeros are discarded is that instead of 099 connecting to 891, we get 99 connecting to 0.


Other digit lengths

For digit lengths other than three or four (in base 10), the routine may terminate at one of several fixed points or may enter one of several cycles instead, depending on the starting value of the sequence. See the table in the section above for
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
fixed points and cycles. The number of cycles increases rapidly with larger digit lengths, and all but a small handful of these cycles are of length three. For example, for 20-digit numbers in base 10, there are fourteen constants (cycles of length one) and ninety-six cycles of length greater than one, all but two of which are of length three. Odd digit lengths produce fewer different end results than even digit lengths.


Programming example

The example below implements the Kaprekar mapping described in the definition above to search for Kaprekar's constants and cycles in Python.


Leading zeroes discarded

def get_digits(x, b): digits = [] while x > 0: digits.append(x % b) x = x // b return digits def form_number(digits, b): result = 0 for i in range(0, len(digits)): result = result * b + digits return result def kaprekar_map(x, b): descending = form_number(sorted(get_digits(x, b), reverse=True), b) ascending = form_number(sorted(get_digits(x, b)), b) return descending - ascending def kaprekar_cycle(x, b): x = int (str(x), b) seen = [] while x not in seen: seen.append(x) x = kaprekar_map(x, b) cycle = [] while x not in cycle: cycle.append(x) x = kaprekar_map(x, b) return cycle


Leading zeroes retained

def digit_count(x, b): count = 0 while x > 0: count = count + 1 x = x // b return count def get_digits(x, b, init_k): k = digit_count(x, b) digits = [] while x > 0: digits.append(x % b) x = x // b for i in range(k, init_k): digits.append(0) return digits def form_number(digits, b): result = 0 for i in range(0, len(digits)): result = result * b + digits return result def kaprekar_map(x, b, init_k): descending = form_number(sorted(get_digits(x, b, init_k), reverse=True), b) ascending = form_number(sorted(get_digits(x, b, init_k)), b) return descending - ascending def kaprekar_cycle(x, b): x = int (str(x), b) init_k = digit_count(x, b) seen = [] while x not in seen: seen.append(x) x = kaprekar_map(x, b, init_k) cycle = [] while x not in cycle: cycle.append(x) x = kaprekar_map(x, b, init_k) return cycle


See also

*
Arithmetic dynamics Arithmetic dynamics is a field that amalgamates two areas of mathematics, dynamical systems and number theory. Classically, discrete dynamics refers to the study of the iteration of self-maps of the complex plane or real line. Arithmetic dynamics is ...
* Dudeney number * Factorion *
Happy number In number theory, a happy number is a number which eventually reaches 1 when replaced by the sum of the square of each digit. For instance, 13 is a happy number because 1^2+3^2=10, and 1^2+0^2=1. On the other hand, 4 is not a happy number because ...
*
Kaprekar number In mathematics, a natural number in a given number base is a p-Kaprekar number if the representation of its square in that base can be split into two parts, where the second part has p digits, that add up to the original number. The numbers are ...
* Meertens number * Narcissistic number * Perfect digit-to-digit invariant * Perfect digital invariant * Sum-product number *
Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is importan ...


Citations


References

*


External links

*
Working link to YouTube

Sample (Perl) code to walk any four-digit number to Kaprekar's Constant
{{Classes of natural numbers Arithmetic dynamics Base-dependent integer sequences Sorting algorithms