Analyzing a Number MysteryDate: 04/10/2006 at 10:36:53 From: Rach Subject: up and down puzzle Take a four digit number (e.g. 8256), write this number in descending order of digits (e.g. 8652) and then in ascending order (e.g. 2568). Subtract the second from the first. Repeat this process with the answer gained, and eventually you wind up with 6174 and get stuck with that result over and over. Following the same process with any starting three digit number always winds up at 495. Why does this happen? For example, 8652 - 2568 = 6084 8640 - 0468 = 8172 8721 - 1278 = 7443 7443 - 3447 = 3996 9963 - 3699 = 6264 6642 - 2466 = 4176 7641 - 1467 = 6174 7641 - 1467 = 6174 stuck on 6174! Date: 04/11/2006 at 21:11:19 From: Doctor Vogler Subject: Re: up and down puzzle Hi Rach, Thanks for writing to Dr. Math. That's a very good question. And I have a very good answer. And a completely unsatisfactory answer. I'll start with the latter, and then explain it with the former: It's just a fluke, a random coincidence, pure luck. Or mostly luck, anyway. In particular, if you use six digits instead of four, then some numbers end on 549945, and other numbers end on 631764, while still others fall into the loop 862632 -> 642654 -> 420876 -> 851742 -> 750843 -> 840852 -> 860832 -> 862632.... For that matter, there are nine four-digit numbers that don't end in 6174. They end in 0. You see, your problem has the following form: You have a finite set S (namely, 4-digit numbers, or 3-digit numbers). And you have a function f: S -> S that maps elements from your set S to (possibly) other elements of your set S. In your case, the function reorders the digits in two ways and takes a difference, but the actual function really doesn't play a very large role. Now you start iterating your function. You start with a number A, and then you compute B = f(A) C = f(B) D = f(C) E = f(D) and so on. Well, you can do this as long as you'd like. In particular, since your set S is finite, you can keep doing this until you get a repeat. Well, as soon as you get one repeat, it will continue to repeat in a cycle, like that seven-long cycle I mentioned in the six-digit case, or like the one-long cycles that you mentioned (a one-long cycle is also called a "fixed point"). So the bottom line is this: No matter where you start, you will eventually end in a cycle (or a fixed point, if the cycle has length one). Now consider a small case: Take S = {0, 1, 2, 3, ... 9}, and define f(x) to be the rightmost (i.e. the "ones" digit) of 2*x. Now draw a graph of what f does to each element of S. You should find that you get a cycle of length 5 (you can draw this as a circle with five arrows pointing around the circle). You also have five other numbers that point into the cycle but nothing points to them. Elements that are not part of a cycle are said to belong to tails (or just "the tail" meaning all of the tails together). Sometimes tails can be very long, but the point is that everything on a tail eventually goes into a cycle and never comes back. Well, in your case, everything is part of a tail, and the only cycle is a single fixed point (well, two fixed points actually, if you count 0). Is this surprising? Or is it normal? Some mathematicians have studied such questions. It boils down to this: Suppose you have a set S with n elements. (It really doesn't matter what they are, so we might as well say the integers from 1 to n.) Then we pick a *random* function f. That is, for each number x from 1 to n, we randomly choose f(x) to be any number from 1 to n. Then we look at the graph. How much is tail, and how much is cycle? How big do the cycles get, and how many are there? Of course, there is a small probability that we will just get one big cycle (such as 1 -> 2 -> 3 -> ... -> n -> 1...), but it turns out that the overwhelming majority of the time, *most* of the numbers in S belong to the tail, and only a rather small portion of them belong to cycles. Typically we get a handful of rather small cycles. So, in your case, you should first notice that one iteration of your function always results in a number divisible by 9 (can you explain why?). So really you are looking at only 1000 four-digit numbers (not 9000). You end up with two fixed points and everything else is tail. Yes, that's a little less cycle than you expect, but you didn't really expect that much in the first place. Consider the six-digit case. Now you have three fixed points (including 0) and a seven-cycle, totaling ten cycle points. Is that small, or about what you expect? Well, if it is small, it's not all that far from what you expect. Furthermore, you tend to get more cycle and less tail when your function has a lot of repeated values. For example, rearranging the digits in x doesn't change f(x), nor does adding the same number to the first and last digits of x, or the two middle digits. These kinds of features of your function f(x) explain why you get even less cycle than random, but even random functions don't get all that much. Sometimes people ask questions that end up being this kind of problem, although it doesn't look like it at first. For example, they might ask what eventually happens to a natural number (positive integer) when you keep applying the function f(x) = sum of k'th powers of the digits of x. In this case, your set S is infinite (all positive integers), but it turns out that this doesn't really matter. You see, when x is very very large, then f(x) will always be much smaller. That means that f still defines a function on a finite set S (positive integers smaller than a certain large number), and even if you start with a number outside of S, it will eventually come inside of S again. In other words, all positive integers not in S are part of the tail. I hope this was helpful. If you have any questions about this, please write back and show me what you have been able to figure out, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/