Geodesic
A slow relative of Hofstadter's $Q$-sequence
Journal of integer sequences, Tome 20 (2017) no. 7.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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},
     publisher = {mathdoc},
     volume = {20},
     number = {7},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%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/