NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/math/9553

Internet Message Format | 1992-07-25 | 2.8 KB

Path: sparky!uunet!mcsun!uknet!cam-cl!cam-cl!cet1
From: [e-mail] (C.E. Thompson)
Newsgroups: sci.math
Subject: Re: Hailstone sequences
Message-ID: <[e-mail]>
Date: 26 Jul 92 00:09:25 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Sender: [e-mail] (The news facility)
Reply-To: [e-mail] (C.E. Thompson)
Organization: U of Cambridge Computer Lab, UK
Lines: 46

In article <[e-mail]>,
[e-mail] (Adam Chalcraft) writes:
|>
|> The result that on the positive integers, the function
|>   f(x)=3x+1 or x/2
|> seems to eventually send every positive integer to 1, whereas the function
|>   f(x)=3x-1 or x/2
|> does not is rather strange. Clearly the first function is "larger" than
|> the second. All that this shows, of course, is that the word "larger" has
|> no useful meaning here, and so any proof that the first function always
|> goes to 1 must use something a bit more subtle.

What one would hope to prove (if one were insanely optimistic) would be
that all sufficiently large integers have eventual iterates smaller than
themselves. How many cycles there are that they might then converge to
would be a matter of "chance".

One way of looking at this is to observe that a cycle with a rises and
b falls multiplies the original number by 3^a/2^b, with a little
pertubation due to the 1s. So one looks for cases where 3^a ~= 2^b:

    3 > 2    3x-1 needed: cycle does exist (1,2)
    3 < 4    3x+1 needed: cycle does exist (1,4,2)
    9 > 8    3x-1 needed: cycle does exist (5,14,7,20,10)
   27 < 32   3x+1 needed: cycle doesn't exist ... ah well
  243 < 256  3x+1 needed: cycle doesn't exist ... life is unfair
 2187 > 2048 3x-1 needed: cycle does exist (17,50,25,74,37,110,55,164,82,41,
                                            122,61,182,91,272,136,68,34)

It isn't too difficult to see how one can bound the perturbation caused
by the +1 or -1, and thus put an upper bound on the smallest member of
any posssible cycle that has particular values of a and b.

The same sort of argument applies to the Conway permutation sequence
generated by 2n->3n, 4n+1->3n+1, 4n-1->3n-1 that I mentioned in another
article, except that here the perturbations are smaller and are both
positive and negative. A cycle of length r contaniing s odd numbers should
make 3^r ~= 2^(r+s). I showed the cycles of lengths 1, 2 and 5 and
invited readers to find the other known one, but I did reveal its length.
I should have kept that concealed as well and suggested that anyone wanting
to guess it should look at the nearest piano...

Chris Thompson
Cambridge University Computing Service
JANET:    [e-mail]
Internet: [e-mail]