In my previous post I reported on a recent proof that every positive integer can be written as the sum of three palindromes. The first thing to report in this follow-up post is that Lewis Baxter sent me the Python code which implements their algorithm—and even better, pointed me to a web page which will run the algorithm for you! Go ahead and try it, it’s fun—and it’s quite fast, even for really huge numbers. For example, just for fun I put in my office phone number, and it turns out that
Good to know!
Commenter Anthony asked if the proof worked for numbers in any base, which was an important point I forgot to mention: what the paper actually proved is that every positive integer can be written as the sum of three palindromes in any base 
The theorem is not true for numbers in base 2. Notice first that any binary number starts with 
ghci> :set -XBinaryLiterals
ghci> import Text.Printf
ghci> let n = 0b10110000
ghci> let isBinPal x = printf "%b" x == reverse (printf "%b" x :: String)
ghci> [ k | k <- [1..n], isBinPal k, isBinPal (n-k) ]
[]
The [] on the last line is an empty list indicating that there are no binary palindromes which add to
This leaves some questions: what about bases 3 and 4? And how many palindromes do you need in base 2? At the time the paper was published, the answers to these questions were not known. It was conjectured that four palindromes are enough in base 2. It was also conjectured that three palindromes are enough for bases 3 and 4—just like in every other base 
In his email, Lewis Baxter also pointed me to an even more recent paper by Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith which uses a completely different method to resolve the remaining questions: it turns out that the conjectures were correct; we now know that every positive integer can indeed be written as a sum of four binary palindromes, and only three palindromes in base 3 or base 4! Jeffrey Shallit has a nice blog post explaining their method here. It’s not clear to me whether their method can be used to produce an actual algorithm for finding base-2, -3, or -4 palindromes that sum to a given number, though it certainly should be possible.
The Math Less Traveled 
At the risk of coming across as a philistine… What is the use of this finding? Of course it’s cool and I would like to have come up with it and all that but are there any general takeaways from this paper or algorithm that applies to other things? Or is this algorithm an instance of a known class of algorithms etc…?
I agree with Anthony that cool is sufficient. In fact, I would say that finding the answer to a question is also sufficient, even if it isn’t cool. As for general takeaways, though… as for the Cilleruelo et al. paper, I don’t know if there are general takeaways, though there probably are to someone who knows more about this area. But the Rajasekaran et al. paper definitely has some good general takeaways. They use a general proof technique which is potentially applicable to a wide variety of other situations.
Cool — aka beautiful — is sufficient. It is the criterion by which art is judged, and that sufficiency is what distinguishes pure math from applied math and physics.
Well this is fun. Is the code available?
I got the code by emailing Lewis Baxter (see the end of the paper, https://arxiv.org/pdf/1602.06208.pdf , for the address). I’m not sure whether it’s intended to be public so I’m not going to reshare it, but you can contact him if you want it.
Thanks for the great blog posts. These results remind me of Tim Gowers’ introduction to the Princeton Companion to Mathematics. “By way of illustration, let us look at a problem that most mathematicians would not take all that seriously and see what it lacks. A number is palindromic if …” after which he describes trying to prove there are infinitely many palindromic primes.
Later he explains exactly when and why a result on palindromes *would* be of interest to mathematicians. “The only realistic hope of solving such a problem would be to prove a much more general result. Such a result would be wonderful and undeniably interesting…” You can read it here in preview https://books.google.co.uk/books?id=ZOfUsvemJDMC&lpg=PP1&pg=PA75#v=onepage&q&f=false
Thanks for the link! Although it doesn’t work for me (it says I’m not allowed to view that page). Maybe I can get my hands on a physical copy of the book.