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(n – B(n – 1)) + B(n – B(n – 2)) + B(n – B(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