2017/06/30 by Aayush Rajasekaran, Jeffrey Shallit, Rajasekaran, Aayush +3 · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1706.10206
openalex publication_date 2017/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. However, the cases b = 2, 3, 4 were left unresolved. We prove, using a decision procedure based on automata, that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.