This problem has a quite elegant solution - Suppose you know the fair palindromes (is a palindrome and a root of a palindrome) of length 2*k. Then you can add either a single digit or double that to the center, and test if it's fair. This algorithm generates all the fair palindromes. https://gist.github.com/macobo/5430510

By memory, there were under 50000 such palindromes in range 0..10^100.