palindromic squares of palindromes This question is inspired by Google's recent programming competition (modified slightly for ease of exposition). For a given $n$, one of the problems was to find all positive "fair" integers $k$ less than $n$, where $k$ is "fair" if 1. $k$ is a palindrome (in base 10, no leading zeros) 2. $k^2$ is also a palindrome. One first result is that if $k$ is a palindrome, then $k^2$ will involve no carrying if and only if the sum of $k$'s squared digits is less than ten. Therefore all palindromes $k$ with sum of squared digits less than ten are "fair." But can there be sporadic "fair" numbers? Palindromes $k$ where computing $k^2$ involves some carrying, but by pure chance $k^2$ still ends up being a palindrome?

During the competition, I found the first few 'fair and square' numbers, then searched for them in Sloane's encyclopedia of integer sequences. Its page < suggests the 'sum of squares of digits is less than 10' condition is necessary as well as sufficient, but doesn't give a proof. It's not obvious to me either.

Edit: Google posted a proof by contradiction at