An exploration of solutions to two related Hofstadter-Huber recurrence relations. (September 2020) - Alkan, Altug; Fox, Nathan; Aybar, Orhan Ozgur; Akdeniz, Zehra
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 .