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 .
The really cool thing is that the proof essentially consists of a (very long, very detailed) algorithm, which, for any positive integer , explicitly finds three palindromes which sum to ! For example, when (the first 21 decimal digits of ), their algorithm gives the three palindromes
You can easily verify (try it!) that these are all palindromes, and that they add up to .
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 , there exists a thing” might be nonconstructive—that is, it shows that for every 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.
Does the proof extend to numbers written to any specified base?
Good point, I didn’t mention that part — the proof is for any base . It isn’t true for , and it’s an open question whether the techniques in the paper can be extended to or .
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.
Typo: you wrote n = 1415… but I think you meant n = 31415…, in both paragraphs 2 and 3.
Good catch, thanks! Fixed now.
Pingback: More on sums of palindromes | The Math Less Traveled
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)
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!
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.
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.
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.
Thank you for sharing this memory of Javier Cilleruelo. It is an impressive result indeed, one he could be justly proud of!
for a given number, is there any algorithm to find those three numbers ?
Yes, read the post more carefully, and also see this followup post: https://mathlesstraveled.com/2018/04/11/more-on-sums-of-palindromes/