# Palindromic Sums

## Solution

I had thought this problem, an example in the Cilleruelo and Luca paper (which proves that any positive integers is a sum of three palindromes (in base 10)) would be difficult, but four readers found a solution.

JosephDeVincentis found two palindromes suffice: 310772864202468277013 + 3386401156511046833

Stephen Meskin found 222463308181803364222 + 91695957177175959619 + 5

Philippe Fondanaiche found 314159000404000951413 + 245152878251542 + 19802100120891

Ken Leone found 314159265353562951413 + 980707089 + 4435665344

Here is DeVincentis's method. The outstanding open question is whether there is an integer B so that every positive integer is a sum of at most B base-two palindromes.

This is a good opportunity for me to attempt to employ the strategy I was envisioning that would solve most numbers as a sum of 2 palindromes.

Write 314159265358979323846 = ABCDEFGHIJKJIHGFEDCBA + LMNOPQRSTUTSRQPONML

21 digits, 21 degrees of freedom in the palindromes. A is necessarily 3, so L is also 3.

314159265358979323846 = 3BCDEFGHIJKJIHGFEDCB3 + 3MNOPQRSTUTSRQPONM3

Now C is going to be 0 or 1, depending on whether D + M carries, so C + 3 does not carry, and B = 1. This then makes M = 3.

314159265358979323846 = 31CDEFGHIJKJIHGFEDC13 + 33NOPQRSTUTSRQPON33

Now D + 3 is going to carry, so C = 0. And then N = 8.

314159265358979323846 = 310DEFGHIJKJIHGFED013 + 338OPQRSTUTSRQPO833

Now E + 8 is going to carry, so D = 7. This makes O = 6.

314159265358979323846 = 3107EFGHIJKJIHGFE7013 + 3386PQRSTUTSRQP6833

Now F + 6 is not going to carry, so E = 7. This makes P = 4.

314159265358979323846 = 31077FGHIJKJIHGF77013 + 33864QRSTUTSRQ46833

Now G + 4 is going to carry, so F = 2. This makes Q = 0.

314159265358979323846 = 310772GHIJKJIHG277013 + 338640RSTUTSR046833

Now H + 0 is not going to carry, so G = 8. This makes R = 1.

314159265358979323846 = 3107728HIJKJIH8277013 + 3386401STUTS1046833

I + 1 is not going to carry, so H = 6. This makes S = 1.

314159265358979323846 = 31077286IJKJI68277013 + 33864011TUT11046833

J + 1 is not going to carry, so I = 4. This makes T = 5.

314159265358979323846 = 310772864JKJ468277013 + 338640115U511046833

K + 5 is now ambiguous as to whether it carries. But J is going to be either 1 or 2, which means J + U will not carry, so K = 0, J = 2, U = 6:

314159265358979323846 = 310772864202468277013 + 3386401156511046833

As already discovered, this algorithm runs into a problem when the first digit and last digit of the sum are the same, or possibly off by 1 if the sum would be forced to carry into the leading digit. In that case, the second palindrome would be forced to end (and thus start) with 0. This problem is resolved by introducing a third palindrome equal to 1.

This algorithm can have trouble with the carries/not carries. It worked out above, but there are certain cases where it fails. In the case where this happens on the last digit, (K, as above), suppose that I needed J + U = 1 (instead of 8) so that this was also ambiguous. Then if I supposed K + 5 doesn't carry, J would be 2, and then J + U = 1 does carry, which makes K + 5 carry, contradicting the assumption. Likewise if I assumed K + 5 does carry, J would be 1, and then J + U would not carry when we needed it to do so!

This carry/not carry can also happen on other digits, and more or less the same thing happens. Again, in these cases we need the third palindrome. However, I am not sure just how bad the carry/not carry problem can get. If I simply make the third palindrome be a 1 (or 2 if it was already 1 to fix the matching first and last digit in the sum) and I cannot guarantee this does not cause other problems elsewhere in the number.

This algorithm also has difficulties when the number of digits in the sum is even. If we had started with ...

3141592653589793238462 = ABCDEFGHIJKKJIHGFEDCBA + LMNOPQRSTUUTSRQPONML

... then there would be 22 digits and 21 degrees of freedom in the palindromes, and we would be in trouble. In the middle, I'd pick K to satisfy K + T = 5, U to satisfy J + U = 9, and then I'd have to pray that K + U = 8, and nine times out of ten it would not. This is probably remedied by making the second palindrome a digit longer, but I am guessing I run into some other problems along the way.