An integer n, such as 1128, is called "sorted" if its digits are in sorted order. Find the largest integer n such that both n and n^{2} are sorted.
there is no largest such number. As proof, consider a number of the form 666....7 consisting of x digits. The first x1 are 6 and the last one is 7.
now this number can be represented by:
1+6*sum(10^k,k=0 to x1)
1+6*(10^x1)/9
1+2*(10^x1)/3
n=[2*10^x+1]/3
obviously, by design n is sorted.
now n^2=[2*10^x+1]^2/9=
[4*10^(2x)+4*10^x+1]/9
now to show that n^2 is also sorted, lets work thru this division.
[4*10^(2x)+4*10^x+1] is of the form
400....400....1
when you work thru the long division you start by dividing 40 by 9, get 4 with a remainder of 4. Since you bring down a zero, you end up with 40 again. Thus you start with a string of 4's until you get to the next 4 in [4*10^(2x)+4*10^x+1]. Then you have 44 which when divided by 9 gives 4 with a remainder of 8, you bring down a 0 and now you have 80 which gives 7 and remainder of 8 again, thus you now have a string of 7's until you reach the last one which makes 81 giving the last digit of 9. Thus n^2 is of the form:
444.....777.....9
thus n^2 is also sorted.
since this holds for any integer x>1, we have that there are an infinite number of integers for which n and n^2 are sorted.

Posted by Daniel
on 20130727 11:33:51 