Journal of Integer Sequences, Vol. 27 (2024), Article 24.7.4

The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions


Nathan Fox
Department of Quantitative Sciences
Canisius University
2001 Main St.
Buffalo, New York 14208
USA

Abstract:

We study the three-term nested recurrence relation B(n) = B(nB(n – 1)) + B(nB(n – 2)) + B(nB(n – 3)) subject to initial conditions where the first N terms are the integers 1 through N. This recurrence is the three-term analog of Hofstadter's famous Q-recurrence. Nested recurrences are highly sensitive to their initial conditions. Some initial conditions lead to finite sequences, others lead to predictable sequences, and yet others lead to sequences that appear to be chaotic and infinite. This work parallels a previous study on the Q-recurrence. As with that work, we consider two families of sequences, one where terms with nonpositive indices are undefined and a second where terms with nonpositive indices are defined to be zero. We find similar results here as with the Q-recurrence, as we can completely characterize the sequences for sufficiently large N. The results here are, in a sense, simpler, as our sequences are all finite for sufficiently large N.


Full version:  pdf,    ps,    latex    


(Concerned with sequences A005185 A188670 A244477 A274058 A278055 A283884 A283885 A283887 A373227 A373228 A373229 A373230 A373231 A373232 A373233 A373234 A373235 A373236 A373237 A373238 A373239.)


Received June 10 2024; revised versions received September 2 2024; September 7 2024. Published in Journal of Integer Sequences, September 7 2024.


Return to Journal of Integer Sequences home page