Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Analyzing a Number Mystery

Date: 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/ 
Associated Topics:
College 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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/