chuck@bunker.UUCP (Chuck Heaton) (08/20/84)
Hi. Douglas Hoffstadter (sp.?) in his book "Godel, Escher, Bach", (a wonderful work if you aren't familiar with it) discussed a function with some rather intriguing properties. The function was defined as follows: h[0] = 0; h[k] = k - h[h[k-1]]; Actually, it is the differences, g[n] = h[n] - h[n-1] (n>0) that are most interesting. You can play with the patterns generated yourself, but what I am concerned with is a definition, recursive or otherwise, for g[] that does NOT involve h[]. Any ideas ??? I fooled around with this for awhile and gave up. Either I have some mental block here, or it realy is a difficult problem. Any responses to this newsgroup would be greatly appreciated. Also, any other such 'fun' things would be welcomed with open arms (& pencil, paper, computer, .....). Thanks. Chuck Heaton
pete@arizona.UUCP (P. Downey) (08/22/84)
Chuck Heaton asked about the behavior of the recurrence h(0) = 0; h(k) = k - h(h(k-1)) which appears in Hofstadter's "Goedel, Escher, Bach". There is an interesting answer, details of which can be found in a paper soon to appear: Downey, P.J. and R.E. Griswold. On a family of nested recurrences. "Fibonacci Quarterly", (Nov 1984). Here's the bottom line; for complete details see the paper or mail me for a copy. Let R stand for the "golden ratio" (sqrt(5)+1)/2 and let P be its reciprocal. Let [ x ] denote the integer part of the number x, i.e., floor(x). Then h(k) = [ P*(k+1) ]. The values of the first difference function g(k) = h(k) - h(k-1) are either zero or 1. The sequence of k for which g(k)=1 form a "Beatty sequence" [R],[2*R],[3*R],...
lsmith@noscvax.UUCP (Larry H. Smith) (08/25/84)
- It is easy to prove the following facts about g and h: g[i] is 0 or 1 for all i>0. h[i]/i converges to .61... = (sqrt(5)-1)/2. I have not read "Godel, Escher, Bach." I wonder if these facts are relevant to his purpose in introducing the sequence, does he mention them? Larry Smith, lsmith@nosc-cod.