%I A005206 M0436
%S A005206 0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,12,13,14,14,15,16,16,17,17,
%T A005206 18,19,19,20,21,21,22,22,23,24,24,25,25,26,27,27,28,29,29,30,30,31,32,
               32,
%U A005206 33,33,34,35,35,36,37,37,38,38,39,40,40,41,42,42,43,43,44,45,45,46,46,
               47
%N A005206 Hofstadter G-sequence: a(n)=n-a(a(n-1)).
%C A005206 Rule of construction for the sequence: a(n) = An, where An denotes the 
               Fibonacci antecessor to (or right shift of) n, which is found by 
               replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly 
               subtracting the largest Fibonacci number you can until nothing remains) 
               by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58)= 34 + 2 = 36. 
               - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
%C A005206 Comments from Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006.
%C A005206 "A recursively built tree structure can be obtained from the sequence 
               (see Hofstadter, p. 137):
%C A005206 14.15.16.17.18.19..20.21
%C A005206 .\./.../..\./...\./.../
%C A005206 ..9..10...11.....12.13
%C A005206 ...\./.../........\/
%C A005206 ....6...7.........8
%C A005206 .....\./......../
%C A005206 ......4.......5
%C A005206 ........\.../
%C A005206 ..........3
%C A005206 ......../
%C A005206 ......2
%C A005206 \.../
%C A005206 ..1
%C A005206 "To construct the tree: node n is connected with the node a(n) below
%C A005206 .. n
%C A005206 . /
%C A005206 a(n)
%C A005206 "For example, since a(7) = 4:
%C A005206 .. 7
%C A005206 . /
%C A005206 .4
%C A005206 "If the nodes of the tree are read from bottum-to-top, left-to-right, 
               one obtains the natural numbers: 1, 2, 3, 4, 5, 6, ... The tree has 
               a recursive structure, since the following construct
%C A005206 ...../
%C A005206 ....x
%C A005206 .\./
%C A005206 ..x
%C A005206 can be repeatedly added on top of its own ends, to construct the tree 
               from its root: e.g.
%C A005206 .............../
%C A005206 ..............x
%C A005206 ...../.....\./
%C A005206 ....x.......x
%C A005206 .\./......./
%C A005206 ..x......x.
%C A005206 ...\.../
%C A005206 .....x
%C A005206 "When moving from a node to a lower connected node, one is moving to 
               the parent. Parent node of n: floor((n+1)/tau). Left child of n: 
               floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/
               2. (See the Sillke link.)"
%C A005206 The number n appears A001468(n) times; A001468(n) = [ (n+1)*Phi] - [n*Phi] 
               with Phi = (1+sqrt 5)/2 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), 
               Sep 22 2005
%C A005206 Number of positive Wythoff A-numbers A000201 not exceeding n.
%C A005206 Number of positive Wythoff B-numbers < A000201(n+1).
%D A005206 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005206 D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further 
               reflections on an interesting recursive function, Internat. J. Computer 
               Math., 26 (1988), 35-43.
%D A005206 H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., Sequences associated with 
               t-ary coding of Fibonacci's rabbits, Fib. Quart., 15 (1977), 311-318.
%D A005206 V. Granville and J. P. Rasson, A strange recursive relation, J. Number 
               Theory, 30 (1988), 238-241.
%D A005206 J. Grytczuk, Another variation on Conway's recursive sequence, Discr. 
               Math. 282 (2004), 149-161.
%D A005206 D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random 
               House, 1980, p. 137.
%D A005206 Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 
               62-67. - from N. J. A. Sloane, May 30 2009
%H A005206 T. D. Noe, <a href="b005206.txt">Table of n, a(n) for n=0..1000</a>
%H A005206 Nick Hobson, <a href="a005206.py.txt">Python program for this sequence</
               a>
%H A005206 B. Schoenmakers, <a href="http://www.win.tue.nl/~berry/papers/lowskew.pdf">
               A tight lower bound for top-down skew heaps</a>, Information Processing 
               Letters, 61(5): 279-284, 14 March 1997.
%H A005206 Torsten Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/
               PUZZLES/floor-recurrence">Title?</a>
%H A005206 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               HofstadterG-Sequence.html">Link to a section of The World of Mathematics.</
               a>
%H A005206 <a href="Sindx_Ho.html#Hofstadter">Index entries for Hofstadter-type 
               sequences</a>
%H A005206 <a href="Sindx_Go.html#GEB">Index entries for sequences from "Goedel, 
               Escher, Bach"</a>
%F A005206 a(n)=floor((n+1)*tau)-n-1 where tau=(1+sqrt(5))/2; or a(n)=floor(sigma*(n+1)) 
               where sigma=(sqrt(5)-1)/2.
%F A005206 a(0)=0, a(1)=1, a(n)=n-a(floor(n/tau)). - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Nov 27 2002
%p A005206 H:=proc(n) option remember; if n=1 then 1 else n-H(H(n-1)); fi; end proc;
%Y A005206 Apart from initial terms, same as A060143. Cf. A123070.
%Y A005206 a(n):=sum(h(k), k=1..n), n>=1, with h(k):= A005614((k-1) and a(0):=0.
%Y A005206 a(n)=A(n+1)-(n+1), n>=0, with Wythoff numbers A(n):= A000201(n).
%Y A005206 Sequence in context: A057363 A073869 A060143 this_sequence A057365 A014245 
               A096386
%Y A005206 Adjacent sequences: A005203 A005204 A005205 this_sequence A005207 A005208 
               A005209
%K A005206 nonn,easy,nice
%O A005206 0,4
%A A005206 N. J. A. Sloane (njas(AT)research.att.com).