Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

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 http://oeis.org/A057135 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 https://code.google.com/codejam/contest/2270488/dashboard#s=a&a=2

share|improve this answer
add comment

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.

share|improve this answer
add comment

The first 412 of these are tabulated at http://oeis.org/A057135/b057135.txt

All the ones listed have no digit exceeding 2, and generally have plenty of zeros, so I'm guessing there aren't any sporadics in the list. Of course, that's not a proof....

share|improve this answer
    
+1 Nice approach - find the root instead of the number itself. –  Adam Matan Apr 14 '13 at 6:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.