Every positive integer is a sum of three palindromes

Posted on April 9, 2018 by Brent

I recently learned from John Cook about a new paper by Javier Cilleruelo, Florian Luca, and Lewis Baxter proving that every positive integer can be written as a sum of three palindromes. A palindrome is a number that is the same when written forward or backward, like 1423241.

The really cool thing is that the proof essentially consists of a (very long, very detailed) algorithm, which, for any positive integer n, explicitly finds three palindromes which sum to n! For example, when n = 314159265358979323846 (the first 21 decimal digits of \pi), their algorithm gives the three palindromes

\begin{array}{rcl} p_1 &=& 210100100111001001012 \\ p_2 &=& 98639929400492993689 \\ p_3 &=& 5419235847485329145 \end{array}

You can easily verify (try it!) that these are all palindromes, and that they add up to 314159265358979323846.

ghci> p1 = 210100100111001001012
ghci> p2 = 98639929400492993689
ghci> p3 = 5419235847485329145
ghci> isPalindrome x = show x == reverse (show x)
ghci> isPalindrome p1 && isPalindrome p2 && isPalindrome p3
  True

ghci> p1 + p2 + p3
  314159265358979323846

The reason this is so cool is that in many cases, the proof of a theorem of the form “For every integer n, there exists a thing” might be nonconstructive—that is, it shows that for every n it can’t be the case that there doesn’t exist a thing, which “proves” the theorem but doesn’t actually help us find the things which we suposedly know must exist. But this proof is very much constructive: not only does it show that every positive integer must be expressible as a sum of three palindromes, it actually backs it up with explicit evidence by giving us a way to find the palindromes.

Apparently the authors have written a Python program which implements the algorithm, and I have asked for a copy; I’m excited to play with it! I’d implement it myself, except that the algorithm has so many cases and sub-cases and sub-sub-cases and special adjustments to the sub-sub-cases, etc. that it would probably take me a week.

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.

14 Responses to Every positive integer is a sum of three palindromes

  1. Anthony says:
    April 9, 2018 at 7:00 pm

    Does the proof extend to numbers written to any specified base?

    • Brent says:
      April 9, 2018 at 7:15 pm

      Good point, I didn’t mention that part — the proof is for any base b \geq 5. It isn’t true for b = 2, and it’s an open question whether the techniques in the paper can be extended to b = 3 or 4.

      • Brent says:
        April 10, 2018 at 2:10 pm

        Update: actually, it was an open question when the paper was published, but it’s not open anymore! I’ll write more in a followup post.

  2. DB says:
    April 10, 2018 at 9:20 am

    Typo: you wrote n = 1415… but I think you meant n = 31415…, in both paragraphs 2 and 3.

  3. Pingback: More on sums of palindromes | The Math Less Traveled

  4. John B. Halleck says:
    April 12, 2018 at 4:55 pm

    I think I missed something. 1 is a positive integer. How is it the sum of three palindromes?
    (Other than the trivial 1+0+0 … But if that is allowed, then for any N, N=N+0+0)

  5. John B. Halleck says:
    April 12, 2018 at 5:01 pm

    Ahhh…. I see the problem. The demo says it can be expressed as a sum of at most three palindromes (which is what I assume the paper says.)

    But YOUR title says it can be expressed as the sum of three palindromes.

    My example in the prior post is only a problem if there have to be three.
    With the conditions of the paper, 1 is the (degenerate) sum of one palindrome, namely one.

    • Brent says:
      April 12, 2018 at 5:11 pm

      If we define 0 to be a palindrome, then there is no difference between saying exactly three and at most three, since you can always fill in extra zeros if you need to.

  6. Xavier says:
    April 20, 2018 at 12:29 pm

    Thanks for the post. I must say Javier Cilleruelo was very proud of this result, that was one of the lasts results he was working and solved; even one could think it is just a curiosity, it is not usual one gets a completely new, non trivial and original result that can be explained to (almost) every one.

    • Brent says:
      April 22, 2018 at 9:08 pm

      Thank you for sharing this memory of Javier Cilleruelo. It is an impressive result indeed, one he could be justly proud of!

  7. R.K.Singh says:
    June 22, 2018 at 10:31 pm

    for a given number, is there any algorithm to find those three numbers ?

Comments are closed.