Associated Topics || Dr. Math Home || Search Dr. Math

### 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!
```
Associated Topics:
College Number Theory
High School Functions
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search