home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / puzzles / 7359 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  1.3 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!stanford.edu!rock!concert!rutgers!igor.rutgers.edu!remus.rutgers.edu!clong
  2. From: clong@remus.rutgers.edu (Chris Long)
  3. Newsgroups: rec.puzzles
  4. Subject: Re: Another sequence (SPOILER)
  5. Message-ID: <Nov.18.03.30.31.1992.18485@remus.rutgers.edu>
  6. Date: 18 Nov 92 08:30:32 GMT
  7. References: <1992Nov17.181310.17548@husc15.harvard.edu>
  8. Organization: Rutgers Univ., New Brunswick, N.J.
  9. Lines: 26
  10.  
  11. In article <1992Nov17.181310.17548@husc15.harvard.edu>, Eric Blom writes:
  12.  
  13. > 2
  14. > 11
  15. > 12
  16. > 122
  17. > 12211
  18. > 1221121
  19. > 1221121221
  20. > ...
  21. > (eventually) 1221121221221121122121...
  22.  
  23. It looks like we have S_1=2, S_2=11, S_3=12, and S_n=S_{n-1}+R(S_{n-3}),
  24. where the "+" symbolizes string concatenation and R(S) is the reverse of
  25. the string S.
  26.  
  27. > Prove that the infinite sequence never repeats.
  28.  
  29. The density of 1's approaches an irrational number in the limit; if
  30. the sequence eventually repeated, the density would converge to a
  31. rational number.  I'll post the details when I have more time, but
  32. the basic idea is that the number of 1's is characterizd by a third-
  33. order difference equation as is the total number of characters, so
  34. solve and take the ratio.
  35. -- 
  36. Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
  37.