I first encountered the algorithm that Wolfram MathWorld calls Kaprekar's Routine last year and actually made a post about it titled Birth Year Magic. I've created this post because I was reminded of the similarity between Kaprekar's Routine and the Odd-Even Algorithm that I've written about in a number of previous posts:
The Kaprekar routine is an algorithm discovered in 1949 by D. R. Kaprekar for 4-digit numbers, but which can be generalised to \(k\)-digit numbers. To apply the Kaprekar routine to a number \(n\), arrange the digits in descending \( n^{'} \) and ascending \( n^{''} \) order. Now compute \( K(n)=n^{'}-n^{''} \) (discarding any initial 0s) and iterate, where \(K(n)\) is sometimes called the Kaprekar function. The algorithm reaches 0 (a degenerate case), a constant, or a cycle, depending on the number of digits in \(k\) and the value of \(n\). The list of values is sometimes called a Kaprekar sequence, and the result K(n) is sometimes called a Kaprekar number (Deutsch and Goldman 2004), though this nomenclature should be deprecated because of confusing with the distinct sort of Kaprekar number.In base-10, the numbers n for which \(K(n)=n\) are given by 495, 6174, 549945, 631764, ... (OEIS A099009). Similarly, the numbers \(n\) for which iterating \(K(n)\) gives a cycle of length \(k \geq 2\) are given by 53955, 59994, 61974, 62964, 63954, 71973, ... (OEIS A099010).Iterating the Kaprekar map in base-10, all 1- and 2-digit numbers give 0. Exactly 60 3-digit numbers, namely 100, 101, 110, 111, 112, 121, 122, 211, 212, 221, ... (OEIS A090429), reach 0, while the rest give 495 in at most 6 iterations. Exactly 77 4-digit numbers, namely 1000, 1011, 1101, 1110, 1111, 1112, 1121, 1211, ... (OEIS A069746), reach 0, while the remainder give 6174 in at most 8 iterations. The value 6174 is sometimes known as Kaprekar's constant (Deutsch and Goldman 2004). This pattern breaks down for 5-digit numbers, which may converge to 0 or one of the 10 constants 53955, 59994, 61974, 62964, 63954, 71973, 74943, 75933, 82962, 83952.
I developed an SageMath algorithm (permalink) to determine the behaviour of numbers of any length over a given range. In my earlier post, my algorithms only applied to three and four digit numbers. Here is the behaviour for numbers in the range from 26400 to 26425:
26400 --> [26400, 63954, 61974, 82962, 75933, 63954]
26401 --> [26401, 62964, 71973, 83952, 74943, 62964]
26402 --> [26402, 61974, 82962, 75933, 63954, 61974]
26403 --> [26403, 61974, 82962, 75933, 63954, 61974]
26404 --> [26404, 61974, 82962, 75933, 63954, 61974]
26405 --> [26405, 62964, 71973, 83952, 74943, 62964]
26406 --> [26406, 63954, 61974, 82962, 75933, 63954]
26407 --> [26407, 73953, 63954, 61974, 82962, 75933, 63954]
26408 --> [26408, 83952, 74943, 62964, 71973, 83952]
26409 --> [26409, 93951, 85932, 74943, 62964, 71973, 83952, 74943]
26410 --> [26410, 62964, 71973, 83952, 74943, 62964]
26411 --> [26411, 52965, 70983, 94941, 84942, 73953, 63954, 61974, 82962, 75933, 63954]
26412 --> [26412, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26413 --> [26413, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26414 --> [26414, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26415 --> [26415, 52965, 70983, 94941, 84942, 73953, 63954, 61974, 82962, 75933, 63954]
26416 --> [26416, 53955, 59994, 53955]
26417 --> [26417, 63954, 61974, 82962, 75933, 63954]
26418 --> [26418, 73953, 63954, 61974, 82962, 75933, 63954]
26419 --> [26419, 83952, 74943, 62964, 71973, 83952]
26420 --> [26420, 61974, 82962, 75933, 63954, 61974]
26421 --> [26421, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26422 --> [26422, 41976, 82962, 75933, 63954, 61974, 82962]
26423 --> [26423, 41976, 82962, 75933, 63954, 61974, 82962]
26424 --> [26424, 41976, 82962, 75933, 63954, 61974, 82962]
26425 --> [26425, 42966, 71973, 83952, 74943, 62964, 71973]
All the numbers end in a loop of one type or another. Let's compare what happens to today's number (I'm 26402 days old) under the two different algorithms:
- Kaprekar's Routine:
26402 --> [26402, 61974, 82962, 75933, 63954, 61974] - Odd Even Algorithm:
26402 -->[26402, 26388, 26367, 26363, 26355, 26360, 26349]
No comments:
Post a Comment