## Every positive integer is a sum of three palindromes

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.

Assistant 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:

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

• Brent says:

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:

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:

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

• Brent says:

Good catch, thanks! Fixed now.

3. 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)

• Brent says:

Right, 1 is a sum of three palindromes since it is 1 + 0 + 0. N+0+0 only works if N itself is a palindrome!

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

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.

5. Xavier says:

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:

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

6. R.K.Singh says:

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