- Hofstadter sequence
In

mathematics , a**Hofstadter sequence**is a member of a family of related integer sequences defined by non-linearrecurrence relations .**equences presented in "Gödel, Escher, Bach: an Eternal Golden Braid"**The first Hofstadter sequences were described by Douglas Robert Hofstadter in his book "

Gödel, Escher, Bach ". In order of their presentation in chapter III on figures and background (Figure-Figure sequence) and chapter V on recursive structures and processes (remaining sequences), these sequences are:**Hofstadter Figure-Figure sequences**The Hofstadter Figure-Figure (R and S) sequences are defined as follows [

*Hofstadter (1980) p73*] [*mathworld|urlname = HofstadterFigure-FigureSequence |title = Hofstadter Figure-Figure Sequence*]:$egin\{align\}R(1)=1\; ;\; S(1)=2\; \backslash R(n)=R(n-1)+S(n-1),\; quad\; n1.end\{align\}$

with the sequence {S("n")} defined as the positive integers not present in {R("n")}. The first few terms of these sequences are

:R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... OEIS|id=A005228:S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... OEIS|id=A030124

**Hofstadter G sequence**The Hofstadter G sequence is defined as followsHofstadter (1980) p137] [

*mathworld|urlname = HofstadterG-Sequence |title = Hofstadter G-Sequence*]:$egin\{align\}G(0)=0\; \backslash G(n)=n-G(G(n-1)),\; quad\; n0.end\{align\}$

The first few terms of this sequence are

:0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... OEIS|id=A005206

**Hofstadter H sequence**The Hofstadter H sequence is defined as follows [

*mathworld|urlname = HofstadterH-Sequence |title = Hofstadter H-Sequence*]:$egin\{align\}H(0)=0\; \backslash H(n)=n-H(H(H(n-1))),\; quad\; n0.end\{align\}$

The first few terms of this sequence are

:0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... OEIS|id=A005374

**Hofstadter Female and Male sequences**The Hofstadter Female (F) and Male (M) sequences are defined as follows [

*mathworld|urlname = HofstadterMale-FemaleSequences |title = Hofstadter Male-Female Sequences*]:$egin\{align\}F(0)=1\; ;\; M(0)=0\; \backslash F(n)=n-M(F(n-1)),\; quad\; n0\; \backslash M(n)=n-F(M(n-1)),\; quad\; n0.end\{align\}$

The first few terms of these sequences are

:F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... OEIS|id=A005378:M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... OEIS|id=A005379

**Hofstadter Q sequence**The Hofstadter Q sequence is defined as follows [

*mathworld|urlname = HofstadtersQ-Sequence |title = Hofstadter's Q-Sequence*]:$egin\{align\}Q(1)=Q(2)=1,\; \backslash Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)),\; quad\; n2.end\{align\}$

The first few terms of the sequence are

:1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... OEIS|id=A005185

Hofstadter named the terms of the sequence "Q numbers"; thus the Q number of 6 is 4. The presentation of the Q sequence in Hofstadter's book is actually the first known mentioning of a

meta-Fibonacci sequence in literature. [*Emerson (2006) p1, p7*]While the terms of the

Fibonacci sequence are determined by summing the two preceding terms, the two preceding terms of a Q number determine how far to go back in the Q sequence to find the two terms to be summed. The indexes of the summation terms thus depend on the Q sequence itself.Q(1), the first element of the sequence (the first Q number) is never the term of any summation in the course of calculating later elements of the sequence; its only use is to provide an index to refer to the second element of the sequence. [

*Pinn (1999) pp5-6*]Although the terms of the Q sequence seem to flow chaoticPinn (1999) p3] [

*Pinn (2000) p1*] [*Emerson (2006) p7*] , like many meta-Fibonacci sequences its terms can be grouped into blocks of successive generations. [*Pinn (1999) pp3-4*] [*Balamohan et al. (2007) p19*] In case of the Q sequence, the "k"-th generation has 2^{"k"}members. [*Pinn (1999) Abstract, p8*] Furthermore, with "g" being the generation that a Q number belongs to, the two terms to be summed to calculate the Q number, called its parents, reside by far mostly in generation ("g"-1) and only a few in generation ("g"-2), but never in an even older generation. [*Pinn (1999) pp4-5*]Most of these findings are empirical observations since virtually nothing has been proved rigorously about the Q sequence so far.Pinn (1999) p2] [

*Pinn (2000) p3*] Balamohan et al. (2007) p2]It is specifically unknown if the sequence is well-defined for all "n", that is, if the sequence "dies" at some point because its generation rule tries to refer to terms which would conceptually sit left of the first term Q(1). [

*Emerson (2006) p7*]**Generalizations of the Q sequence****Hofstadter-Huber Q**_{r,s}(n) family20 years after Hofstadter first described the Q sequence, he and

Greg Huber used the character Q to name the generalization of the Q sequence towards a family of sequences, and renamed the original Q sequence of his book to U sequence.The original Q sequence is generalized by replacing ("n"-1) and ("n"-2) by ("n"-"r") and ("n"-"s"), respectively.

This leads to the sequence family

:$Q\_\{r,s\}(n)\; =\; egin\{cases\}1\; ,\; quad\; 1\; le\; n\; le\; s,\; \backslash Q\_\{r,s\}(n-Q\_\{r,s\}(n-r))+Q\_\{r,s\}(n-Q\_\{r,s\}(n-s)),\; quad\; n\; s,end\{cases\}$

where s≥2 and r<s.

With ("r","s") = (1,2), the original Q sequence is a member of this family. So far, only three sequences of the family Q

_{r,s}are known, namely the U sequence with ("r","s") = (1,2) (which is the original Q sequence); the V sequence with (r,s) = (1,4); [*Balamohan et al. (2007) full article*] and the W sequence with (r,s) = (2,4). Only the V sequence, which does not behave as chaotically as the others, is proven not to "die". Similar to the original Q sequence, virtually nothing has been proved rigorously about the W sequence to date.The first few terms of the V sequence are

:1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... OEIS|id=A063882

The first few terms of the W sequence are

:1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... OEIS|id=A087777

For other values ("r","s") the sequences sooner or later "die" i.e. there exists an "n" for which "Q

_{r,s}(n)" is undefined because "n-Q_{r,s}(n-r) < 1".**Pinn F**_{i,j}(n) familyIn 1998,

Klaus Pinn , scientist at University of Münster (Germany) and in close communication with Hofstadter, suggested another generalization of Hofstadter's Q sequence which Pinn called F sequences.Pinn (2000) p16]The family of Pinn F

_{i,j}sequences is defined as follows::$F\_\{i,j\}(n)\; =\; egin\{cases\}1\; ,\; quad\; n=1,2,\; \backslash F\_\{i,j\}(n-i-F\_\{i,j\}(n-1))+F\_\{i,j\}(n-j-F\_\{i,j\}(n-2)),\; quad\; n\; 2.end\{cases\}$

Thus Pinn introduced additional constants "i" and "j" which shift the index of the terms of the summation conceptually to the left (that is, closer to start of the sequence).

Only F sequences with ("i","j") = (0,0), (0,1), (1,0), and (1,1), the first of which represents the original Q sequence, appear to be well-defined. Unlike Q(1), the first elements of the Pinn F

_{i,j}(n) sequences are terms of summations in calculating later elements of the sequences when any of the additional constants is 1.The first few terms of the Pinn F

_{0,1}sequence are:1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, ... OEIS|id=A055748

**Hofstadter-Conway $10,000 sequence**The Hofstadter-Conway $10,000 sequence is defined as follows [

*mathworld|urlname = Hofstadter-Conway10000-DollarSequence |title = Hofstadter-Conway $10,000 Sequence*]:$egin\{align\}a(1)=a(2)=1,\; \backslash a(n)=a(a(n-1))+a(n-a(n-1)),\; quad\; n2.end\{align\}$

The first few terms of this sequence are

:1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... OEIS|id=A004001

This sequence acquired its name because

John Horton Conway offered a prize of $10,000 to anyone who could demonstrate a particular result about itsasymptotic behaviour. The prize, subsequently reduced to $1,000, was claimed byCollin Mallows . [*[*] In private communication with*http://el.media.mit.edu/logo-foundation/pubs/papers/easy_as_11223.html Easy as 1 1 2 2 3*] ; Michael TempelKlaus Pinn , Hofstadter later pointed out he had found the sequence and its structure some 10-15 years before Conway posed his challenge.**Notes****References***Citation

last1 = Balamohan

first1 = B.

last2 = Kuznetsov

first2 = A.

last3 = Tanny

first3 = Stephan M.

title = On the Behaviour of a Variant of Hofstadter's Q-Sequence

journal = Journal of Integer Sequences

volume = 10

issue = 7

publisher = University of Waterloo

location = Waterloo, Ontario (Canada)

date =2007-06-27

url = http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.pdf

issn = 1530-7638 .

*Citation

last1 = Emerson

first1 = Nathanial D.

title = A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions

journal = Journal of Integer Sequences

volume = 9

issue = 1

publisher = University of Waterloo

location = Waterloo, Ontario (Canada)

date =2006-03-17

url = http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.pdf

issn = 1530-7638 .

*citation

last = Hofstadter

first = Douglas

authorlink = Douglas Hofstadter

title = Gödel, Escher, Bach: an Eternal Golden Braid

publisher = Penguin Books

date = 1980

isbn = 0140055797.

*Citation

last1 = Pinn

first1 = Klaus

contribution = Order and Chaos in Hofstadter's Q(n) Sequence

journal = Complexity

volume = 4

pages = 41–46

year = 1999

id = arxiv|chao-dyn|9803012v2 .

*Citation

last1 = Pinn

first1 = Klaus

contribution = A Chaotic Cousin of Conway's Recursive Sequence

journal = Experiment. Math.

volume = 9

issue = 1

pages = 55–66

year = 2000

id = arxiv|cond-mat|9808031 .

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Hofstadter-Folge**— In der Mathematik sind die Hofstadter Folgen Angehörige einer Familie ganzzahliger Folgen, die durch nichtlineare Differenzengleichungen beschrieben werden. Inhaltsverzeichnis 1 Hofstadter Folgen aus dem Buch Gödel, Escher, Bach 1.1 Hofstadters… … Deutsch Wikipedia**Douglas R. Hofstadter**— Douglas Hofstadter (2006 in Stanford) Douglas Richard Hofstadter (* 15. Februar 1945 in New York City … Deutsch Wikipedia**List of mathematics articles (H)**— NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… … Wikipedia**Q-Folge**— In der Mathematik sind die Hofstadter Folgen Angehörige einer Familie ganzzahliger Folgen, die durch nichtlineare Differenzengleichungen beschrieben werden. Inhaltsverzeichnis 1 Hofstadter Folgen aus dem Buch Gödel, Escher, Bach: ein Endloses… … Deutsch Wikipedia**Fluid Concepts and Creative Analogies**— Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought is a 1995 book by Douglas Hofstadter and other members of the Fluid Analogies Research Group exploring the mechanisms of intelligence through computer … Wikipedia**Existence (Philosophy of) 1**— Philosophy of existence 1 Heidegger Jacques Taminiaux At the very outset and up to the end, the long philosophical journey of Martin Heidegger (1889–1976) remained oriented by a single question, the question of Being, the Seinsfrage. This does… … History of philosophy**Gödel number**— In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well formed formula of some formal language a unique natural number called its Gödel number. The concept was first used by Kurt Gödel for the proof of his… … Wikipedia**Protein music**— is a musical genre or form, composed by converting protein sequences, such as genes, to musical notes. Contents 1 Theory 2 Practice 3 See also 4 Notes … Wikipedia**Nucleic acid notation**— The nucleic acid notation currently in use was first formalized by the International Union of Pure and Applied Chemistry (IUPAC) in 1970.[1] This universally accepted notation uses the Roman characters G, C, A, and T, to represent the four… … Wikipedia**Rubik's Cube**— Other names Magic Cube … Wikipedia