Discovering linear-recurrent solutions to Hofstadter-like recurrences using symbolic computation. (July 2018)

• Record Type: Journal Article
• Authors: Fox, Nathan
• Is Part Of: Journal of symbolic computation. Volume 87(2018)
• Page Start: 99
• Page End: 126
• Publication Date: 2018-07
• Subjects: Nested recursion -- Recurrences -- Quasipolynomials -- Integer sequences; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.06.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: The Hofstadter Q -sequence, with its simple definition, has defied all attempts at analyzing its behavior. Defined by a simple nested recurrence and an initial condition, the sequence looks approximately linear, though with a lot of noise. But, it is unknown whether the sequence is even infinite. In the years since Hofstadter published his sequence, various people have found variants with predictable behavior. Commonly, the variant sequences eventually satisfy linear recurrences. Proofs of such behaviors are inductive and highly automatable. This suggests that a search for more sequences like these may be fruitful. In this paper, we develop an algorithm to search for these sequences. Using this algorithm, we determine that such sequences come in infinite families that are themselves plentiful. In fact, there are hundreds of easy to describe families based on the Hofstadter Q -recurrence alone.