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.