An interesting case is $n=101$.
The $3$-digit palindrome $aba$ is divisible by 101 iff $b=0$.
The $4$-digit palindrome $abba$ is divisible by 101 iff $a=b$.
The $5$-digit palindrome $abcba$ is divisible by 101 iff $c=2a$.
The $6$-digit palindrome $abccba$ is divisible by 101 iff $a+b=c$.
The $7$-digit palindrome $abcdcba$ is divisible by 101 iff $d=2b$.
The $8$-digit palindrome $abcddcba$ is divisible by 101 iff $a+d=b+c$.
The $9$-digit palindrome $abcdedcba$ is divisible by 101 iff $e = 2(c-a)$.
The $10$-digit palindrome $abcdeedcba$ is divisible by 101 iff $a+b+e=c+d$.
...
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.
Best Answer
Before beginning, note that in questions like these, we prefer to say that leading zeroes are not written. That is to say that we do not consider $00500$ a palindrome number since it could be reduced to $500$, ignoring the zeroes on the left.
Break this into cases: it is 1 digit long, it is 2 digits long, it is 3 digits long, $\cdots$, it is 9 digits long, (and it is 10 digits long)
In the case of it being five digits long we have:
__, __, __, __, __
The furthest left digit must match the furthest right, the second on the left must match the second on the right, and the one in the middle could be anything.
By the multiplication principle, http://en.wikipedia.org/wiki/Rule_of_product, you can break this into steps. Step 1: Choose the first digit (any digit 1-9, in doing so, that forces the last digit to be the same), Step 2: Choose the second digit (any digit 0-9, in doing so, that forces the second to last digit to be the same), Step 3: Choose the digit in the middle (any digit 0-9).
Note also that in step 1, the first digit is not allowed to be a zero, but in all other cases it is allowed.
So, we have for the case of a 5 digit palindrome number, $9\cdot 10 \cdot 10\cdot 1 \cdot 1$ number of possibilities.
Repeat this process for all other cases and add them together for the total amount.
Note also for the case of it being 10 digits, you will also need to check that it is less than 1,000,000,000. You should quickly notice that since 1,000,000,000 is the smallest 10 digit number, and is not itself a palindrome, all other 10 digit numbers are not smaller than 1,000,000,000 and thus are ignored for the purposes of this problem.