home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9481 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  1.7 KB
  1. Path: sparky!uunet!mcsun!uknet!cam-cl!cam-cl!cet1
  2. From: cet1@cl.cam.ac.uk (C.E. Thompson)
  3. Newsgroups: sci.math
  4. Subject: Conway's permutation sequence
  5. Keywords: Conway Collatz Hailstone
  6. Message-ID: <1992Jul24.001907.9491@cl.cam.ac.uk>
  7. Date: 24 Jul 92 00:19:07 GMT
  8. References: <1992Jul22.134601.6735@nmt.edu>
  9. Sender: news@cl.cam.ac.uk (The news facility)
  10. Reply-To: cet1@cl.cam.ac.uk (C.E. Thompson)
  11. Organization: U of Cambridge Computer Lab, UK
  12. Lines: 37
  13.  
  14. In article <1992Jul22.134601.6735@nmt.edu>, jefu@akbar.nmt.edu 
  15. (Jeff Putnam) considers inverting the order of the Collatz sequence
  16. (I would still like to know where this "Hailstone" tag comes from)
  17. and points out that there are either 1 or 2 possible immediate
  18. predecessors for each integer.
  19.  
  20. This reminded me of the following function defined on the integers:
  21.  
  22.    f(2n)   = 3n
  23.    f(4n+1) = 3n+1
  24.    f(4n-1) = 3n-1
  25.  
  26. due to J.H.Conway. Obviously, this f does have an inverse; therefore
  27. under iteration of f every integer either lies in a cycle or in a
  28. doubly-infinite chain. The first few lie in cycles:
  29.  
  30.    (1)
  31.    (2, 3)
  32.    (4, 6, 9, 7, 5)
  33.  
  34. Do the iterates of 8,
  35.  
  36.      ..., 287, 215, 161, 121, 91, 68, 102, 153, 115, 86, 129, 97, 73,
  37.      55, 41, 31, 23, 17, 13, 10, 15, 11, 8, 12, 18, 27, 20, 30, 45, 34,
  38.      51, 38, 57, 43, 32, 48, 72, 108, 162, 243, 182, 273, 205, 154, 231, 
  39.      173, 130, 195, 146, 219, 164, 246, ...
  40.  
  41. form a doubly-infinite chain? Probably...
  42.  
  43. There is one more known cycle, of length 12, which I leave as an exercise
  44. for the interested reader (its elements are less than 300). Are there any
  45. others? M.J.T.Guy has proved that if so, they have length greater than 320.
  46.  
  47. Chris Thompson
  48. Cambridge University Computing Service
  49. JANET:    cet1@uk.ac.cam.phx
  50. Internet: cet1@phx.cam.ac.uk
  51.