Geodesic
A slow relative of Hofstadter's \(Q\)-sequence
Journal of integer sequences, Tome 20 (2017) no. 7
Hofstadter's $Q$-sequence remains an enigma fifty years after its introduction. Initially, the terms of the sequence increase monotonically by 0 or 1 at a time. But the 12th term exceeds the 11th by two, and monotonicity fails shortly thereafter. In this paper, we add a third term to Hofstadter's recurrence in the most natural way. We show that this new recurrence, along with a suitable initial condition that naturally generalizes Hofstadter's initial condition, generates a sequence whose terms all increase monotonically by 0 or 1 at a time. Furthermore, we give a complete description of the resulting frequency sequence, which allows the $n$th term of our sequence to be computed efficiently. We conclude by showing that our sequence cannot be easily generalized.
Classification : 11B37, 11B39
Keywords: nested recurrence, Hofstadter sequence, slow sequence 
@article{JIS_2017__20_7_a6,
     author = {Fox,  Nathan},
     title = {A slow relative of {Hofstadter's} {\(Q\)-sequence}},
     journal = {Journal of integer sequences},
     year = {2017},
     volume = {20},
     number = {7},
     zbl = {1366.11022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2017__20_7_a6/}
}
TY  - JOUR
AU  - Fox,  Nathan
TI  - A slow relative of Hofstadter's \(Q\)-sequence
JO  - Journal of integer sequences
PY  - 2017
VL  - 20
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/JIS_2017__20_7_a6/
LA  - en
ID  - JIS_2017__20_7_a6
ER  - 
%0 Journal Article
%A Fox,  Nathan
%T A slow relative of Hofstadter's \(Q\)-sequence
%J Journal of integer sequences
%D 2017
%V 20
%N 7
%U http://geodesic.mathdoc.fr/item/JIS_2017__20_7_a6/
%G en
%F JIS_2017__20_7_a6
Fox,  Nathan. A slow relative of Hofstadter's \(Q\)-sequence. Journal of integer sequences, Tome 20 (2017) no. 7. http://geodesic.mathdoc.fr/item/JIS_2017__20_7_a6/