2018/07/03 by Nathan Fox, Fox, Nathan
Computer Science · #11B37 #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1807.01365
openalex publication_date 2018/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nested recurrence relations are highly sensitive to their initial conditions. The best-known nested recurrence, the Hofstadter Q-recurrence, generates sequences displaying a wide variety of behaviors. Most famous among these is the Hofstadter Q-sequence, which appears to be structured at a macro level and chaotic at a micro level. Other choices of initial conditions can lead to more predictable solutions, frequently interleavings of simple sequences. Previous work has focused on the form of a desired solution and on describing an initial condition that generates such a solution. In this paper, we flip this paradigm around. We illustrate how focusing on the form of an initial condition and describing the resulting sequences can yield strange families of new solutions to nested recurrences.