More on sums of palindromes

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

5014501377 = 4010220104 + 963303369 + 40977904.

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 b \geq 5.

The theorem is not true for numbers in base 2. Notice first that any binary number starts with 1, so any binary palindrome must end with 1 as well, that is, it must be odd—except 0, which we define to be a palindrome as well. But a sum of three odd numbers is odd, so for the theorem to true, every even number would have to be the sum of two palindromes in base 2 (plus zero to make three palindromes). But the even binary number 10110000 is a counterexample, since it can be checked (e.g. by writing a computer program to try all possibilities) that it is not the sum of two binary palindromes. The following code does exactly that:

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 10110000.

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 \geq 5; the proof just didn’t cover those cases.

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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, links and tagged , , , . Bookmark the permalink.

7 Responses to More on sums of palindromes

  1. Naren Sundar says:

    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…?

    • Brent says:

      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.

  2. Anthony says:

    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.

  3. Anonymous says:

    Well this is fun. Is the code available?

  4. 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

    • Brent says:

      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.

Comments are closed.