Papers › The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions
The Behavior of a Three-Term Hofstadter-Like Recurrence with Linear Initial Conditions
Nathan Fox
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In this paper, 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 Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)). 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. A corresponding study to this one was previously carried out 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections