Journal of Integer Sequences, Vol. 10 (2007), Article 07.7.1

On the Behavior of a Variant of Hofstadter's Q-Sequence

B. Balamohan, A. Kuznetsov and Stephen Tanny
Department of Mathematics
University Of Toronto
Toronto, Ontario M5S 2E4


We completely solve the meta-Fibonacci recursion V(n) = V(n - V(n - 1)) + V(n - V(n - 4)), a variant of Hofstadter's meta-Fibonacci Q-sequence. For the initial conditions V(1) = V(2) = V(3) = V(4) = 1 we prove that the sequence V(n) is monotone, with successive terms increasing by 0 or 1, so the sequence hits every positive integer. We demonstrate certain special structural properties and fascinating periodicities of the associated frequency sequence (the number of times V(n) hits each positive integer) that make possible an iterative computation of V(n) for any value of n. Further, we derive a natural partition of the V-sequence into blocks of consecutive terms ("generations") with the property that terms in one block determine the terms in the next. We conclude by examining all the other sets of four initial conditions for which this meta-Fibonacci recursion has a solution; we prove that in each case the resulting sequence is essentially the same as the one with initial conditions all ones.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A004001, A005185 A063882, and A087777 .)

Received April 11 2007; revised version received June 26 2007. Published in Journal of Integer Sequences, June 27 2007.

Return to Journal of Integer Sequences home page