The Recurring Fixed Point

The mathematical concept I am about to discuss was first introduced by Indian mathematician D.R. Kaprekar in 1959. He devised an algorithm for any 4-digit number, excluding those comprised of identical digits. For instance, 5793 is acceptable, while 0000 or 9999 is not (you'll see why soon).

Let’s use 5793 for our initial demonstration of Kaprekar's method, which comprises three steps:

Step 1: Form a new number 'A' by arranging the digits in descending order. For 5793, A = 9753.

Step 2: Form a new number 'B' by arranging the digits in ascending order. For 5793, B = 3579.

Step 3: Compute the difference between A and B. For 5793, A - B = 6174.

Please remember this algorithm, as we will utilize it several times throughout the essay. As shown, for 5793, the algorithm leads us directly to 6174. Could this simply be a coincidence?

Let's test this theory with another number, 6859, and apply Kaprekar's algorithm again:

Step 1: For 6859, A = 9865.

Step 2: For 6859, B = 5689.

Step 3: For 6859, A - B = 4176.

Did you expect to get 6174? If so, don’t worry just yet. Let’s apply Kaprekar's algorithm recursively to 4176:

Step 1: For 4176, A = 7641.

Step 2: For 4176, B = 1467.

Step 3: For 4176, A - B = 6174.

This time, we indeed reach 6174! In the first instance (with 5793), we landed on 6174 immediately, while with 6859, we needed to apply the algorithm again to the first resulting number, 4176.

In this context, 4176 is referred to as a Kaprekar number, and 6174 is known as Kaprekar’s constant. It turns out that when we apply Kaprekar's algorithm recursively to any 4-digit number (that does not consist of the same four digits), the steps needed to arrive at 6174 can range from 1 to 7. In other words, while it may take some time, we will ultimately reach 6174.

At this juncture, the naturally curious among you might wonder what happens when we apply Kaprekar's algorithm to 6174 itself. Let's find out:

Step 1: For 6174, A = 7641.

Step 2: For 6174, B = 1467.

Step 3: For 6174, A - B = 6174.

How intriguing! We again end up with 6174. This means that regardless of the starting point, we always arrive at the fixed point of 6174. This is why 6174 is termed Kaprekar’s constant, while the numbers we encounter along the way are known as Kaprekar numbers. The initial number we work with (like 5793) is designated a seed number.

But what accounts for this phenomenon? To start grasping the underlying principles, let's investigate the cases of 2-digit and 3-digit numbers. The insights we uncover will be both enlightening and surprising. Let's begin with the 2-digit scenario.

The Limit Cycle

To kick things off, let’s examine the number 90 using Kaprekar's algorithm:

Step 1: For 90, A = 90.

Step 2: For 90, B = 09.

Step 3: For 90, A - B = 81.

From this point onward, we will apply Kaprekar's algorithm recursively several times. To streamline the explanation, I will present the results (Kaprekar numbers) as follows: Seed number ? Kaprekar number ? Kaprekar number ? Kaprekar number …

The sequence of Kaprekar numbers following the original number is termed a Kaprekar sequence. For the number 90, the Kaprekar sequence is:

90 ? 81 ? 63 ? 27 ? 45 ? 09 ? 81 ? …

Do you observe anything particularly noteworthy? Take a moment if necessary. For starters, ALL of these numbers are multiples of 9. Additionally, notice that at step 1, we arrived at 81, and at step 6 (considering 90 as step 0), we returned to 81. If we continued applying Kaprekar's algorithm beyond this point, the sequence from 81 through 09 would repeat indefinitely.

In number theory, such a cycle is known as a Limit Cycle.

It could be coincidental that we ended up with multiples of 9 starting from 90, so let’s try another unrelated seed number: 16. The Kaprekar sequence for 16 is as follows:

16 ? 45 ? 09 ? 81 ? 63 ? 27 ? 45 ? …

Isn’t that fascinating? Once again, we arrive at a sequence consisting of multiples of 9 that repeats every 6 steps.

Our discovery that Kaprekar numbers are multiples of 9 is valuable in itself. However, we can further demonstrate that all 2-digit Kaprekar numbers MUST be multiples of 9.

Let ‘a’ and ‘b’ denote the two digits of the original number where a > b. Consequently, from the first step of Kaprekar's algorithm, we derive A = ab. From the second step, we obtain B = ba. Finally, we can express any Kaprekar number with the following formula:

Kaprekar number (K) = ab - ba

Here, ‘a’ represents the 10's place in the decimal system, while ‘b’ represents the 1's place. For the second number, their positions are reversed. Thus, we can represent the formula visually:

This relationship verifies that all 2-digit Kaprekar numbers MUST be multiples of 9. Furthermore, it provides a means to predict the next Kaprekar number from a given one. With this, we could compile a table of all possible Kaprekar sequences. While this may be tedious, it would still be an improvement over random guessing (the entropy is significantly reduced with a finite table).

When we began this investigation, our understanding was minimal. But we have made significant progress. What more can we learn? Let's advance to the 3-digit case and discover.

The Limit Cycle Disappears

Having already laid out the groundwork in previous cases, I can be more concise with the 3-digit scenario. Let’s begin by outlining the Kaprekar sequence for the 3-digit seed number 741:

741 ? 594 ? 495 ? 495

Wait, what? Our limit cycle from the 2-digit case has vanished, revealing Kaprekar’s constant for the 3-digit case (495). To be thorough, here are the Kaprekar sequences for two additional seed numbers, 142 and 480:

142 ? 297 ? 693 ? 594 ? 495 ? 495

480 ? 792 ? 495 ? 495

Do you notice anything particularly interesting? Take your time if needed. First, all of the Kaprekar numbers have 9 as their middle digit. Second, the sum of the first and last digits always equals 9. Consequently, the total of all digits for 3-digit Kaprekar numbers is consistently 18. Why is this?

We can apply the same mathematical approach we used for the 2-digit case to understand why this occurs. Let the seed number be represented by abc, where all three digits differ (a ? b ? c). The formula for the Kaprekar number can be expressed as follows:

K = abc - cba

For the first number, ‘a’ occupies the 100's place, ‘b’ takes the 10's place, and ‘c’ is in the 1's place. In cba (the second number), their positions are inverted. Thus, we can illustrate the formula:

This formula conveys two key points:

1. All 3-digit Kaprekar numbers are multiples of 99 (and thus 9).
2. Any 3-digit Kaprekar number can be computed using ONLY the first and last digits of the seed/Kaprekar number.

The elimination of the middle digit (9) can be viewed as a reduction of noise or entropy. Armed with this insight, we can now predict the behavior of Kaprekar's algorithm for the 3-digit case. Finally, we are ready to tackle the 4-digit case (6174).

The Equivalence Class

Just as we defined seed numbers for the 2-digit and 3-digit cases, let’s define the seed number for the 4-digit case using the digits ‘a’, ‘b’, ‘c’, and ‘d’, where a ? b ? c ? d. Thus, we can formulate the equation for 4-digit Kaprekar numbers as follows:

K = abcd - dcba

In this equation, ‘a’ represents the 1000's place, ‘b’ the 100's place, ‘c’ the 10's place, and ‘d’ the 1's place. For dcba (the second number), their positions are reversed. Therefore, we can rewrite the formula visually:

This relationship confirms that 4-digit Kaprekar numbers are also multiples of 9. Furthermore, it offers a method to predict the behavior of Kaprekar sequences. Without this relationship, we would have to create a table of 10,000 possible 4-digit numbers.

You might be wondering how this formula is beneficial. Focus on the terms (a - d) and (b - c). These represent the differences between the outer and inner digits, respectively. Let’s designate m = (a - d) and n = (b - c). We can rewrite the 4-digit Kaprekar formula as follows:

K(m, n) = 999m + 90n

Interestingly, numerous 4-digit numbers can yield the same (m, n) combination. A collection of mathematical objects that share a common characteristic is grouped into an equivalence class.

For instance, the equivalence class for (8, 1) includes 9981, 9871, 9651, 9541, 9431, 9321, 9211, 8870, 8760, 8650, 8540, 8430, 8320, 8210, 8100, and all their permutations. This significantly decreases the number of possibilities.

Excluding numbers with identical digits, there are only 54 classes in total that converge to Kaprekar’s constant (6174). This greatly simplifies the prediction of Kaprekar sequence behavior in the 4-digit case.

If you’ve read this far, I assume you find these concepts as captivating as I do. But what practical application does this have? As far as my research indicates, the concept of the Kaprekar sequence has limited utility outside the realm of cryptography. While this may be somewhat disappointing, I believe it remains a noteworthy contribution to mathematics, kindling excitement among math enthusiasts.

With that, I conclude this essay and hope you found it enjoyable.

A MAP of almost ALL of my work till date. Enjoy!

Reference and credit: David Deutsch and Benjamin Goldman.