@Article{Rajasekaran2019,
author="Rajasekaran, Aayush
and Shallit, Jeffrey
and Smith, Tim",
title="Additive Number Theory via Automata Theory",
journal="Theory of Computing Systems",
year="2019",
month="May",
day="29",
abstract="We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. 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 (Cilleruelo et al., Math. Comput. 87, 3023--3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove 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 of palindromes as an additive basis. 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.",
issn="1433-0490",
doi="10.1007/s00224-019-09929-9",
url="https://doi.org/10.1007/s00224-019-09929-9"
}