Hofstadter series

In mathematics , the Hofstadter sequences are members of a family of integer sequences that are described by nonlinear difference equations .

Hofstadter episodes from the book Gödel, Escher, Bach

The first Hofstadter episodes were described by Douglas Richard Hofstadter in his book Gödel, Escher, Bach : an Endless Braided Band . In the order of their introduction in chapter III: figure and background (figure-figure sequence) and chapter V: recursive structures and processes (remaining sequences):

Hofstadter's figure-figure sequences

Hofstadter's figure-figure (also: R and S ) sequences are described as follows:

${\displaystyle {\begin{aligned}R(1)&=1\ ;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}}$

The sequence {S ( n )} is described as a sequence of positive integers that are not contained in the sequence {R ( n )}. The first numbers 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, ... (sequence A005228 in OEIS )

S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... (sequence A030124 in OEIS )

Hofstadter's G-Series

Hofstadter's G-sequence is described as follows:

${\displaystyle {\begin{aligned}G(0)&=0\\G(n)&=n-G(G(n-1)),\quad n>0.\end{aligned}}}$

The first numbers in this sequence are:

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... (sequence A005206 in OEIS )

Hofstadter's H-sequence

Hoftstadter's H-sequence is described as follows:

${\displaystyle {\begin{aligned}H(0)&=0\\H(n)&=n-H(H(H(n-1))),\quad n>0.\end{aligned}}}$

The first numbers in this sequence are:

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... (sequence A005374 in OEIS )

Hofstadter's "married episodes"

Hofstadter's "married episodes" are described as follows:

${\displaystyle {\begin{aligned}F(0)&=1\ ;\ M(0)=0\\F(n)&=n-M(F(n-1)),\quad n>0\\M(n)&=n-F(M(n-1)),\quad n>0.\end{aligned}}}$

These consequences are "corresponding in English of the US original edition of Hofstadter's book as sequences Female (F) and Male (M) " (dt.  Male and female consequences ) called; the designation as married episodes does not appear in the original English text and is a translation compromise. Nevertheless, Hofstadter's consent to this transfer of names can be assumed, since he speaks German and has looked through the German edition of his book.

The first numbers 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, ... (sequence A005378 in OEIS )

M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (sequence A005379 in OEIS )

Hofstadter's Q-sequence

Hofstadter's Q-sequence is described as follows:

${\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)),\quad n>2.\end{aligned}}}$

The first numbers in this sequence are:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (sequence A005185 in OEIS )

Hofstadter names the elements of these sequence numbers; the Q number of 6 is therefore 4. The representation of the sequence in Hofstadter's book is the first known mention of a meta-Fibonacci sequence in literature. ${\displaystyle Q}$ ${\displaystyle Q}$

While the elements of the Fibonacci sequence are determined by adding up the two preceding elements, the two preceding elements of a number determine by how many elements in the Q-sequence you should go back to get to the two summands. Therefore the indices of these two summands depend on the sequence itself. ${\displaystyle Q}$ ${\displaystyle Q}$

${\displaystyle Q(1)}$, the first element of the sequence (the first number), is never involved in the calculation of elements of the Q sequence as a summand in the calculation of further elements of the sequence; it is used alone to compute the index used to refer to the second element of the sequence. ${\displaystyle Q}$

Although the elements of the sequence appear to evolve chaotically, like those of many meta-Fibonacci sequences, their elements can be grouped into successive blocks, which the literature calls generations . In the case of the -sequence, the -th generation has members. If also indicates the generation to which a number belongs, then the summands of this number, which are referred to as parents , are by far most frequently located in the generation ( ) and only a few in the generation ( ), but never in one even earlier generation. ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$ ${\displaystyle g}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle g-1}$ ${\displaystyle g-2}$

Most of these statements are empirical observations, as virtually none of the properties of the sequence have been proven in the strict sense. ${\displaystyle Q}$

In particular, it is unknown whether the sequence is well-defined for everyone , that is, whether the sequence breaks off somewhere because its production rule tries to refer to elements that should conceptually be to the left of the first element . ${\displaystyle n}$ ${\displaystyle Q(1)}$

Generalizations of the Q-sequence

Hofstadter-Huber-Q _{r, s} (n) family

Twenty years after Hofstadter first described the episode, he and Greg Huber used the letter to denote a generalization of the episode into a family of episodes. They renamed the original episode from his book to episode. ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle U}$

The original sequence is generalized by replacing ( ) and ( ) with ( ) and ( ), respectively. ${\displaystyle Q}$ ${\displaystyle n-1}$ ${\displaystyle n-2}$ ${\displaystyle n-r}$ ${\displaystyle n-s}$

This leads to the sequence family

${\displaystyle Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),\quad n>s,\end{cases}}}$

where and is. ${\displaystyle s\geq 2}$ ${\displaystyle r<s}$

With the original Q-sequence is a member of this family. So far only three episodes of the family are known, namely the episode with (which is the original episode), the episode with and the episode with . Only for the episode, which is not as chaotic as the others, has been proven that it does not break off. Similar to the original sequence, practically no properties of the sequence in the strict sense have been proven to date . ${\displaystyle (r,s)=(1,2)}$ ${\displaystyle Q_{r,s}}$ ${\displaystyle U}$ ${\displaystyle (r,s)=(1,2)}$ ${\displaystyle Q}$ ${\displaystyle V}$ ${\displaystyle (r,s)=(1,4)}$ ${\displaystyle W}$ ${\displaystyle (r,s)=(2,4)}$ ${\displaystyle V}$ ${\displaystyle Q}$ ${\displaystyle W}$

The first numbers in the sequence are: ${\displaystyle V}$

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (sequence A063882 in OEIS )

The first numbers in the sequence are: ${\displaystyle W}$

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... (sequence A087777 in OEIS )

For other values ​​of the sequences break off sooner or later, i.e. i.e., there is one for which is not defined because . ${\displaystyle (r,s)}$ ${\displaystyle n}$ ${\displaystyle Q_{r,s}(n)}$ ${\displaystyle n-Q_{r,s}(n-r)<1}$

Pinn-F _{i, j} (n) family

1998 beat Klaus Pinn , scientists at the Westphalian Wilhelms University in Muenster and in close contact with Hofstadter, another generalization of Hofstadter's episode before that Pinn -Follow called. ${\displaystyle Q}$ ${\displaystyle F}$

The Pinn family is described as follows: ${\displaystyle F_{i,j}}$

${\displaystyle F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\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}}}$

So Pinn introduced the additional constants and , which conceptually shift the index of the summands to the left (i.e. closer to the beginning of the sequence). ${\displaystyle i}$ ${\displaystyle j}$

Only the sequences with and , the first of which is the original sequence, appear well-defined. In contrast to this , the first elements of the Pinn- sequences are summands when calculating further sequence elements if one of the additional constants is 1. ${\displaystyle F}$ ${\displaystyle (i,j)=(0,0),(0,1),(1,0)}$ ${\displaystyle (1,1)}$ ${\displaystyle Q}$ ${\displaystyle Q(1)}$ ${\displaystyle F_{i,j}(n)}$

The first numbers of Pinn's sequence are: ${\displaystyle F_{0,1}}$

1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, ... (sequence A055748 in OEIS )

Hofstadter-Conway-10,000-Dollar-Series

The Hofstadter-Conway $ 10,000 series is described as follows:

${\displaystyle {\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a(a(n-1))+a(n-a(n-1)),\quad n>2.\end{aligned}}}$

The first numbers in this sequence are:

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... (sequence A004001 in OEIS )

This episode got its name from a $ 10,000 award given by John Horton Conway to anyone who could display certain features of its asymptotic behavior. The prize money, which has now been reduced to $ 1,000, was awarded to Collin Mallows . Hofstadter later stated that he had found the sequence and its structure about 10-15 years before the Conway Prize was announced.

literature

• B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behavior of a Variant of Hofstadter's Q-Sequence . In: Journal of Integer Sequences . tape 10 , no. 7 . University of Waterloo, 2007, ISSN  1530-7638 ( cs.uwaterloo.ca [PDF]).
• Nathanial D. Emerson : A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions . In: Journal of Integer Sequences . tape 9 , no. 1 . University of Waterloo, 2006, ISSN  1530-7638 ( cs.uwaterloo.ca [PDF]).
• Douglas Richard Hofstadter: Gödel, Escher, Bach: to Eternal Golden Braid . Vintage Books, New York 1980, ISBN 0-465-02656-7 .
• Douglas Richard Hofstadter: Gödel, Escher, Bach: an endless braided ribbon . 11th edition. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X .
• Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 41-46 , arxiv : chao-dyn / 9803012v2 .
• Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence . In: Experimental Mathematics . tape 9 , no. 1 , 2000, pp. 55-66 , arxiv : conat / 9808031 .
• S. Plouffe, Neil J.A. Sloane: The Encyclopedia of Integer Sequences . Academic Press, San Diego 1995, ISBN 0-12-558630-2 .
• Neil J.A. Sloane: The On-Line Encyclopedia of Integer Sequences . In: Notices of the American Mathematical Society . tape 50 , no. 8 , 2003, p. 912 ( ams.org [PDF; 92 kB ]).

Individual evidence

1. ↑ Douglas Richard Hofstadter: Gödel, Escher, Bach: an endless braided band . 11th edition. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X , p. 79 .
2. ↑ Mathworld: Hofstadter Figure-Figure Sequence
3. ^ ^{A b c} Douglas Richard Hofstadter: Gödel, Escher, Bach: an endless braided band . 11th edition. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X , p. 148 .
4. ^ Mathworld: Hofstadter G-Sequence
5. ^ Mathworld: Hofstadter H-Sequence
6. ^ Mathworld: Hofstadter Male-Female Sequences
7. ^ Douglas Richard Hofstadter: Gödel, Escher, Bach: an Eternal Golden Braid . Vintage Books , New York, NY, USA 1980, ISBN 0-465-02656-7 , pp. 137 .
8. ↑ Douglas Richard Hofstadter: Gödel, Escher, Bach: an endless braided band . 11th edition. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X , p. 820 .
9. ^ ^{A b c} Douglas Richard Hofstadter: Gödel, Escher, Bach: an endless braided band . 11th edition. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X , p. 149 .
10. ^ Mathworld: Hofstadter's Q-Sequence
11. ^ ^{A b} Nathanial D. Emerson : A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions . In: Journal of Integer Sequences . tape 9 , no. 1 . University of Waterloo, 2006, ISSN  1530-7638 , pp. 1, 7 ( cs.uwaterloo.ca [PDF]).
12. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 5-6 , arxiv : chao-dyn / 9803012v2 .
13. ↑ ^{a b} Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 3 , arxiv : chao-dyn / 9803012v2 .
14. ↑ Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence . In: Experimental Mathematics . tape 9 , no. 1 , 2000, pp. 1 , arxiv : conat / 9808031 .
15. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 3-4 , arxiv : chao-dyn / 9803012v2 .
16. ↑ B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behavior of a Variant of Hofstadter's Q Sequence . In: Journal of Integer Sequences . tape 10 , no. 7 . University of Waterloo, June 27, 2007, ISSN  1530-7638 , p. 19 ( cs.uwaterloo.ca [PDF]).
17. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. Overview, 8 , arxiv : chao-dyn / 9803012v2 .
18. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 4-5 , arxiv : chao-dyn / 9803012v2 .
19. ↑ ^{a b} Klaus Pinn: Order and Chaos in Hofstadter's Q (n) Sequence . In: Complexity . tape 4 , 1999, p. 2 , arxiv : chao-dyn / 9803012v2 .
20. ↑ Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence . In: Experimental Mathematics . tape 9 , no. 1 , 2000, pp. 3 , arxiv : conat / 9808031 .
21. ↑ ^{a b c d e f g h i} B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behavior of a Variant of Hofstadter's Q-Sequence . In: Journal of Integer Sequences . tape 10 , no. 7 . University of Waterloo, June 27, 2007, ISSN  1530-7638 , p. 2 ( cs.uwaterloo.ca [PDF]).
22. ^ Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions . In: Journal of Integer Sequences . tape 9 , no. 1 . University of Waterloo, 2006, ISSN  1530-7638 , pp. 7 ( cs.uwaterloo.ca [PDF]).
23. ↑ B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behavior of a Variant of Hofstadter's Q Sequence . In: Journal of Integer Sequences . tape 10 , no. 7 . University of Waterloo, June 27, 2007, ISSN  1530-7638 ( cs.uwaterloo.ca [PDF]).
24. ↑ ^{a b c} Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence . In: Experimental Mathematics . tape 9 , no. 1 , 2000, pp. 16 , arxiv : conat / 9808031 .
25. ^ Mathworld: Hofstadter-Conway $ 10,000 Sequence
26. ↑ Michael Tempel: Easy as 1 1 2 2 3 ( Memento of the original from March 2, 2008 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. .