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!