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:
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.
The algorithm is as follows: [2]
The sequence is called a Kaprekar sequence and the function 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 , and so is called a trivial Kaprekar's constant. All other Kaprekar's constant are nontrivial Kaprekar's constants.
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 (other than possibly the first) 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 (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.
It can be shown that all natural numbers
are fixed points of the Kaprekar mapping in even base for all natural numbers .
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, 8887FFFF7778... |
9 | 18 | 8H9, 98HH89, 998HHH889, 9998HHHH8889... |
All numbers are expressed in base , using A−Z to represent digit values 10 to 35.
Base | Digit length | Nontrivial (nonzero) Kaprekar's constants | Cycles |
---|---|---|---|
2 | 2 | 01 [note 1] | |
3 | 011 [note 1] | ||
4 | 0111, [note 1] 1001 | ||
5 | 01111, [note 1] 10101 | ||
6 | 011111, [note 1] 101101, 110001 | ||
7 | 0111111, [note 1] 1011101, 1101001 | ||
8 | 01111111, [note 1] 10111101, 11011001, 11100001 | ||
9 | 011111111, [note 1] 101111101, 110111001, 111010001 | ||
3 | 2 | ||
3 | 022 → 121 → 022 [note 1] | ||
4 | 1012 → 1221 → 1012 | ||
5 | 20211 | ||
6 | 102212 → 210111 → 122221 → 102212 | ||
7 | 2202101 | 2022211 → 2102111 → 2022211 | |
8 | 21022111 | ||
9 | 222021001 | 220222101 → 221021101 → 220222101 202222211 → 210222111 → 211021111 → 202222211 | |
4 | 2 | 03 → 21 → 03 [note 1] | |
3 | 132 | ||
4 | 3021 | 1332 → 2022 → 1332 | |
5 | 20322 → 23331 → 20322 | ||
6 | 213312, 310221, 330201 | ||
7 | 3203211 | ||
8 | 31102221, 33102201, 33302001 | 22033212 → 31333311 → 22133112 → 22033212 | |
9 | 221333112, 321032211, 332032101 | ||
5 | 2 | 13 | |
3 | 143 → 242 → 143 | ||
4 | 3032 | ||
6 | 2 | 05 → 41 → 23 → 05 [note 1] | |
3 | 253 | ||
4 | 1554 → 4042 → 4132 → 3043 → 3552 → 3133 → 1554 | ||
5 | 41532 | 31533 → 35552 → 31533 | |
6 | 325523, 420432, 530421 | 205544 → 525521 → 432222 → 205544 | |
7 | 4405412 → 5315321 → 4405412 | ||
8 | 43155322, 55304201 | 31104443 → 43255222 → 33204323 → 41055442 → 54155311 → 44404112 → 43313222 → 31104443 42104432 → 43204322 → 42104432 53104421 → 53304221 → 53104421 | |
7 | 2 | ||
3 | 264 → 363 → 264 | ||
4 | 3054 → 5052 → 5232 → 3054 | ||
8 | 2 | 25 | 07 → 61 → 43 → 07 [note 1] |
3 | 374 | ||
4 | 1776 → 6062 → 6332 → 3774 → 4244 → 1776 3065 → 6152 → 5243 → 3065 | ||
5 | 42744 → 47773 → 42744 51753 → 61752 → 63732 → 52743 → 51753 | ||
6 | 437734, 640632 | 310665 → 651522 → 532443 → 310665 | |
9 | 2 | 17 → 53 → 17 | |
3 | 385 → 484 → 385 | ||
4 | 3076 → 7252 → 5254 → 3076 5074 → 7072 → 7432 → 5074 | ||
10 [4] | 2 | 09 → 81 → 63 → 27 → 45 → 09 [note 1] | |
3 | 495 | ||
4 | 6174 | ||
5 | 53955 → 59994 → 53955 61974 → 82962 → 75933 → 63954 → 61974 62964 → 71973 → 83952 → 74943 → 62964 | ||
6 | 549945, 631764 | 420876 → 851742 → 750843 → 840852 → 860832 → 862632 → 642654 → 420876 | |
7 | 7509843 → 9529641 → 8719722 → 8649432 → 7519743 → 8429652 → 7619733 → 8439552 → 7509843 | ||
8 | 63317664, 97508421 | 43208766 → 85317642 → 75308643 → 84308652 → 86308632 → 86326632 → 64326654 → 43208766 64308654 → 83208762 → 86526432 → 64308654 | |
9 | 554999445, 864197532 | 865296432 → 763197633 → 844296552 → 762098733 → 964395531 → 863098632 → 965296431 → 873197622 → 865395432 →753098643 → 954197541 → 883098612 → 976494321 → 874197522 → 865296432 | |
10 | 6333176664, 9753086421, 9975084201 | 8655264432 → 6431088654 → 8732087622 → 8655264432 8653266432 → 6433086654 → 8332087662 → 8653266432 8765264322 → 6543086544 → 8321088762 → 8765264322 8633086632 → 8633266632 → 6433266654 → 4332087666 → 8533176642 → 7533086643 → 8433086652 → 8633086632 9775084221 → 9755084421 → 9751088421 → 9775084221 | |
11 | 2 | 37 | |
3 | 4A6 → 5A5 → 4A6 | ||
4 | 3098 → 9452 → 7094 → 9272 → 7454 → 3098 5096 → 9092 → 9632 → 7274 → 5276 → 5096 | ||
12 | 2 | 0B → A1 → 83 → 47 → 29 → 65 → 0B [note 1] | |
3 | 5B6 | ||
4 | 3BB8 → 8284 → 6376 → 3BB8 4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198 | ||
5 | 83B74 | 64B66 → 6BBB5 → 64B66 | |
6 | 65BB56 | 420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98 | |
7 | 962B853 | 841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974 | |
8 | 873BB744, A850A632 | 4210AA98 → A9737422 → 87428744 → 64328876 → 652BB866 → 961BB953 → A8428732 → 86528654 → 6410AA76 → A92BB822 → 9980A323 → A7646542 → 8320A984 → A7537642 → 8430A874 → A5428762 → 8630A854 → A540X762 → A830A832 → A8546632 → 8520A964 → A740A742 → A8328832 → 86546654 | |
13 | 2 | 1B → 93 → 57 → 1B | |
3 | 5C7 → 6C6 → 5C7 | ||
14 | 2 | 49 | 2B → 85 → 2B 0D → C1 → A3 → 67 → 0D [note 1] |
3 | 6D7 | ||
15 | 2 | ||
3 | 6E8 → 7E7 → 6E8 | ||
16 [5] | 2 | 2D → A5 → 4B → 69 → 2D 0F → E1 → C3 → 87 → 0F [note 1] | |
3 | 7F8 | ||
4 | 3FFC → C2C4 → A776 → 3FFC A596 → 52CB → A596 E0E2 → EB32 → C774 → 7FF8 → 8688 → 1FFE → E0E2 E952 → C3B4 → 9687 → 30ED → E952 | ||
5 | 86F88 → 8FFF7 → 86F88 A3FB6 → C4FA4 → B7F75 → A3FB6 A4FA6 → B3FB5 → C5F94 → B6F85 → A4FA6 | ||
6 | 87FF78 | 310EED → ED9522 → CB3B44 → 976887 → 310EED 532CCB → A95966 → 532CCB 840EB8 → E6FF82 → D95963 → A42CB6 → A73B86 → 840EB8 A80E76 → E40EB2 → EC6832 → C91D64 → C82C74 → A80E76 C60E94 → E82C72 → CA0E54 → E84A72 → C60E94 | |
7 | C83FB74 | B62FC95 → D74FA83 → C92FC64 → D85F973 → C81FD74 → E94FA62 → DA3FB53 → CA5F954 → B74FA85 → B62FC95 B71FD85 → E83FB72 → DB3FB43 → CA6F854 → B73FB85 → C63FB94 → C84FA74 → B82FC75 → D73FB83 → CA3FB54 → C85F974 → B71FD85 | |
8 | 3110EEED → EDD95222 → CBB3B444 → 97768887 → 3110EEED 5332CCCB → A9959666 → 5332CCCB 7530ECA9 → E951DA62 → DB52CA43 → B974A865 → 7530ECA9 A832CC76 → A940EB66 → E742CB82 → CA70E854 → E850EA72 → EC50EA32 → EC94A632 → C962C964 → A832CC76 C610EE94 → ED82C722 → CBA0E544 → E874A872 → C610EE94 C630EC94 → E982C762 → CA30EC54 → E984A762 → C630EC94 C650EA94 → E852CA72 → CA50EA54 → E854AA72 → C650EA94 CA10EE54 → ED84A722 → CB60E944 → E872C872 → CA10EE54 |
In 1949 D. R. Kaprekar discovered [6] that if the above process is applied to four-digit numbers in base 10, the sequence converges to 6174 within seven iterations or, more rarely, converges to 0. The number 6174 is the first Kaprekar's constant to be discovered, and thus is sometimes known as Kaprekar's constant. [7] [8] [9]
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, [10] 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:
discard leading zeros | retain leading zeros |
---|---|
2111 − 1112 = 999 | 2111 − 1112 = 0999 |
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.
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. [7]
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, [11] 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.
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. [7] See the table in the section above for base 10 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. [12] [13]
The example below implements the Kaprekar mapping described in the definition above to search for Kaprekar's constants and cycles in Python.
importstringfromcollections.abcimportSequence,GeneratorBASE36_DIGITS=f"{string.digits}{string.ascii_uppercase}"defdigit_count(x:int,/,base:int=10)->int:count=0whilex>0:count+=1x//=basereturncountdefget_digits_reversed(x:int,/,base:int=10,init_k:int=0)->Generator[str]:ifinit_k>0:k=digit_count(x,base)whilex>0:yieldBASE36_DIGITS[x%base]x//=baseifinit_k>0:for_inrange(k,init_k):yield"0"defget_digits(x:int,/,base:int=10,init_k:int=0)->str:return"".join(reversed(list(get_digits_reversed(x,base,init_k))))defkaprekar_map(x:int,/,base:int=10,init_k:int=0)->int:digits=list(get_digits_reversed(x,base,init_k))digits.sort()descending=int("".join(reversed(digits)),base)ascending=int("".join(digits),base)returndescending-ascendingdefkaprekar_cycle(x:int|str|bytes|bytearray,/,base:int=10)->list[int|str]:""" Return Kaprekar's cycles as list >>> kaprekar_cycle(8119) [6174] >>> kaprekar_cycle('09') [9, 81, 63, 27, 45] >>> kaprekar_cycle('0F', 16) ['0F', 'E1', 'C3', '87'] >>> kaprekar_cycle('B71FD85', 16) ['B71FD85', 'E83FB72', 'DB3FB43', 'CA6F854', 'B73FB85', 'C63FB94', 'C84FA74', 'B82FC75', 'D73FB83', 'CA3FB54', 'C85F974'] """leading_zeroes_retained=notisinstance(x,int)init_k=len(x)ifleading_zeroes_retainedelse0x=int(x)ifbase==10elseint(x,base)seen=[]whilexnotinseen:seen.append(x)x=kaprekar_map(x,base,init_k)cycle=[]whilexnotincycle:cycle.append(x)x=kaprekar_map(x,base,init_k)returncycleifbase==10else[get_digits(x,base,init_k)forxincycle]if__name__=="__main__":importdoctestdoctest.testmod()
In mathematics, the Euler–Maclaurin formula is a formula for the difference between an integral and a closely related sum. It can be used to approximate integrals by finite sums, or conversely to evaluate finite sums and infinite series using integrals and the machinery of calculus. For example, many asymptotic expansions are derived from the formula, and Faulhaber's formula for the sum of powers is an immediate consequence.
The natural logarithm of a number is its logarithm to the base of the mathematical constant e, which is an irrational and transcendental number approximately equal to 2.718281828459. The natural logarithm of x is generally written as ln x, logex, or sometimes, if the base e is implicit, simply log x. Parentheses are sometimes added for clarity, giving ln(x), loge(x), or log(x). This is done particularly when the argument to the logarithm is not a single symbol, so as to prevent ambiguity.
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter ζ (zeta), is a mathematical function of a complex variable defined as
In mathematics, the Euler numbers are a sequence En of integers defined by the Taylor series expansion
In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.
In mathematics, the Bernoulli polynomials, named after Jacob Bernoulli, combine the Bernoulli numbers and binomial coefficients. They are used for series expansion of functions, and with the Euler–MacLaurin formula.
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.
A hexagonal number is a figurate number. The nth hexagonal number hn is the number of distinct dots in a pattern of dots consisting of the outlines of regular hexagons with sides up to n dots, when the hexagons are overlaid so that they share one vertex.
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,
In mathematics, a harshad number in a given number base is an integer that is divisible by the sum of its digits when written in that base. Harshad numbers in base n are also known as n-harshad numbers. Harshad numbers were defined by D. R. Kaprekar, a mathematician from India. The word "harshad" comes from the Sanskrit harṣa (joy) + da (give), meaning joy-giver. The term "Niven number" arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977.
A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.
In mathematics, the Leibniz formula for π, named after Gottfried Wilhelm Leibniz, states that
In number theory, a Dudeney number in a given number base is a natural number equal to the perfect cube of another natural number such that the digit sum of the first natural number is equal to the second. The name derives from Henry Dudeney, who noted the existence of these numbers in one of his puzzles, Root Extraction, where a professor in retirement at Colney Hatch postulates this as a general method for root extraction.
In number theory, a narcissistic number in a given number base is a number that is the sum of its own digits each raised to the power of the number of digits.
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 number theory, a factorion in a given number base is a natural number that equals the sum of the factorials of its digits. The name factorion was coined by the author Clifford A. Pickover.
In number theory, a perfect digit-to-digit invariant is a natural number in a given number base that is equal to the sum of its digits each raised to the power of itself. An example in base 10 is 3435, because . The term "Munchausen number" was coined by Dutch mathematician and software engineer Daan van Berkel in 2009, as this evokes the story of Baron Munchausen raising himself up by his own ponytail because each digit is raised to the power of itself.
The decimal value of the natural logarithm of 2 is approximately
In number theory, a perfect digital invariant (PDI) is a number in a given number base () that is the sum of its own digits each raised to a given power ().