Hofstadter sequence
Encyclopedia
In mathematics
, a Hofstadter sequence is a member of a family of related integer sequences defined by non-linear recurrence relations.
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:
with the sequence {S(n)} defined as the positive integers not present in {R(n)}. The first few terms of these sequences are
The first few terms of this sequence are
The first few terms of this sequence are
The first few terms of these sequences are
The first few terms of the sequence are
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 mention of a meta-Fibonacci sequence in literature.
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.
Although the terms of the Q sequence seem to flow chaotically, like many meta-Fibonacci sequences its terms can be grouped into blocks of successive generations. In case of the Q sequence, the k-th generation has 2k members. 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.
Most of these findings are empirical observations, since virtually nothing has been proved rigorously about the Q sequence so far.
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).
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
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 Qr,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); 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
The first few terms of the W sequence are
For other values (r,s) the sequences sooner or later "die" i.e. there exists an n for which Qr,s(n) is undefined because n-Qr,s(n-r) < 1.
The family of Pinn Fi,j sequences is defined as follows:
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 Fi,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 F0,1 sequence are
The first few terms of this sequence are
This sequence acquired its name because John Horton Conway
offered a prize of $10,000 to anyone who could demonstrate a particular result about its asymptotic
behaviour. The prize, subsequently reduced to $1,000, was claimed by Collin Mallows. In private communication with Klaus Pinn, Hofstadter later claimed he had found the sequence and its structure some 10–15 years before Conway posed his challenge.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Hofstadter sequence is a member of a family of related integer sequences defined by non-linear recurrence relations.
Sequences presented in Gödel, Escher, Bach: an Eternal Golden Braid
The first Hofstadter sequences were described by Douglas Richard HofstadterDouglas Hofstadter
Douglas Richard Hofstadter is an American academic whose research focuses on consciousness, analogy-making, artistic creation, literary translation, and discovery in mathematics and physics...
in his book Gödel, Escher, Bach
Gödel, Escher, Bach
Gödel, Escher, Bach: An Eternal Golden Braid is a book by Douglas Hofstadter, described by his publishing company as "a metaphorical fugue on minds and machines in the spirit of Lewis Carroll"....
. 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 followswith 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, ...
- S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ...
Hofstadter G sequence
The Hofstadter G sequence is defined as followsThe 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, ...
Hofstadter H sequence
The Hofstadter H sequence is defined as followsThe 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, ...
Hofstadter Female and Male sequences
The Hofstadter Female (F) and Male (M) sequences are defined as followsThe 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, ...
- M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ...
Hofstadter Q sequence
The Hofstadter Q sequence is defined as followsThe 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, ...
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 mention of a meta-Fibonacci sequence in literature.
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.
Although the terms of the Q sequence seem to flow chaotically, like many meta-Fibonacci sequences its terms can be grouped into blocks of successive generations. In case of the Q sequence, the k-th generation has 2k members. 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.
Most of these findings are empirical observations, since virtually nothing has been proved rigorously about the Q sequence so far.
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).
Hofstadter-Huber Qr,s(n) family
20 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
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 Qr,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); 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, ...
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, ...
For other values (r,s) the sequences sooner or later "die" i.e. there exists an n for which Qr,s(n) is undefined because n-Qr,s(n-r) < 1.
Pinn Fi,j(n) family
In 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.The family of Pinn Fi,j sequences is defined as follows:
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 Fi,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 F0,1 sequence are
- 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, ...
Hofstadter-Conway $10,000 sequence
The Hofstadter-Conway $10,000 sequence is defined as followsThe 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, ...
This sequence acquired its name because John Horton Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
offered a prize of $10,000 to anyone who could demonstrate a particular result about its asymptotic
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
behaviour. The prize, subsequently reduced to $1,000, was claimed by Collin Mallows. In private communication with Klaus Pinn, Hofstadter later claimed he had found the sequence and its structure some 10–15 years before Conway posed his challenge.