Journal of Integer Sequences, Vol. 20 (2017), Article 17.7.3

A Slow Relative of Hofstadter's Q-Sequence

Nathan Fox
Department of Mathematics
Rutgers University
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,    dvi,    ps,    latex    

(Concerned with sequences A004001 A005185 A046699 A057198 A063882 A087777 A278055.)

Received January 2 2017; revised version received June 26 2017. Published in Journal of Integer Sequences, July 2 2017.

Return to Journal of Integer Sequences home page