Kaprekar's constant

mfgoode · 2004-05-31, 16:59

The no. 6174 is widely and internationally known as Kaprekars constant, the result of Kaprekar,s (kaps,) process applied to any 4 digit number, apart from the exceptional no.s whose digits are all equal.
Take any 4 digit no. and arrange the digits in ascending and descending order, so that for e.g. 4527 leads to 2457 and 7542. Subtract and repeat The eventual result is the number 6174. This resutl will be attained within 8 subtractions. If a no. ends in 0, 00 , or 000, then also the substraction is valid and 6174 is obtained.
For the no. 4572 we get,
7542 - 2457 = 5085
8550 - 0558 = 7992 and so on till the 7th substraction- 8532 - 2358 = 6174

7641 - 1467 = 6174 and so the calculation repeats after 7 subtractions :surprised

6174 is also a Harshad no. because it is divisible by the sum of its digits.

Kaprekar was a contemporary of mine and I made it a point to meet him when ever he came to Mumbai from Pune.

His one great disappointment was that he could not prove that this process was valid for all digits excluding no.s whose digits are all equal.
A sketchy proof has been given on the Net but it is not satisfactory or rigorous enough.

Can any one prove this constant resulting from Kaps process?

Also that the no. will be attained within 8 subtractions?.
What about other no.s with different no. of digits (like 5 digits no.s?) etc. ?
I have tried for a long time but have not arrived with an acceptable proof.

Mally

apocalypse · 2004-05-31, 20:11

With only about 10000 numbers to test, I'd expect a proof by exhaustive search to be feasible, if not particularly insightful.

jinydu · 2004-06-01, 02:43

I found a counter-example: 9998

Its digits are not all equal, but:

9998 - 8999 = 999

And of course, 999 - 999 = 0

markr · 2004-06-01, 02:57

Perhaps it should be
9998 - 8999 = 0999
9990 - 0999 = 8991
which does become 6174 in three more steps.

devarajkandadai · 2004-06-01, 05:02

yes;it works.regards
devaraj

Quote:

Originally Posted by mfgoode

The no. 6174 is widely and internationally known as Kaprekars constant, the result of Kaprekar,s (kaps,) process applied to any 4 digit number, apart from the exceptional no.s whose digits are all equal.
Take any 4 digit no. and arrange the digits in ascending and descending order, so that for e.g. 4527 leads to 2457 and 7542. Subtract and repeat The eventual result is the number 6174. This resutl will be attained within 8 subtractions. If a no. ends in 0, 00 , or 000, then also the substraction is valid and 6174 is obtained.
For the no. 4572 we get,
7542 - 2457 = 5085
8550 - 0558 = 7992 and so on till the 7th substraction- 8532 - 2358 = 6174

7641 - 1467 = 6174 and so the calculation repeats after 7 subtractions :surprised

6174 is also a Harshad no. because it is divisible by the sum of its digits.

Kaprekar was a contemporary of mine and I made it a point to meet him when ever he came to Mumbai from Pune.

His one great disappointment was that he could not prove that this process was valid for all digits excluding no.s whose digits are all equal.
A sketchy proof has been given on the Net but it is not satisfactory or rigorous enough.

Can any one prove this constant resulting from Kaps process?

Also that the no. will be attained within 8 subtractions?.
What about other no.s with different no. of digits (like 5 digits no.s?) etc. ?
I have tried for a long time but have not arrived with an acceptable proof.

Mally

mfgoode · 2004-06-01, 10:13

Quote:

Originally Posted by markr

Perhaps it should be
9998 - 8999 = 0999
9990 - 0999 = 8991
which does become 6174 in three more steps.

Thank you Markr. I was baffled for a while with Jinydu's post :surprised

Mally

jinydu · 2004-06-01, 12:45

To start off, any four digit number can be written as 1000a + 100b + 10c + d.

Since we're going to arrange these digits in ascending and descending order, we may assume, without loss of generality a >= b >= c >= d and a NOT= d (otherwise, the digits would all be the same).

Then, the first step is:

(1000a + 100b + 10c + d) - (1000d + 100c + 10b + a) = 999a + 90b - 90c -999d

Clearly, the result is divisible by 9.

Thus, we need now only consider four-digit numbers that are divisible by 9.

But I'm not sure where to go from there, other than brute force computation.

mfgoode · 2004-06-01, 16:20

Quote:

Originally Posted by jinydu

To start off, any four digit number can be written as 1000a + 100b + 10c + d.

Since we're going to arrange these digits in ascending and descending order, we may assume, without loss of generality a >= b >= c >= d and a NOT= d (otherwise, the digits would all be the same).

Then, the first step is:

(1000a + 100b + 10c + d) - (1000d + 100c + 10b + a) = 999a + 90b - 90c -999d

Clearly, the result is divisible by 9.

Thus, we need now only consider four-digit numbers that are divisible by 9.

But I'm not sure where to go from there, other than brute force computation.

Excellent deduction and thanks for the lead.

These 4 digit no.s are the result of subtractions which are divisible by 9.
I can visualise a no. tree whose upper branches start with random no.s and these taper down the branches to no.s divisible by 9. Somehow these no.s then taper down to the trunk resulting in one number which is 6174.
Lets take it from there and give it more thought.
The probability that 6174 comes up eveytime must be very high even approaching 1.

Mally

jinydu · 2004-06-02, 01:00

This "tree" would look something like this:

Level 0: All positive integers less than 10,000 except 1111*n (where n is a natural number).

Level 1: All multiples of 9 less than 10,000

Level 2: All positive integers less than 10,000 that are multiples of 9 and are ?

...

Level 8: 6174

The bottleneck is that I can't deduce the special property about Level 2 that distinguishes it from Level 1.

Put another way:

Given that a + b + c + d = 0mod9

What can be said about the whole expression: 999a + 90b - 90c - 999d (other than it being divisible by 9).

An alternative method of proving it is to simply prove that the only possible loop in this process is 6174---->6174. But this seems even more difficult (because a loop could potentially have a length of over 1000, since there are over 1000 multiples of 9 below 10000).

jinydu · 2004-06-02, 02:59

Now, I've made some improvements to what numbers can appear in level 1.

Remember that if the number is the zeroth level is 1000a + 100b + 10c + d, then the number for the first level is 999a + 90b - 90c - 999d.

Now, suppose we want to find the maximum value for that expression. Clearly then, we would want to maximize a and b, while minimizing c and d. There is no reason why we can't choose a = b = 9 and c = d = 0 (this corresponds to starting with the number 9900).

Therefore, max (level 1) = 999(9) + 90(9) = 9801

If we want to find the minimum, we can factorize the expresssion to get: 999(a - d) + 90(b - c)

Because of our restriction that a >= b >= c >= d, neither of the two terms can be negative. The smallest possible value of (b - c) is zero, since there is no reason why we can't choose b = c. However, a cannot equal d (which would mean that the largest digit equals the smallest digit, implying that all the digits are the same, which is not allowed). Instead, the smallest possible value of (a - d) is 1.

Therefore, min (level 1) = 999(1) = 999

Now, returning to the expression 999(a - d) + 90(b - c), we can define two variables, p and q:

p = a - d
q = b - c

Thus, the expression becomes 999p + 90q

We already noted that (a - d) cannot equal 0. Its not difficult to see that the maximum value of p is 9 (corresponding to a = 9 and d = 0).

Therefore, 1 <= p <= 9

Also, (b - c) can equal 0 (there's no reason why the middle two digits can't be the same) or 9 (b = 9 and c = 0), or anything in between.

Therefore, 0 <= q <= 9

One more thing to note is that: Since a >= b, then (a - c) >= (b - c).
Similarly: Since c >= d, then (a - d) >= (a - c)
From these two inequalities, its easy to see (a - d) >= (b - c)
This is the same as saying:

p >= q

In summary then, all possible numbers at level 1 are given by:

999p + 90q

Where, 1 <= p <= 9, 0 <= q <= 9 and p >= q

This gives a total of 54 possible values at level 1, a breeze for a computer (but that still wouldn't be very insightful).

Anyway, I'll have to get on with level 2.

jinydu · 2004-06-02, 04:06

Ok, I've used Microsoft Excel to analyze all the possibilities and I have found several things:

1) All numbers do eventually become 6174
2) It takes a maximum of 7 subtractions for this to occur.
3) Here are the number of distinct numbers at each level:

Level 0 - 9990
Level 1 - 54
Level 2 - 20
Level 3 - 14
Level 4 - 10
Level 5 - 7
Level 6 - 4
Level 7 - 1

I've attached the file, if anyone wants to check my calculations.

2004-05-31, 16:59	#1
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²·3³·19 Posts	Kaprekar's constant The no. 6174 is widely and internationally known as Kaprekars constant, the result of Kaprekar,s (kaps,) process applied to any 4 digit number, apart from the exceptional no.s whose digits are all equal. Take any 4 digit no. and arrange the digits in ascending and descending order, so that for e.g. 4527 leads to 2457 and 7542. Subtract and repeat The eventual result is the number 6174. This resutl will be attained within 8 subtractions. If a no. ends in 0, 00 , or 000, then also the substraction is valid and 6174 is obtained. For the no. 4572 we get, 7542 - 2457 = 5085 8550 - 0558 = 7992 and so on till the 7th substraction- 8532 - 2358 = 6174 7641 - 1467 = 6174 and so the calculation repeats after 7 subtractions :surprised 6174 is also a Harshad no. because it is divisible by the sum of its digits. Kaprekar was a contemporary of mine and I made it a point to meet him when ever he came to Mumbai from Pune. His one great disappointment was that he could not prove that this process was valid for all digits excluding no.s whose digits are all equal. A sketchy proof has been given on the Net but it is not satisfactory or rigorous enough. Can any one prove this constant resulting from Kaps process? Also that the no. will be attained within 8 subtractions?. What about other no.s with different no. of digits (like 5 digits no.s?) etc. ? I have tried for a long time but have not arrived with an acceptable proof. Mally

2004-06-02, 02:59	#10
jinydu Dec 2003 Hopefully Near M48 2·3·293 Posts	Now, I've made some improvements to what numbers can appear in level 1. Remember that if the number is the zeroth level is 1000a + 100b + 10c + d, then the number for the first level is 999a + 90b - 90c - 999d. Now, suppose we want to find the maximum value for that expression. Clearly then, we would want to maximize a and b, while minimizing c and d. There is no reason why we can't choose a = b = 9 and c = d = 0 (this corresponds to starting with the number 9900). Therefore, max (level 1) = 999(9) + 90(9) = 9801 If we want to find the minimum, we can factorize the expresssion to get: 999(a - d) + 90(b - c) Because of our restriction that a >= b >= c >= d, neither of the two terms can be negative. The smallest possible value of (b - c) is zero, since there is no reason why we can't choose b = c. However, a cannot equal d (which would mean that the largest digit equals the smallest digit, implying that all the digits are the same, which is not allowed). Instead, the smallest possible value of (a - d) is 1. Therefore, min (level 1) = 999(1) = 999 Now, returning to the expression 999(a - d) + 90(b - c), we can define two variables, p and q: p = a - d q = b - c Thus, the expression becomes 999p + 90q We already noted that (a - d) cannot equal 0. Its not difficult to see that the maximum value of p is 9 (corresponding to a = 9 and d = 0). Therefore, 1 <= p <= 9 Also, (b - c) can equal 0 (there's no reason why the middle two digits can't be the same) or 9 (b = 9 and c = 0), or anything in between. Therefore, 0 <= q <= 9 One more thing to note is that: Since a >= b, then (a - c) >= (b - c). Similarly: Since c >= d, then (a - d) >= (a - c) From these two inequalities, its easy to see (a - d) >= (b - c) This is the same as saying: p >= q In summary then, all possible numbers at level 1 are given by: 999p + 90q Where, 1 <= p <= 9, 0 <= q <= 9 and p >= q This gives a total of 54 possible values at level 1, a breeze for a computer (but that still wouldn't be very insightful). Anyway, I'll have to get on with level 2. Last fiddled with by jinydu on 2004-06-02 at 03:01

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Various and Constant BSOD's.	badbud65	Software	46	2016-05-02 23:18
Constant n Search	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	5	2009-06-22 23:00
Explicit constant?	Zeta-Flux	Math	4	2007-11-30 08:56
Constant n-Search for k*2^n-1	kar_bon	Riesel Prime Search	45	2007-11-27 19:15
Generalization of Brun's Constant	R.D. Silverman	Math	14	2006-08-17 19:58

2004-05-31, 20:11	#2
apocalypse Feb 2003 2·3·29 Posts	With only about 10000 numbers to test, I'd expect a proof by exhaustive search to be feasible, if not particularly insightful.

2004-06-01, 02:43	#3
jinydu Dec 2003 Hopefully Near M48 2×3×293 Posts	I found a counter-example: 9998 Its digits are not all equal, but: 9998 - 8999 = 999 And of course, 999 - 999 = 0

2004-06-01, 02:57	#4
markr "Mark" Feb 2003 Sydney 3·191 Posts	Perhaps it should be 9998 - 8999 = 0999 9990 - 0999 = 8991 which does become 6174 in three more steps.

2004-06-01, 12:45	#7
jinydu Dec 2003 Hopefully Near M48 3336₈ Posts	To start off, any four digit number can be written as 1000a + 100b + 10c + d. Since we're going to arrange these digits in ascending and descending order, we may assume, without loss of generality a >= b >= c >= d and a NOT= d (otherwise, the digits would all be the same). Then, the first step is: (1000a + 100b + 10c + d) - (1000d + 100c + 10b + a) = 999a + 90b - 90c -999d Clearly, the result is divisible by 9. Thus, we need now only consider four-digit numbers that are divisible by 9. But I'm not sure where to go from there, other than brute force computation.

2004-06-02, 01:00	#9
jinydu Dec 2003 Hopefully Near M48 2×3×293 Posts	This "tree" would look something like this: Level 0: All positive integers less than 10,000 except 1111n (where n is a natural number). Level 1: All multiples of 9 less than 10,000 Level 2: All positive integers less than 10,000 that are multiples of 9 and are ? ... Level 8: 6174 The bottleneck is that I can't deduce the special property about Level 2 that distinguishes it from Level 1. Put another way: Given that a + b + c + d = 0mod9 What can be said about the whole* expression: 999a + 90b - 90c - 999d (other than it being divisible by 9). An alternative method of proving it is to simply prove that the only possible loop in this process is 6174---->6174. But this seems even more difficult (because a loop could potentially have a length of over 1000, since there are over 1000 multiples of 9 below 10000).