All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Squarely Sorted (Posted on 2013-07-27) Difficulty: 3 of 5
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 n2 are sorted.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
answer with proof | Comment 1 of 4

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information