Hofstadter sequence
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Hofstadter sequence is a member of a family of related integer sequences defined by
non-linear In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
recurrence relations In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
.


Sequences presented in ''Gödel, Escher, Bach: an Eternal Golden Braid''

The first Hofstadter sequences were described by Douglas Richard Hofstadter in his book ''
Gödel, Escher, Bach ''Gödel, Escher, Bach: an Eternal Golden Braid'', also known as ''GEB'', is a 1979 book by Douglas Hofstadter. By exploring common themes in the lives and works of logician Kurt Gödel, artist M. C. Escher, and composer Johann Sebastian Bach, t ...
''. 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 a pair of complementary integer sequences defined as follows : \begin R(1)&=1~ ;\ S(1)=2 \\ R(n)&=R(n-1)+S(n-1), \quad n>1. \end with the sequence S(n) defined as a strictly increasing series of 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 follows : \begin G(0)&=0 \\ G(n)&=n-G(G(n-1)), \quad n>0. \end 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, ...


Hofstadter H sequence

The Hofstadter H sequence is defined as follows : \begin H(0)&=0 \\ H(n)&=n-H(H(H(n-1))), \quad n>0. \end 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, ...


Hofstadter Female and Male sequences

The Hofstadter Female (F) and Male (M) sequences are defined as follows : \begin 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 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, ... :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 follows : \begin Q(1)&=Q(2)=1, \\ Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)), \quad n>2. \end 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, ... 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 In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
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 indices of the summation terms thus depend on the Q sequence itself. Q(1), the first element of the sequence, is never one of the two terms being added to produce a later element; it is involved only within an index in the calculation of Q(3). 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 2''k'' 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).


Generalizations of the ''Q'' sequence


Hofstadter–Huber ''Q''''r'',''s''(''n'') family

20 years after Hofstadter first described the ''Q'' sequence, he and
Greg Huber Greg is a masculine given name, and often a shortened form of the given name Gregory. Greg (more commonly spelled " Gregg") is also a surname. People with the name *Greg Abbott (disambiguation), multiple people * Greg Abel (born 1961/1962), Canad ...
used the character ''Q'' to name the generalization of the ''Q'' sequence toward 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_(n) = \begin 1 , \quad 1 \le n \le s, \\ Q_(n-Q_(n-r))+Q_(n-Q_(n-s)), \quad n > s, \end 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); 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 ''Q''''r'',''s''(''n'') is undefined because ''n'' − ''Q''''r'',''s''(''n'' − ''r'') < 1.


Pinn ''F''''i'',''j''(''n'') family

In 1998,
Klaus Pinn Klaus is a German, Dutch and Scandinavian given name and surname. It originated as a short form of Nikolaus, a German form of the Greek given name Nicholas. Notable persons whose family name is Klaus * Billy Klaus (1928–2006), American baseba ...
, 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 ''F''''i'',''j'' sequences is defined as follows: : F_(n) = \begin 1 , \quad n=1,2, \\ F_(n-i-F_(n-1))+F_(n-j-F_(n-2)), \quad n > 2. \end 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, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ...


Hofstadter–Conway $10,000 sequence

The Hofstadter–Conway $10,000 sequence is defined as follows \begin a(1) &= a(2) = 1, \\ a(n) &= a\big(a(n - 1)\big) + a\big(n - a(n - 1)\big), \quad n > 2. \end 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, ... The values a(n)/n converge to 1/2, and this sequence acquired its name because
John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
offered a prize of $10,000 to anyone who could determine its
rate of convergence In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said to have ''order of c ...
. The prize, since reduced to $1,000, was claimed by Collin Mallows, who proved that \left, \frac - \frac\ = O\left(\frac\right). In private communication with
Klaus Pinn Klaus is a German, Dutch and Scandinavian given name and surname. It originated as a short form of Nikolaus, a German form of the Greek given name Nicholas. Notable persons whose family name is Klaus * Billy Klaus (1928–2006), American baseba ...
, Hofstadter later claimed that he had found the sequence and its structure about 10–15 years before Conway posed his challenge.


References


Sources

*. *. *. *. *{{Citation , last1 = Pinn , first1 = Klaus , title = A Chaotic Cousin of Conway's Recursive Sequence , journal =
Experimental Mathematics Experimental mathematics is an approach to mathematics in which computation is used to investigate mathematical objects and identify properties and patterns. It has been defined as "that branch of mathematics that concerns itself ultimately with th ...
, volume = 9 , issue = 1 , pages = 55–66 , year = 2000 , doi = 10.1080/10586458.2000.10504635 , arxiv = cond-mat/9808031 , bibcode = 1998cond.mat..8031P , s2cid = 13519614 . Integer sequences