In mathematics, 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 Hofstadter 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:
Hofstadter Figure-Figure sequences The Hofstadter Figure-Figure (R and S) sequences are a pair of complementary integer sequences defined as follows:
R ( 1 ) = 1 , S ( 1 ) = 2 ; R ( n ) = R ( n − 1 ) + S ( n − 1 ) , n > 1 , {\displaystyle {\begin{aligned}R(1)&=1,\ S(1)=2;\\R(n)&=R(n-1)+S(n-1),\quad n>1,\end{aligned}}}
with the sequence S ( n ) {\displaystyle S(n)} defined as a strictly increasing series of positive integers not present in R ( n ) {\displaystyle 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, ... (sequence A005228 in the 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 the OEIS)
Hofstadter G sequence The Hofstadter G sequence is defined as follows:
G ( 0 ) = 0 , G ( n ) = n − G ( G ( n − 1 ) ) , n > 0. {\displaystyle {\begin{aligned}G(0)&=0,\\G(n)&=n-G{\big (}G(n-1){\big )},\quad n>0.\end{aligned}}}
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, ... (sequence A005206 in the OEIS)
Hofstadter H sequence The Hofstadter H sequence is defined as follows:
H ( 0 ) = 0 , H ( n ) = n − H ( H ( H ( n − 1 ) ) ) , n > 0. {\displaystyle {\begin{aligned}H(0)&=0,\\H(n)&=n-H{\Big (}H{\big (}H(n-1){\big )}{\Big )},\quad n>0.\end{aligned}}}
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, ... (sequence A005374 in the OEIS)
Hofstadter Female and Male sequences The Hofstadter Female (F) and Male (M) sequences are defined as follows:
… excerpt ends here. Continue reading the full article.
