Back to Search
Start Over
Sums of Palindromes: an Approach via Automata
- Publication Year :
- 2018
- Publisher :
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2018.
-
Abstract
- 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.
- Subjects :
- FOS: Computer and information sciences
000 Computer science, knowledge, general works
Mathematics - Number Theory
Formal Languages and Automata Theory (cs.FL)
010102 general mathematics
Computer Science - Formal Languages and Automata Theory
02 engineering and technology
01 natural sciences
Computer Science
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics - Combinatorics
020201 artificial intelligence & image processing
Combinatorics (math.CO)
Number Theory (math.NT)
0101 mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....350bbf38466e3713f9cc74c6327d843a
- Full Text :
- https://doi.org/10.4230/lipics.stacs.2018.54