2024/06/03 by Nathan Fox, Fox, Nathan
Computer Science · #11B37 #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2406.00904
openalex publication_date 2024/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.