[Math] palindromic squares of palindromes

palindromerecreational-mathematics

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?

Best Answer

I've tried solving the same problem yesterday. I managed to brute-force my way to finding all fair and square (palindromes whose square root is a palindrome) numbers from 1 to $10^{14}$:

1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 4004009004004

My solution was correct, and the second dataset was solved. But I couldn't find a proper way to calculate all fair and square numbers up to $10^{100}$.

I showed this to my wife this morning, and she noticed an interesting pattern of numbers within my list: 

121, 10201, 1002001, 102030201, 10000200001, 1000002000001
484, 40804, 4008004, 400080004, 40000800004, 4000008000004
12321, 1002003002001,

Some fair and square numbers re-appear with space padding. Let's try beyond $10^{14}$. Adding some zeros to $1020302030406040302030201$, whose square root is $1010100010101$ - a palindrome!

Wish I had my wife with me when I solved this yesterday.

I don't have a mathematical explanation for this phenomena, but I guess that for some reason, every fair and square number beyond a certain boundary can be built by adding zeros to a smaller palindrome.

Related Question