A Slow Relative of Hofstadter's Q-Sequence
Department of Mathematics
110 Frelinghuysen Rd.
Piscataway, NJ 08854
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 nth term of our sequence
to be computed efficiently. We conclude by showing that our sequence
cannot be easily generalized.
Full version: pdf,
(Concerned with sequences
Received January 2 2017; revised version received June 26 2017.
Published in Journal of Integer Sequences, July 2 2017.
Journal of Integer Sequences home page