# That Kaprekar was an interesting chap...

Page 1 of 1

 410612.  Sat Sep 20, 2008 2:38 pm Take any four digit number (whose digits are not all identical), and do the following: Rearrange the string of digits to form the largest and smallest 4-digit numbers possible. Take these two numbers and subtract the smaller number from the larger. Use the number you obtain and repeat the above process. What happens if you repeat the above process over and over? Let's see... Suppose we choose the number 3141. 4311-1134=3177. 7731-1377=6354. 6543-3456=3087. 8730-0378=8352. 8532-2358=6174. 7641-1467=6174... The process eventually hits 6174 and then stays there. But the more interesting thing is this: every four digit number whose digits are not all the same will eventually hit 6174, in at most 7 steps, and then stay there. 410615.  Sat Sep 20, 2008 3:01 pm I have no reason to doubt you, but Id love to see a mathematical proof of this. Is anyone clever enough ? (I got tied up in knots) 410617.  Sat Sep 20, 2008 3:13 pm There isn't really a proof as such, it's just a a truth in base 10 maths. Each number in the sequence uniquely determines the next number in the sequence. Since there is only a finite number of possibilities, eventually the sequence must return to a number it has hit before, describing a cycle. So any starting number will give a sequence that eventually cycles. There can many cycles; however, for a length 4 strings in base 10, there happens to be only 1 non-trivial cycle, and it has length 1 (involving the number 6174). So there we are. 410855.  Sun Sep 21, 2008 11:48 am This is indeed interesting! I've been trying some sort of proof of this, and my room is now full of screwed up bits of paper.

I can outline my line of reasoning so far, and I'll TeX up my solution (or just scan it) when I have it fully fleshed out. Ideally, I want to find a solution for an n-digit number but for now just consider a number with four digits w, x, y, z that satisfies the relations

0 < z < y < x < w < 9

and

w!= x != y != z

So the maximum number is {wxyz} and the minimum is {zyxw}

Using the general method for subtraction (just think about precisely how you subtract numbers, and this makes sense)

 Code: wxyz - zyxw   -------   WXYZ

we get four relations

Z = 10 + z - w
Y = 9 + y - x
X = x - y - 1
W = w - z

Now we need to check all of the possible combinations of {wxyz} and see if they satisfy the relations above. For example, if we try {WXYZ} = {wxyz}, then
z = 10 + z - w
y = 9 + y - x
x = x - y - 1
w = w - z

Which gives
w = 10
x = 9
y = 1
z = 0

Which violates our requirement, as w cannot be 10. Now, I used a fairly laborious Group Theory method to continue here (but it's frankly about as uninteresting as just trying every one of the 24 combinations and solving the equations in turn), and I have a calculator that can solve the simultaneous equations for me, and I've found only one combination that satisfies our conditions.

{WXYZ} = {xzwy}

Which has solutions w=7, x=6, y=4, z=1

That is, {WXYZ} = 6174

Now, for n=4 there is one and only one solution, but I see no reason why, in general, that should be the case. I have an eerie feeling that n=5 might be a problem for similar reasons to finding roots of the quintic equation, but I still have to flesh out that thought. 410897.  Sun Sep 21, 2008 1:48 pm Quote: Ideally, I want to find a solution for an n-digit number

Just to add something here - if n = 2 then there is no single n digit solution.

I started off randomly looking at 27:

72-27 = 45
54-45 = 09
90-09 = 81
81-18 = 63
63-36 = 27 ie 5 steps

but using other choices with 7 as one of the digit we get:

71-17 = 54 (reduces to the 5 steps above)

73-37 = 36 (likewise)

74-47 = 27 (and so on......

75-57 = 18

76-67 = 09

87-78 = 09

which begins to look like all patterns reduce to the 5 step

So, the question then arises - does the solution for n digits reduce to N recurring steps; and in the case of n=4, N=1?

(I can see I'm going to be up all night pondering this!) 410900.  Sun Sep 21, 2008 2:01 pm this has gone way over my head already. "TAXI!" 410910.  Sun Sep 21, 2008 2:22 pm This kind of thong has been discussed previously, I seem to recall Flash has a very good trick involving numbers, Harry Potter, and a chair 410914.  Sun Sep 21, 2008 2:30 pm barbados wrote: This kind of thong has been discussed previously, I seem to recall Flash has a very good trick involving numbers, Harry Potter, and a chair

Is it Harry Potter or Flash who wears the thong? 410917.  Sun Sep 21, 2008 2:34 pm I don't believe HP wears underwear. 410961.  Sun Sep 21, 2008 3:54 pm I've decided to hate Rudolph for posting this thread. Having looked up Kaprekar on the interweb thingy and discovered that there is an N=1 solution for n=3 and n=4 but for no other values of n; and realising that this is one of those deceptively simply stated things like Fermat's last theorem but which are fiendishly difficult to prove - I just know I'm going to spend weeks on this. 411194.  Mon Sep 22, 2008 6:37 am bobwilson wrote: I've decided to hate Rudolph for posting this thread. Having looked up Kaprekar on the interweb thingy and discovered that there is an N=1 solution for n=3 and n=4 but for no other values of n; and realising that this is one of those deceptively simply stated things like Fermat's last theorem but which are fiendishly difficult to prove - I just know I'm going to spend weeks on this.

That's unusual - people don't normally post a reason. 411399.  Mon Sep 22, 2008 2:07 pm Quite interestingly, the difference between two numbers generated by ordering the digits is always divisible by 9. for example abcd-dcba = 1000(a-d)+100(b-c)+10(c-b)+(d-a) =999(a-d)+90(b-c) =9(111(a-d)+10(b-c)) This works for any number of digits. 411503.  Mon Sep 22, 2008 5:07 pm Generalising this entire thing: If n is the number of digits in the puzzle group and N is the number of steps in the repeating pattern and B is the base is there a general solution? is there a solution to the maximum number of steps in the repeating pattern? is there a solution to the maximum number of steps required to reach the repeating pattern? For the benefit of jak: ;) If you take 3 digit numbers n = 3, N is 1 (the repeating pattern you reach is 495 which just keeps repeating by subtracting 459 from 954), and B is 10 (we're working in decimal). If you take 4 digit numbers again N is 1, and B is 10 but n=4 But, if you take 2 digit numbers n=2, N is (maybe) 5, and B is still 10. What happens when you start working in other bases? Succinctly, can it be shown that for a given base (B), with a number made up of n digits that there is always a repeating pattern of N steps? That would be a start. Or can it be shown that it this is an unanswerable query? PS I hate Rudolph 411712.  Tue Sep 23, 2008 5:21 am You might start here... Page 1 of 1

All times are GMT - 5 Hours

Display posts from previous:

User tools