Back to Search
Start Over
Proving properties of some greedily-defined integer recurrences via automata theory
- Publication Year :
- 2023
-
Abstract
- Venkatachala on the one hand, and Avdispahi\'c & Zejnulahi on the other, both studiied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2308.06544
- Document Type :
- Working Paper