View previous topic | View next topic

That Kaprekar was an interesting chap...

Page 1 of 1

Rudolph Hucker
410612.  Sat Sep 20, 2008 2:38 pm Reply with quote

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.

 
AndyMcH
410615.  Sat Sep 20, 2008 3:01 pm Reply with quote

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)

 
Rudolph Hucker
410617.  Sat Sep 20, 2008 3:13 pm Reply with quote

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.

 
Mort
410855.  Sun Sep 21, 2008 11:48 am Reply with quote

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.

 
bobwilson
410897.  Sun Sep 21, 2008 1:48 pm Reply with quote

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!)

 
jakamneziak
410900.  Sun Sep 21, 2008 2:01 pm Reply with quote

this has gone way over my head already. "TAXI!"

 
barbados
410910.  Sun Sep 21, 2008 2:22 pm Reply with quote

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

 
Rudolph Hucker
410914.  Sun Sep 21, 2008 2:30 pm Reply with quote

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?

 
barbados
410917.  Sun Sep 21, 2008 2:34 pm Reply with quote

I don't believe HP wears underwear.

 
bobwilson
410961.  Sun Sep 21, 2008 3:54 pm Reply with quote

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.

 
Rudolph Hucker
411194.  Mon Sep 22, 2008 6:37 am Reply with quote

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.

 
Nigelblt
411399.  Mon Sep 22, 2008 2:07 pm Reply with quote

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.

 
bobwilson
411503.  Mon Sep 22, 2008 5:07 pm Reply with quote

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

 
Nigelblt
411712.  Tue Sep 23, 2008 5:21 am Reply with quote

You might start here...

 

Page 1 of 1

All times are GMT - 5 Hours


Display posts from previous:   

Search Search Forums

Powered by phpBB © 2001, 2002 phpBB Group