An exploration of solutions to two related Hofstadter-Huber recurrence relations. (September 2020)

• Record Type: Journal Article
• Authors: Alkan, Altug; Fox, Nathan; Aybar, Orhan Ozgur; Akdeniz, Zehra
• Is Part Of: Chaos, solitons and fractals. Volume 138(2020)
• Publication Date: 2020-09
• Subjects: Meta-Fibonacci -- Hofstadter V-recurrence -- Familes of solutions to nested recurrences; Chaotic behavior in systems -- Periodicals; Solitons -- Periodicals; Fractals -- Periodicals; Chaotic behavior in systems; Fractals; Solitons; Periodicals; 003.7
• DOI: 10.1016/j.chaos.2020.109900
• Languages: English
• ISSNs: 0960-0779

Abstract

Highlights: Generational structure analysis of the one of the longest known chaotic finite meta-Fibonacci sequences that is generated by Hofstadter's V-recurrence. New kind of solution sequences in Hofstadter-Huber family with more complicated structure than previously known slow or quasi-linear solutions. A new nested recursion H ( n ) = H ( n − H ( n − 2 ) ) + H ( n − H ( n − 3 ) ) that has structural connection with Hofstadter's V-recurrence. Abstract: In this study, we explore the properties of certain solutions of two Hofstadter-Huber recurrence relations. The first is Hofstadter's V -recurrence, which is defined by the nested recurrence relation V ( n ) = V ( n − V ( n − 1 ) ) + V ( n − V ( n − 4 ) ) . Plus, we introduce another meta-Fibonacci recurrence H ( n ) = H ( n − H ( n − 2 ) ) + H ( n − H ( n − 3 ) ) . First, we study a finite chaotic solution to the V -recurrence in order to analyse its generational structure. Then, we explore a new type of infinite solution to nested recurrence relations, finding solutions of this type to both the V -recurrence and the H -recurrence. Our construction relates to systems of nested recurrences that resemble Golomb's recurrence G ( n ) = G ( n − G ( n − 1 ) ) + 1 .