And just to clarify, the greedy algorithm (take the largest palindrome less than the number you're trying to express) doesn't work. To take a random nine-digit

And just to clarify, the greedy algorithm (take the largest palindrome less than the number you're trying to express) doesn't work. To take a random nine-digit example (literally the first one I tried): 635932028 = 635929536 + 2442 + 44 + 6. In general you can express N as a sum of something like log(log(N)) palindromes this way, which is not quite constant.