In mathematics, a Hofstadter sequence is a member of a family of related integer sequences defined by non-linear recurrence relations.
defined as a strictly increasing series of positive integers not present in
The indices of the summation terms thus depend on the Q sequence itself.
[13][14] In case of the Q sequence, the k-th generation has 2k members.
[16] Most of these findings are empirical observations, since virtually nothing has been proved about the Q sequence so far.
[17][18][19] It is specifically unknown whether the sequence is well-defined for all n; that is, whether 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).
[19] Only the V sequence, which does not behave as chaotically as the others, is proven not to "die".
[19] 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.
[21] 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).
[21] 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.
converge to 1/2, and this sequence acquired its name because John Horton Conway offered a prize of $10,000 to anyone who could determine its rate of convergence.
The prize, since reduced to $1,000, was claimed by Collin Mallows, who proved that[23][24]
In private communication with Klaus Pinn, Hofstadter later claimed that he had found the sequence and its structure about 10–15 years before Conway posed his challenge.