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

Internet Message Format | 1992-07-23 | 1.9 KB

Path: sparky!uunet!mcsun!uknet!cam-cl!cam-cl!cet1
From: [e-mail] (C.E. Thompson)
Newsgroups: sci.math
Subject: Re: Hailstone sequences
Keywords: Hailstone Collatz
Message-ID: <[e-mail]>
Date: 23 Jul 92 23:46:46 GMT
References: <[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: 41

In article <[e-mail]>,
[e-mail] (Kermit Rose) writes:
|>
|> Two simple observations:
|>
|> If n = (2^k+1)m where m is odd, then n' = 3(2^k+1)m + 1 and n'' =
|> 3(2^[k-1])m + [3m+1]/2 is larger than n.
|> If m = 3 mod 4, then [3m+1]/2 is odd.

More generally, if n = -1 mod 2^k, then the 3x+1 and x/2 cases will
strictly alternate k-1 times, and so there are n which get bigger by
arbitrarily large factors.

|> If we could show that for each n, the sequence eventually reaches a value
|> less than n, then an inductive proof would be possible.

Quite. One uses this observation in programs to verify the Collatz hypothesis
up to some large N. For example, all but 19 of the residue classes mod 256
produce an iterate smaller than the original number before one loses track
of their parity.

By the way, it is natural to extend the domain of the function being
iterated to include the negative integers (or equivalently, to use
3x-1 instead of 3x+1 in the x odd case). As well as the cycle

   (1, 2, 4)

one then also gets

   (-1, -2)
   (-5, -14, -7, -20, -10)
   (-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61,
      -182, -91, -272, -136, -68, -34)

and probably (but as unprovably as before) no more. (I suppose {0}
should be included as a cycle all by itself!)

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