login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005206 Hofstadter G-sequence: a(n)=n-a(a(n-1)).
(Formerly M0436)
43
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 natural numbers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the following 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) = [ (n+1)*Phi] - [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

Rahman's abstract: "We give a combinatorial interpretation of a classical meta-Fibonacci sequence defined by G(n) = n - G(G(n-1)) with the initial condition G(1) = 1, which appears in Hofstadter's 'Godel, Escher, Bach: An Eternal Golden Braid'. The interpretation is in terms of an infinite labelled tree. We then show a few corollaries about the behaviour of the sequence G(n) directly from the interpretation." - Jonathan Vos Post, May 09 2011

a(n) = n - A060144(n+1). - Reinhard Zumkeller, Apr 07 2012

REFERENCES

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.

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.

V. Granville and J. P. Rasson, A strange recursive relation, J. Number Theory, 30 (1988), 238-241.

J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.

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).

Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - from N. J. A. Sloane, May 30 2009

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, F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153, 2013

Nick Hobson, Python program for this sequence

Mustazee Rahman, A Combinatorial interpretation of Hofstadter's G-sequence, May 9, 2011.

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

Eric Weisstein's World of Mathematics, Hofstadter G-Sequence

Wikipedia, Hofstadter sequence

Index entries for Hofstadter-type sequences

Index entries for sequences from "Goedel, Escher, Bach"

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) = sum(A000045(m)*A213676(m,k): m=A000201(n+1), k=1..A072649(m)). - Reinhard Zumkeller, Mar 10 2013

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] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0]

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

CROSSREFS

Apart from initial terms, same as A060143. Cf. A123070.

a(n):=sum(h(k), k=1..n), 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).

Sequence in context: A057363 A073869 A060143 * A057365 A014245 A096386

Adjacent sequences:  A005203 A005204 A005205 * A005207 A005208 A005209

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified September 19 03:51 EDT 2014. Contains 246967 sequences.