Tuesday, December 2, 2014

Some notes on the Kaprekar function




Consider a 3 digit number, say 395. Take its digits and form the greatest and least possible 3 digit numbers and subtract them: 935 - 359 = 594. Now do the same with the result:  954 - 459 = 495. Try it again, and you see that the process has hit a fixed point: 954 - 459 = 495.


The Kaprekar function involves taking a number, computing two shuffles of its digits (the shuffle with the greatest value, and the one with the least value), and then taking the difference of those two shuffles. So for an integer n, if g is the number you get from re-arranging the digits of n from greatest to least, and l is the number you get from re-arranging the digits of n from least to greatest, then the Kaprekar function is (n) = g - l. If you repeatedly apply the Kaprekar function to an integer n, you may end up converging to a constant value. For any n whose digits are all the same, you automatically converge to 0. Surprisingly, for any 3 digit number whose digits are not all the same, k will converge to 495 (as is the case with the numbers in this plot), for any 4 digit number whose digits are not all the same, k will converge to 6174. Numbers with more than 4 digits apparently do not have a single convergent value, but bounce around within sets of values.


The pattern on the left comes from making 9 columns of numbers, the leftmost column is a listing of 100 to 199 (starting at the bottom), the rightmost column is a listing of 900 to 999. These are coloured based on how quickly each number causes the Kaprekar function to converge to a constant value. Mathworld shows a similar plot for four-digit numbers taken from an article that appeared in Mathematics Teacher.



Here's a few examples of 3 digit numbers converging to 495:

949 -> 495 (white)
950 -> 891 -> 792 -> 693 -> 594 -> 495 (dark pink)
951 -> 792 -> 693 -> 594 -> 495 (somewhat dark pink)
952 -> 693 -> 594 -> 495 (somewhat light pink)
953 -> 594 -> 495 (light pink)
954 -> 495 (white)

949 converges quickly: 994 - 499 = 495; 953 takes a little longer, first you get 953 - 359 = 594. and then 594 gives us 954 - 459 = 495. You can test out the other chains, and also try it with any three digit number whose digits are not all the same: they always end up at 495. A 3 digit number whose digits are all the same gives 0.

Here are two observations that help me understand what is going on with this:

(1) If you take the difference of two shuffles of the same number, the result is always divisible by 9.

(2) Any number that is divisible by 9, when shuffled, will also be divisible by 9.

I found these two things very surprising at first, but both can be understood if you think about digital roots.

When you apply the Kaprekar function to a number, your result is not just any old number, but a member of a much smaller set: the multiples of 9. And since many of those multiples of 9 are just shuffles of other multiples of 9, they behave the same when the Kaprekar function is applied to them.

Why does the pattern for the three digit numbers seem to repeat and shift up to the right? The shift corresponds to adding 111. Adding 111 generally increases each digit by 1 (except if one of the digits is a 9), leaving the difference between the greatest and least shuffles unchanged.