Integer Iteration Function
Date: 12/24/2003 at 12:38:49 From: Miltos Subject: The magic 123!! Let X be a positive integer, A be the number of even digits in that integer, B be the number of odd digits and C be the number of total digits. We create the new integer ABC and then we apply that process repeatedly. We will eventually get the number 123! For example, suppose we start with 4673985. A = 3 evens, B = 4 odds and X = 7 total digits. So now we have ABC = 347. Using the same rule, there is 1 even, 2 odds and 3 total so we have 123. This always works! But how can we prove that?
Date: 12/24/2003 at 18:24:04 From: Doctor Vogler Subject: Re: The magic 123!! Hi Miltos, This is an example I hadn't run into before of a function whose iterations spiral into a small set, in this case a single 3-digit number. (Other examples are to go from a number to the sum of its digits, or to the sum of the squares of its digits.) They are all analyzed in the same manner: Let's say that f(n) is the function that goes from the number X to the number ABC. That is, f(X) = ABC. If you start with a number X which has more than three digits, then f(X) = ABC will have *fewer* digits than X. But if you start with a number X which has three digits or fewer, then f(X) = ABC will still have three digits or fewer. This is the important point that shows that iterating (or repeating) this function will take all large values closer and closer and finally into the finite set of 3-digit numbers (there are only 999 of them), and then it will stay there. From there, we just have to look at what happens to those 999 numbers. Fortunately, for your function, that's not very hard. If X is a one-digit number, then f(X) is either 101 or 011. If X is a two-digit number, then f(X) is one of 202, 112, or 022. If X is a three-digit number, then f(X) is one of 303, 213, 123, or 033. All of these converge to 123 like so: one-digit-number -> one of these two: 101 -> 123 011 -> 123 two-digit-number -> one of these three: 202 -> 303 -> 123 112 -> 123 022 -> 303 -> 123 three-digit-number -> one of these four: 303 -> 123 213 -> 123 123 -> 123 033 -> 123 Does that answer your question? Write back if you have any more questions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 12/25/2003 at 08:21:02 From: Miltos Subject: The magic 123!! Thanks for the answer Dr.Vogler. I had the same thoughts but I still haven't found how I can prove that this function will take X to f(X) with fewer digits. I know that is obvious but we have a mathematical problem here and I must.
Date: 12/25/2003 at 20:39:19 From: Doctor Vogler Subject: Re: The magic 123!! Miltos, Well, okay. Let's suppose that X has n digits and n > 3. Case 1: If n < 10, then A, B, and C are one digit each, so f(X) has 3 digits. Case 2: If n >= 10, then A, B, and C are each less than or equal to n. So how many digits can they each have? Well, no more than 1 + log n (to base 10). So f(X) can have no more than 3(1 + log n) digits. Then you just need to show that 3(1 + log n) < n. Show (for example by induction on n) that, for n > 9, n < 2^(n-3). Conclude that n^3 < 8^(n-3) < 10^(n-3). Since log (base 10) is an increasing function, log (n^3) < log 10^(n-3) 3 log n < n - 3 3 + 3 log n < n 3(1 + log n) < n Will that do it? Write back if you need more help. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 12/28/2003 at 13:22:47 From: Miltos Subject: Thank you (The magic 123!!) Thank you, Dr. Vogler. That's the complete answer to the problem. Numbers are mysterious--have fun with your explorations of them!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.