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² are sorted.

there is no largest such number.  As proof, consider a number of the form 666....7 consisting of x digits.  The first x-1 are 6 and the last one is 7.
now this number can be represented by:
1+6*sum(10^k,k=0 to x-1)
1+6*(10^x-1)/9
1+2*(10^x-1)/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 2013-07-27 11:33:51