Fact-checked by Grok 2 weeks ago

Kaprekar's routine

Kaprekar's routine is an iterative algorithm in , discovered by the Dattatreya Ramachandra Kaprekar in 1949, whereby one selects a multi-digit number (typically four digits, excluding those with all identical digits), rearranges its digits to form the largest and smallest possible numbers, subtracts the latter from the former to obtain a new number, and repeats the process. For any four-digit starting number with at least two distinct digits, the routine converges to the fixed point —known as Kaprekar's constant—in at most seven iterations, after which further applications yield repeatedly, as 7641 - 1467 = 6174. The routine highlights intriguing properties of permutations and in base 10, serving as a solitaire or puzzle that demonstrates deterministic despite the apparent of digit rearrangements. Numbers with all identical digits (repdigits, such as 1111) result in zero after one and remain there, while the process pads the ascending arrangement with leading zeros if necessary to maintain the digit length. Kaprekar initially described it as "another solitaire ," emphasizing its playful yet profound mathematical structure. Generalizations of the routine extend to other digit lengths and bases, revealing multiple constants or cycles; for instance, three-digit numbers converge to 495 in at most six steps, while five-digit numbers may enter cycles, such as the one involving 53955 and 59994. These extensions have inspired further research into fixed points, iteration counts, and periodic behaviors, with applications in and . The maximum iteration count for four digits is seven, achieved by 2,184 starting numbers, underscoring the routine's efficiency and universality within its constraints.

Overview

Definition

Kaprekar's routine is an iterative applied to an n-digit number in base b, where n ≥ 2 and b ≥ 2. The process begins by rearranging the digits of the input number to form the largest possible n-digit number α, obtained by the digits in descending order, and the smallest possible n-digit number β, obtained by the digits in ascending order while allowing leading zeros in β to maintain n digits. The next number in the sequence is then computed as the difference d = α - β, which is padded with leading zeros if necessary to ensure it has exactly n digits before the next iteration. This step is repeated indefinitely. The core of the routine is encapsulated in the Kaprekar mapping K_b: S \to S, where S is the set of n-digit numbers in base b (including those with leading zeros), defined as K_b(m) = \alpha - \beta, with α and β formed as described from the digits of m. For the routine to produce non-trivial behavior, the starting number must have at least two distinct digits; otherwise, if all digits are identical (a ), then α = β, resulting in d = 0, which is a fixed point. In the special case of single-digit numbers (n=1), the routine yields 0 in one iteration, since α = β and their difference is 0 (padded to one digit), making 0 a fixed point. Iterating the routine typically leads to a , which is a fixed point of the where K_b(c) = c.

Historical Background

Kaprekar's routine was discovered in 1949 by Dattatreya Ramchandra Kaprekar, an Indian mathematician from Devlali, who devised the iterative process of rearranging digits in descending and ascending order and subtracting the results, initially applying it to four-digit numbers and noting convergence to 6174. He detailed this observation in his paper "Another Solitaire Game," published in Scripta Mathematica, volume 15, pages 244–245. Kaprekar's work stemmed from his broader interest in and digit-based operations, though his lack of formal postgraduate training limited its immediate international visibility. Early analyses built on Kaprekar's foundation in the mid-20th century, with Kaprekar himself extending explorations in the and through additional publications, such as "An Interesting Property of the Number " in Scripta Mathematica, volume 21, page 304 (1955), which further examined the routine's behavior. Due to its publication in niche journals and Kaprekar's context, the routine received limited documentation and attention outside initially. It gained broader recognition in the through Martin Gardner's 1975 article in , which highlighted its recreational appeal. Subsequent studies advanced the understanding of the routine's cycles and generalizations. In 1981, A. L. Prichett, J. F. Ludington, and J. F. Lapenta published "The Determination of All Decadic Kaprekar Constants" in The Fibonacci Quarterly, volume 19, number 1, pages 45–52, systematically identifying all base-10 Kaprekar constants and analyzing associated cycles. Building on this, Yumi Hirata's 2005 computational study, "The Kaprekar Transformation for Higher-Digit Numbers," in the Kyoai Gakuen University Journal, generalized the routine to up to 31 digits, enumerating fixed points and loops to explore its behavior beyond four digits. Recent developments include Haruo Iwasaki's 2024 paper "A New Classification of the Kaprekar Numbers" in The Fibonacci Quarterly, volume 62, number 4, which categorizes all nonzero decimal Kaprekar numbers into five distinct sets based on their structural properties under the transformation, notably distinguishing constants like 495 (for three digits) and 6174 (for four digits) within these sets. Throughout its history, the routine has remained primarily a topic of recreational mathematics and number theory puzzles, with no documented applications in fields such as cryptography.

The Process in Base 10

For Three-Digit Numbers

Kaprekar's routine applied to three-digit numbers in base 10 begins with any from 100 to 999. The digits are rearranged to form the largest possible number α by placing them in descending order and the smallest possible number β by placing them in ascending order, padding β with leading zeros if necessary to maintain three digits. The difference α - β is computed, resulting in a new three-digit number (again padded with leading zeros if under 100), and the process is repeated. Consider the starting number 123 as an illustrative example. The digits are 1, 2, 3, so α = 321 and β = 123, yielding 321 - 123 = 198. Next, for 198: α = 981, β = 189, difference 981 - 189 = 792. For 792: α = 972, β = 279, difference 972 - 279 = 693. For 693: α = 963, β = 369, difference 963 - 369 = 594. For 594: α = 954, β = 459, difference 954 - 459 = 495. Applying the routine to 495 gives α = 954, β = 459, difference 954 - 459 = 495, establishing it as a fixed point. All three-digit numbers except the nine repdigits (111, 222, ..., 999) converge to the fixed point 495 under this routine, requiring at most six iterations. This convergence holds because the operation systematically reduces the possibilities until reaching the cycle at 495, as verified through exhaustive computation of the 891 applicable starting numbers. Repdigit three-digit numbers map directly to 0 in one step, since α = β, yielding a trivial fixed point of 0 that remains unchanged thereafter.

For Four-Digit Numbers

Kaprekar's routine applied to four-digit numbers in base 10 involves selecting an between and 9999 that is not a , where all digits are identical. The digits are rearranged to form the largest possible four-digit number α and the smallest possible four-digit number β, padding β with leading zeros if necessary to maintain four digits. The difference α - β is then computed, resulting in another four-digit number (or fewer, but treated as four digits with leading zeros), and is repeated. A representative example begins with the number 8991. Arranging the digits descending gives 9981 and ascending gives 1899, so 9981 - 1899 = 8082. Next, 8820 - 0288 = 8532. Then, 8532 - 2358 = . Applying the routine to yields 7641 - 1467 = , establishing it as a fixed point. This sequence reaches the fixed point in four iterations, though the maximum number of steps required for any valid starting number is seven. The number serves as the unique non-trivial Kaprekar constant for four-digit numbers; every valid starting number converges to it under repeated application of the routine. This property was first identified by in his 1955 publication. In the trivial case, repdigit numbers such as or 9999 yield a difference of after one iteration, and subsequent applications remain at .

For Other Numbers of Digits

For one-digit numbers in base 10, the Kaprekar routine is trivial, as the largest and smallest arrangements of the single are identical, yielding a difference of on the first . This fixed point at requires no further iterations, and all such numbers converge immediately without nontrivial behavior. For two-digit numbers, the routine typically enters a of length 5 when with leading zeros to maintain two digits, unless the starting number has identical digits, in which case it reaches immediately. Starting with distinct digits, such as 21, the process yields 21 - 12 = 9 (padded as 09), then 90 - 09 = 81, 81 - 18 = 63, 63 - 36 = 27, 72 - 27 = , and 54 - 45 = 09, repeating the 09 ↔ 81 ↔ 63 ↔ 27 ↔ . All differences in this process are multiples of 9, reflecting the routine's preservation of digital roots modulo 9. There is no nontrivial fixed point, and the represents the for numbers with distinct digits. For five-digit numbers, the routine does not converge to a unique constant like in the three- or four-digit cases; instead, numbers may reach 0 (for repunits or multiples leading to all identical digits) or enter one of three distinct s: two of length 4 and one of length 2, consisting of 10 distinct five-digit numbers in total. For example, starting from 12345 leads to iterations eventually entering the 63954 → 61974 → 82962 → 75933 → 63954 (length 4), while others, such as 24680, enter 74943 → 62964 → 71973 → 83952 → 74943 (length 4). Another is 53955 ↔ 59994 (length 2). There are no fixed points beyond . For six or more digits, the behavior grows more complex, with multiple fixed points and cycles serving as attractors rather than a single constant, and is not always to a fixed point. In six digits, there are two known fixed points—549945 and 631764—alongside several cycles. For seven digits, no fixed points exist, and outcomes include cycles or ; beyond that, the number of cycles increases with digit length, often exceeding dozens for 10+ digits, though all iterations remain bounded within the d-digit space. This multiplicity highlights the routine's tendency toward cyclic attractors for d > 4, contrasting with the unique in fewer digits.

Kaprekar Constants and Numbers

Definition and Properties

A Kaprekar constant in base b is defined as a fixed point of , denoted K_b(c) = c, where the routine involves rearranging the digits of a number to form the largest and smallest possible values and subtracting the latter from the former. A is any number that appears in the iterative sequence generated by the routine starting from an initial value and leading to a Kaprekar constant. Key properties of Kaprekar constants include their self-reproducing nature under the digit rearrangement subtraction process, meaning applying the routine yields the constant itself. In base 10, notable examples are 495 for three-digit numbers and for four-digit numbers, both of which satisfy K_{10}(c) = c. Additionally, all outputs of the routine, including Kaprekar constants, are multiples of b-1; in base 10, this means they are multiples of 9. In 2024, Haruo Iwasaki provided a comprehensive of in base 10, identifying five mutually based on digit patterns and behavior under the routine. Set T1 consists of numbers like 495, characterized by repeated applications yielding patterns with least digit 4 and maximum digit 9. Set T2 includes numbers like , with least digit 1 and maximum digit 7. The remaining sets (T3, T4, T5) involve more complex combinations of digit sequences, such as ascending patterns from 1 to 9 or insertions of zeros, with least digits of 1 or 0 and maximum of 9; a nonzero n-digit number (n ≥ 3) is a if and only if it belongs to one of these sets. Regarding uniqueness in base 10, non-trivial Kaprekar constants—those attracting sequences from most starting numbers—exist only for three-digit and four-digit cases, with 495 and as the sole such constants, respectively; for other digit lengths, no single non-trivial constant emerges.

Determination Methods

The primary method for determining Kaprekar constants and numbers involves computational of the routine across all possible n-digit numbers in base b, identifying fixed points where the operation yields the number itself and attractors where sequences converge. This brute-force approach models the process as a , with nodes representing numbers and edges indicating the result of one iteration, allowing detection of cycles and fixed points by exhaustively computing paths until stabilization. For small n, such as 3 or 4 digits, programs efficiently track these by representing numbers in reduced forms to avoid leading zeros and minimizing sorting operations during . This method has confirmed unique constants like 495 for 3-digit numbers and for 4-digit numbers in base 10, and extended results to other bases, such as a unique 7-digit constant in base 4 (3203211). Theoretical approaches leverage and properties to narrow the search space. In base b, the always produces a result divisible by (b-1), as the difference between rearrangements preserves modulo (b-1) due to the identical s of the ascending and descending forms. In base 10, this implies all subsequent iterates (and thus constants and numbers) are multiples of 9, enabling searches to focus exclusively on such candidates, which reduces computational load significantly for larger n. These properties stem from of the , confirming that fixed points must satisfy specific divisibility conditions. A recent theoretical framework, proposed by Haruo Iwasaki in , classifies all Kaprekar numbers for n ≥ 3 digits in base 10 by partitioning them into five (T₁ through T₅) based on their iterative behavior under the transformation and inherent digit symmetries. Each set is defined by patterns derived from known constants like 495 and , combined with repeating digit blocks (e.g., T₁ involves repetitions of 495, while T₄ incorporates mixtures of 123456789, 36, 495, and 27), solved via Diophantine equations to generate explicit forms. This method provides a complete, non-computational without , confirming that only 495 and are Kaprekar constants while identifying all numbers that map to themselves. For enumeration and verification, the (OEIS) serves as a key resource, with sequence A099009 listing fixed points of the Kaprekar mapping across digit lengths and providing patterns like divisibility by 9 for all terms.

Generalizations to Other Bases

Kaprekar Constants in Arbitrary Bases

Kaprekar's routine generalizes naturally to any integer b > 1, where the "digits" are symbols representing values from 0 to b-1. For an n-digit number in b, the process rearranges these digits to form the largest possible number (descending order) and the smallest possible number (ascending order, allowing leading zeros), subtracts the smaller from the larger to obtain a new n-digit number (padding with leading zeros if needed), and repeats the operation. This iteration typically converges to a fixed point or a short after a finite number of steps. In arbitrary bases, such fixed points or cycles are termed Kaprekar constants, provided they are non-trivial (i.e., not all s identical or zero). For any fixed b and digit length n, only finitely many Kaprekar constants exist, as established by analysis of the routine's behavior. Non-trivial constants appear prominently for n = 3 and n = 4 in many bases, analogous to the base-10 cases of 495 and 6174. For the 3-digit case in even bases b = 2k with k \geq 2, an explicit non-trivial Kaprekar constant exists with digits (k-1, b-1, k). In base 6 (k = 3), this yields 253_6, which satisfies the fixed-point property: rearranging its digits gives descending 532_6 and ascending 235_6, and their difference is again 253_6. Similarly, in base 10 (k = 5), it produces 495_10. For 4-digit cases, non-trivial constants occur in certain bases; for instance, base 5 has 3032_5 as a fixed point, while base 10 has 6174_10. In odd bases, the behavior often involves cycles rather than fixed points. For example, in base 3 with 3 digits, all non-repdigit numbers converge to the 2-cycle consisting of 022_3 and 121_3, where applying the routine alternates between them. Base 8 (even) exhibits non-trivial 4-digit Kaprekar constants or cycles, such as fixed points documented in sequence analyses, though specific forms vary. These generalizations highlight how the routine's properties persist across bases, with constants providing insight into digit dynamics.

Special Case: Even Bases

In even bases b = 2k, Kaprekar constants arise from arrangements that balance the descending and ascending forms to produce systematic borrows during , ensuring the difference matches the original number. This balanced structure is facilitated by the even base, enabling explicit constructions for fixed points, whereas in odd bases cycles are more common though fixed points can exist for specific n. The derivation involves selecting s for the constant such that the sorted forms \alpha (descending) and \beta (ascending) satisfy \alpha - \beta = the constant, with borrows occurring in positions that regenerate the pattern. For the three-digit case, unique to even bases, the Kaprekar constant is explicitly constructed as the number with digits (k-1, 2k-1, k) in base b. This yields a fixed point because the descending arrangement is (2k-1, k, k-1), the ascending is (k-1, k, 2k-1), and subtraction involves borrows at each position: the units place borrows to give k, the middle place borrows to give $2k-1, and the hundreds place gives k-1, reproducing the original. For base 4 (k=2), the constant is $132_4 (30 in decimal); descending $321_4, ascending $123_4, and $321_4 - 123_4 = 132_4 via borrows confirming the pattern. In base 10 (k=5), this gives 495 for three digits, where $954 - 459 = 495. Extending to four digits in base 10, the constant exemplifies the alternating pattern: digits 6,1,7,4 lead to descending 7641 and ascending 1467, with subtraction $7641 - 1467 = 6174 through borrows at the units (4-7 borrows to 14-7=7, propagating to yield 1 in tens after further borrow) and hundreds places, aligning with the even base's symmetric halving properties.

Mathematical Properties

Convergence and Cycles

The Kaprekar routine defines a on the space of n-digit numbers in base b, where each iteration rearranges the digits to form the largest and smallest possible numbers and subtracts the latter from the former. This operation systematically reduces the variability in digit placements, as the resulting differences often exhibit repeated digits or symmetric patterns that propagate toward stable attractors, either fixed points or short cycles. For instance, in three- and four-digit cases in base 10, the process diminishes the spread between the highest and lowest digits in a stepwise manner, ensuring rapid progression to a unique fixed point. In base 10, convergence to fixed points occurs universally for three-digit numbers (to 495) and four-digit numbers with non-identical digits (to ), with the basin of attraction covering all such inputs—effectively 100% of the non-repdigit space for these lengths. For two-digit numbers, repdigits remain fixed at 00, while others enter a : 09 → 81 → 63 → 27 → 45 → 09, demonstrating cycle formation when fixed points are absent. Beyond four digits, the behavior fragments into multiple attractors; five-digit numbers, for example, distribute across three cycles, including a 2-cycle (53955 ↔ 59994) and two 4-cycles, with only a subset of inputs reaching each. Theoretical analyses reveal bounded iteration counts for small n, with empirical maximums of 6 steps for three-digit base-10 numbers and 7 steps for four-digit ones, beyond which no further progress occurs toward the attractor. In general bases and larger n, basins are partial, with cycle lengths typically short (1–5 iterations predominant across bases 2–36 for up to 9 digits), though no universal convergence proof exists—observations hold empirically for n ≤ 9, where transient lengths grow slowly.

Multiples of (b-1)

In base b, the Kaprekar routine involves rearranging the digits of a number \alpha to form the descending arrangement [\delta](/page/Delta) and the ascending arrangement [\beta](/page/Beta), then computing the next iterate as \delta - \beta. To show that this difference is always a multiple of b-1, consider modulo b-1. Since b \equiv 1 \pmod{b-1}, it follows that b^i \equiv 1 \pmod{b-1} for any non-negative i. Thus, \alpha = \sum d_i b^i \equiv \sum d_i \pmod{b-1}, where s = \sum d_i is the sum of the digits. The arrangements \delta and \beta use the same digits, so they are also congruent to s \pmod{b-1}. Therefore, \delta - \beta \equiv s - s = 0 \pmod{b-1}, meaning the first iterate is divisible by b-1. By , since each subsequent iterate is obtained by applying the same process to a multiple of b-1, all iterates in the sequence are multiples of b-1. This property holds regardless of whether the starting number \alpha is a multiple of b-1, but for sequences where all terms (including the starting number) are multiples of b-1, the initial number must satisfy this condition to avoid trivial paths leading immediately to . The Kaprekar constants themselves obey this divisibility; for example, in base 10 where b-1 = 9, the 3-digit constant 495 satisfies $495 \div 9 = 55, and the 4-digit constant satisfies $6174 \div 9 = 686. In general, Kaprekar sequences in base b preserve divisibility by b-1 from the first iterate onward, providing an algebraic that aids in analyzing and optimizing computational determination of constants by restricting searches to multiples of b-1.

References

  1. [1]
    Kaprekar Routine -- from Wolfram MathWorld
    The Kaprekar routine is an algorithm discovered in 1949 by DR Kaprekar for 4-digit numbers, but which can be generalized to k-digit numbers.Missing: original | Show results with:original
  2. [2]
    [PDF] On 2-digit and 3-digit Kaprekar's Routine - arXiv
    In 1949, D. R. Kaprekar [1] first discovered the following process: takes any four- digit number with at least two different digits; arrange the digits in ...
  3. [3]
    [PDF] The Kaprekar Routine - UNL Digital Commons
    This shows that when applying the Kaprekar Routine to any two-digit number, the difference will always be nine multiplied by the difference of the two digits.
  4. [4]
    [PDF] The Kaprekar Routine and Other Digit Games for Undergraduate ...
    The Kaprekar Routine is a famous mathematical procedure involving the digits of a positive integer. This paper offers natural generalizations of the routine ...
  5. [5]
    Mysterious number 6174 | plus.maths.org
    Mar 1, 2006 · Find out why in this follow-up to the article. References. Kaprekar, D. R., "Another Solitaire Game", Scripta Mathematica, vol 15, pp 244-245 ( ...
  6. [6]
    D R Kaprekar (1905 - 1986) - Biography - MacTutor
    This was first discovered by Kaprekar in 1946 and he announced it at the Madras Mathematical Conference in 1949. ... Scripta Mathematica in 1953. Clearly starting ...
  7. [7]
    A Primer On Kaprekar's Constant - Indica Today
    Sep 10, 2019 · In 1975, Martin Gardner, a famous author on popular mathematics, wrote an article on Kaprekar's constant in his popular column on recreational ...Missing: routine | Show results with:routine
  8. [8]
    [PDF] 6 = I* r odd - The Fibonacci Quarterly
    Kaprekar. "Another Solitaire Game." Scripta Mathematical,. 15 (1949):. 244-245. D. R. Kaprekar. "An Interesting Property of the Number 6174." Scripta.
  9. [9]
    [PDF] 高次桁のカプレカ変換1
    The Kaprekar Transformation for Higher-digit Numbers 1. Yumi Hirata. All fixed points and loops under the Kaprekar transformation up to 31 digits were found.
  10. [10]
    [PDF] A NEW CLASSIFICATION OF THE KAPREKAR NUMBERS 1 ...
    [3] showed that 6174 and 495 are the only Kaprekar constants. Meanwhile,. Hirata [1] found, by computation, 257 Kaprekar numbers less than or equal to 1031.
  11. [11]
    Kaprekar's Constant for 3-Digit Numbers: 495 - Math . info
    1) Take any three-digit number with at least two digits different. · 2) Arrange the digits in ascending and then in descending order to get two four-digit ...Missing: routine | Show results with:routine
  12. [12]
    Kaprekar's Constant | Brilliant Math & Science Wiki
    6+1+7+46174=343. This process fails for numbers made of 4 repeating integers (e.g. 7777). The most number of steps possible is 7 (e.g. 6432). This is also ...Missing: routine | Show results with:routine
  13. [13]
    (PDF) Kaprekar's Constant 6174 for Four Digits Number Reality to ...
    Aug 4, 2025 · Indian mathematician Kaprekar discovered a constant or dead end 6174 for four digits decimal number when the digits in the number are not repeated.
  14. [14]
    On the The Kaprekar Series
    These (no, not the zero) are the Kaprekar Series numbers. If you had tried a 4-digit number, you will reach 6174 and for 3-digit numbers you'll reach 495!
  15. [15]
  16. [16]
    A099009 - OEIS
    A099009 Fixed points of the Kaprekar mapping f(n) = n' - n'', where in n' the digits of n are arranged in descending, in n'' in ascending order.
  17. [17]
    [PDF] Kaprekar phenomena - University of Rochester
    It was shown that for decimals (i.e., base 10), for 3 digits, the constant is 495, and there is no such behavior in any other (than. 3 and 4) number of digits, ...
  18. [18]
    [PDF] The Base Dependent Behavior of Kaprekar's Routine - arXiv
    Oct 16, 2017 · In 1949, D. R. Kaprekar became the first to discover that this process, known as the Kaprekar Routine, would always yield 6174 within 7 ...
  19. [19]
  20. [20]
    [PDF] Fixed Points and Cycles of the Kaprekar Transformation: 1. Odd Bases
    A cycle is special if any member has a Kaprekar index that is not regular. Thus in base 3, Yamagami and Matsui's singular cycles are classified here as special, ...
  21. [21]
    A165094 - OEIS
    - **Summary**: A165094 lists fixed points of the base-8 Kaprekar map for 4-digit numbers. Examples include:
  22. [22]
    [PDF] A VARIATION ON THE TWO-DIGIT KAPREKAR ROUTINE Anne ...
    In 1949 the Indian mathematician D. R. Kaprekar discovered a curious relationship between the number 6174 and other 4-digit numbers.
  23. [23]
    [PDF] integers 21 (2021) maximum distances in the four-digit kaprekar ...
    Oct 15, 2021 · Prichett, A.L. Ludington, and J.F. Lapenta, The determination of all decadic Kaprekar constants, Fibonacci Quart. 19(1) (1981), 45–52 ...<|control11|><|separator|>
  24. [24]
    [PDF] Rich dynamical behaviors from a digital reversal operation - arXiv
    Aug 5, 2024 · The. Kaprekar routine is to arrange the digits in either descending order or ascending order, then subtract the two (e.g., 1726 → 7621-1267 ...<|control11|><|separator|>