The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005206 Hofstadter G-sequence: a(n) = n - a(a(n-1)). (Formerly M0436) 64
 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, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent 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 From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start) A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):   14  15  16  17  18  19  20  21     \ /   /     \ /     \ /   /      9  10      11      12  13       \ /       /         \ /        6       7           8         \     /           /          \   /           /           \ /           /            4           5             \         /              \       /               \     /                \   /                 \ /                  3                 /                2             \ /              1 To construct the tree: node n is connected with the node a(n) below      n     /   a(n) For example, since a(7) = 4:     7    /   4 If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct       /      x   \ /    x can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,               /              x       /   \ /      x     x   \ /     /    x     x     \   /      \ /       x 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.) (End) The number n appears A001468(n) times; A001468(n) = floor((n+1)*Phi) - floor(n*Phi) with Phi = (1 + sqrt 5)/2. - Philippe Deléham, Sep 22 2005 Number of positive Wythoff A-numbers A000201 not exceeding n. - N. J. A. Sloane, Oct 09 2006 Number of positive Wythoff B-numbers < A000201(n+1). - N. J. A. Sloane, Oct 09 2006 Also a(n) = A293688(n)/(n+1) for n >= 0; i.e., for n=0, a(0)=0/1=0; for n=1, a(1)=2/2=1; for n=2, a(2)=3/3=1, etc. - Enrique Navarrete, Oct 15 2017 REFERENCES Martin Griffiths, A formula for an infinite family of Fibonacci-word sequences, Fib. Q., 56 (2018), 75-80. D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 0..20000 (the first 1000 terms were found by T. D. Noe) M. Celaya and F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013. F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1. 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. Gault and M. Clint, "Curiouser and curiouser said Alice. Further reflections on an interesting recursive function, Intern. J. Computer. Math., 26 (1988), 35-43. (Annotated scanned copy) 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. Vincent Granville and Jean-Paul Rasson, A strange recursive relation, J. Number Theory 30 (1988), no. 2, 238--241. MR0961919(89j:11014). J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161. Nick Hobson, Python program for this sequence D. R. Hofstadter, Eta-Lore [Cached copy, with permission] D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission] D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991 C. Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273. P. Letouzey, Hofstadter's problem for curious readers, Technical Report, 2015. Mustazee Rahman, A Combinatorial interpretation of Hofstadter's G-sequence, arXiv:1105.1718 [math.CO], 2011-2013. B. Schoenmakers, A tight lower bound for top-down skew heaps, Information Processing Letters, 61(5): 279-284, 14 March 1997. Torsten Sillke, Floor Recurrences Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - N. J. A. Sloane, May 30 2009 Eric Weisstein's World of Mathematics, Hofstadter G-Sequence Wikipedia, Hofstadter sequence FORMULA 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. a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - Benoit Cloitre, Nov 27 2002 a(n) = A019446(n) - 1. - Reinhard Zumkeller, Feb 02 2012 a(n) = n - A060144(n+1). - Reinhard Zumkeller, Apr 07 2012 a(n) = Sum_{k=1..A072649(m)} A000045(m)*A213676(m,k): m=A000201(n+1). - Reinhard Zumkeller, Mar 10 2013 a(n + a(n)) = n. - Pierre Letouzey, Sep 09 2015 a(n) + a(a(n+1) - 1) = n. - Pierre Letouzey, Sep 09 2015 a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). - Pierre Letouzey, Sep 09 2015 MAPLE H:=proc(n) option remember; if n=0 then 0 elif n=1 then 1 else n-H(H(n-1)); fi; end proc: seq(H(n), n=0..76); MATHEMATICA a = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0] (* Second program: *) Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* Michael De Vlieger, Nov 13 2017 *) PROG (Haskell) a005206 n = a005206_list !! n a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list) -- Reinhard Zumkeller, Feb 02 2012, Aug 07 2011 (Haskell) a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1) -- Reinhard Zumkeller, Mar 10 2013 (PARI) first(n)=my(v=vector(n)); v=1; for(k=2, n, v[k]=k-v[v[k-1]]); concat(0, v) \\ Charles R Greathouse IV, Sep 02 2015 (MAGMA) [Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016 CROSSREFS Apart from initial terms, same as A060143. Cf. A123070. a(n):=Sum{k=1..n} h(k), n >= 1, with h(k):= A005614(k-1) and a(0):=0. a(n) = A(n+1) - (n+1), n >= 0, with Wythoff numbers A(n):= A000201(n). Cf. A060144, A019446, A072649, A213676. Sequence in context: A057363 A073869 A060143 * A309077 A057365 A014245 Adjacent sequences:  A005203 A005204 A005205 * A005207 A005208 A005209 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 20 06:31 EDT 2021. Contains 343121 sequences. (Running on oeis4.)