Hofstadter sequence
In mathematics, the Hofstadter sequences are members of a family of integer sequences, which are described by nonlinear difference equations.
- 2.1 Hofstadter -Huber- Qr, s ( n ) family
- 2.2 Pin -Fi, j ( n ) family
Hofstadter sequences from the book Godel, Escher, Bach
The first Hofstadter sequences were from Douglas Richard Hofstadter in his book Gödel, Escher, Bach: an Endless braided belt described. In the order of their introduction in Chapter III: Figure and background ( figure - figure -series ) and Chapter V: Recursive Structures and Processes (remaining episodes):
Hofstadter's figure - figure sequences
Hofstadter's figure - figure (also: R- and S- ) consequences are described as follows:
The sequence { S ( n)} is described here as a result of positive integers that are not included in the sequence { R ( n)}. The first numbers of these sequences are:
Hofstadter's G- sequence
Hofstadter G sequence is described as follows:
The first numbers in this sequence are:
Hofstadter's H -Series
Hoftstadters H sequence is described as follows:
The first numbers in this sequence are:
Hofstadter's " married consequences "
Hofstadter's " married consequences " are described as follows:
These consequences are in the English language according to the U.S. original edition of Hofstadter's book as "Female (F) and Male (M) sequences" refers to ( dt male and female episodes); the designation as a married consequences does not appear in the original English text and translation is a compromise. However, we can of Hofstadter's consent be assumed with this name transfer because he speaks German and has seen the German edition of his book.
The first numbers of these sequences are:
Hofstadter Q sequence
Hofstadter Q sequence is described as follows:
The first numbers in this sequence are:
Hofstadter calls the elements of this sequence Q- numbers; the Q- number of 6 is therefore 4 The representation of Q- sequence in Hofstadter's book is the first known mention of a meta- Fibonacci sequence in the literature.
While the elements of the Fibonacci sequence can be determined by summing the two respective preceding elements that determine two respective preceding elements of Q- number to the number of elements should be returned in the Q- sequence in order to access the two addends. Therefore, the Indice these two terms depend on the Q- sequence itself.
Q (1 ), the first element of the sequence (the first Q- number) is not involved as a summand to the calculation of further elements of the sequence in the course of the calculation of elements of the Q sequence; It is only used to calculate the index with which the second element of the sequence of reference.
Although the elements of the Q -series seem chaotic to develop their elements as that of many meta- Fibonacci sequences can be grouped into successive blocks, which designates the literature as generations. In the case of Q result, the k-th generation 2k members. In addition, if g represents the generation to which it belongs a Q number, then the summands of the Q number which are referred to as parent, located far the most common in the generation of ( G-1) and only a few in the generation ( g -2), but never in an even earlier generation.
Most of these findings are empirical observations, since virtually none of the properties of the Q- sequence are shown in the strict sense.
It is particularly unknown whether the sequence is well-defined for all n, that is, whether the sequence terminates somewhere, because their production usually tries to refer to elements that are theoretically left of the first element of Q would have to be found (1).
The Q- sequence generalizations
Hofstadter -Huber- Qr, s ( n ) family
Twenty years after Hofstadter had described the Q- sequence for the first time, he and Greg Huber used the letter Q to denote a generalization of Q- sequence to a family of sequences. The original Q - sequence of his book named them in a U- sequence.
The original Q sequence is generalized by (n-1 ) and (n -2 ) are replaced respectively by (NR) and ( ns).
This leads to the sequence family
Where s ≥ 2 and r < s.
With (r, s) = (1,2) is the original Q -Series a member of this family. So far, namely the U- sequence with (r, s) = (1,2) ( the original Q - sequence group), the V-Series with (r, s ) are only three episodes of the family Qr, s known = (1,4) and the W- sequence with (r, s) = (2,4). Only for the V-Series, which does not behave as chaotic as the others, it is proven that it does not break off. Similar to the original Q- sequence to date, no properties of the W -series have been proved in the strict sense practically.
The first numbers of the V-Series are:
The first numbers of the W -series are:
For other values of (r, s) from the consequences sooner or later break down, that is, there exists an n for which Qr, s ( n) is not defined because n- Qr, s ( nr) < 1
Pinn -Fi, j ( n ) family
Of 1998, Klaus Pinn, scientists at the Westfälische Wilhelms-Universität in Münster and in close contact with Hofstadter, another generalization of Hofstadter's Q- sequence before that called Pin F sequences.
The Pinn -Fi, j family is described as follows:
So Pinn introduced the additional constants i and j, the conceptual shifts the index of the summands to the left (closer to the beginning result ).
Only the F- sequences with (i, j ) = ( 0,0), (0,1 ), ( 1,0) and (1,1), the first of which is the original Q -series, well-defined appear. Other than Q (1) are the first elements of the pin- Fi, j ( n ) sequences addend in the calculation result of further elements, if any of the additional constant is 1.
The first numbers of Pinus F0 ,1- sequence are:
Hofstadter - Conway $ 10,000 sequence
The Hofstadter - Conway $ 10,000 sequence is described as follows:
The first numbers in this sequence are:
This episode was named by a ausgelobten by John Horton Conway prize of $ 10,000 to anyone who could show certain characteristics of their asymptotic behavior. The meantime reduced to $ 1,000 in prize money was awarded Collin Mallows. Hofstadter later said that he had found the sequence and structure about 10-15 years before the competition on the Conway price.