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.
@InProceedings{rajasekaran_et_al:LIPIcs.STACS.2018.54, author = {Rajasekaran, Aayush and Shallit, Jeffrey and Smith, Tim}, title = {{Sums of Palindromes: an Approach via Automata}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {54:1--54:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.54}, URN = {urn:nbn:de:0030-drops-84976}, doi = {10.4230/LIPIcs.STACS.2018.54}, annote = {Keywords: finite automaton, nested-word automaton, decision procedure, palindrome, additive number theory} }
Feedback for Dagstuhl Publishing