Sunday, June 3, 2018

241: A Strange Fixation

Audio Link


Hi everyone.   Before we get started, I want to thank listener ‘katenmkate’ for posting another nice review in Apple Podcasts recently.   Thanks Kate!   By the way, other listeneres:  the podcast world is constantly growing more competitive, so a new positive review is still useful— please think about posting one if you like the podcast.   And the same comment goes for the Math Mutation book, which is available & reviewable on Amazon.   Also remember, if you like Math Mutation enough that you want to donate money, please make a donation to your favorite charity & email me about it, and I’ll mention you on the podcast for that as well.

Now for today’s topic.   Try the following experiment:   Take any 4-digit number and generate 2 values from it by arranging the digits in ascending and then descending order.   By the way, don’t choose a degenerate case where the number has all digits the same, like ‘2222’.   (For today I’ll pronounce 4-digit numbers just by saying the digits, to save time.)   Now subtract the smaller 4-digit number from the larger one.  You should find that you get another 4-digit number (or a 3-digit one, in which case you can add a leading 0.)   Repeat the process for a few steps.   Do you notice anything interesting?

For example, let’s start with 3524.  After we generate numbers by the orderings of the digits, we subtract 5432 - 2345, and get 3087.    Repeating the procedure, we subtract 8730-0378, and get 8352.   One more time, and we do 8532 - 2358, to get 6174.   So far this just seems like a weird procedure for generating arbitrary numbers, maybe a bit of a curiosity but nothing special.   But wait for the next step.   From 6174, we do 7641 - 1467, which gives us… 6174 again!   We have reached an attractor, or fixed point:   repeating our process always brings us back to this same number, 6174.   If you start with any other non-degenerate 4-digit number, you will find that you still get back to this same value, though the number of steps may vary.

This value, 6174, is known as Kaprekar’s Constant,  named after the Indian mathematician who discovered this strange property back in 1949.   Strangely, I was unable to find any mention of an elegant proof of why this number is special; it seems like it’s just one of those arbitrary coincidences of number theory.  It’s easy to prove the correctness of the Constant algebraically, but that really doesn’t provide much fundamental insight.   This constant does have some interesting additional properties though:   in the show notes, you’ll find a link to a fun website by a professor named Girish Arabale.    He uses a computer program to plot how many steps of Kaprekar’s operation it takes to reach the constant, indicating the step count by color, and generates some pretty-looking patterns.   The web page even showcases some music generated by this operation, though I still prefer David Bowie. 

We see more strange properties if we investigate different numbers of digits.   There is a corresponding constant for 3-digit operations, 495, but not with any higher digit counts.   If you try the same operation with 2, 5 or 6 digit numbers, for example, you will eventually settle into a small loop of numbers which generate each other, or a small set of possible self-generating constants, rather than a single arbitrary constant.    Let’s try 2 digits, starting arbitrarily at 90:      90 - 09 = 81.   81 - 18 = 63.  63 - 36 = 27.   72 - 27 = 45.  54 - 45 = 09— and you can see we’re now in a loop.   If we continue the operation, we will repeat  9, 81, 63, 27, 45, 9 forever!   You will see similar results if trying the operation in bases other than 10, where the meaning of the digits is slightly different and a result similar to Kaprekar’s doesn’t appear so easily.

One other aspect of Kaprekar’s Constant that we should point out is that this is really just a specific example of the general phenomenon of “attractors”.   If you take an arbitrary iterative operation, where you repeat some calculation that leads you back into the same space of numbers, it’s not that unusual to find that you eventually settle into a small loop, a small set of constants, or a fixed point like Kaprekar’s Constant.   I think his constant became famous because it’s described with a relatively simple operation, and was discovered relatively early in the history of popularization of the mathematical concept of attractors.    

Thinking about such things has actually become very important in some areas of computer science, such as the generation of pseudo-random numbers.   We often want to use a repeated mathematical procedure to generate numbers that look random to the consumer, but from the same start point, called a “seed”, will always generate the same numbers.   This is important in areas like simulation testing of engineering designs.   In my day job, for example, I might want to see how a proposed new computer chip would react to a set of several million random stimuli, but in case something strange happens, I want to easily reproduce the same set of supposedly “random” input later.     The typical solution is a pseudo-random number generator, where the previous number generates the next one through some function.

Kaprekar’s Constant helps demonstrate that if we choose an arbitrary mathematical procedure to repeatedly generate numbers from other ones, the results might not end up as arbitrary or random-looking as you would expect.   You can create some convoluted repetitive procedure that really has no sensible reason in its definition for creating a predictable pattern, like Kaprekar’s procedure, and suddenly find that it always leads you down an elegant path to a specific constant or a small loop of repeated results.   Thus, the designers of pseudo-random number generators must be very careful that their programs really do create random-seeming results, and are free of the hazards of attractors and fixed points like Kaprekar’s Constant.

And this has been your Math Mutation for today.


References:



6 comments: