 mersenneforum.org > Math Kaprekar's constant
 Register FAQ Search Today's Posts Mark Forums Read 2004-05-31, 16:59 #1 mfgoode Bronze Medalist   Jan 2004 Mumbai,India 22·33·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-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, 05:02   #5

May 2004

13C16 Posts kaprekar's const.

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      2004-06-01, 10:13   #6
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts Kaprekar's constant

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    2004-06-01, 12:45 #7 jinydu   Dec 2003 Hopefully Near M48 33368 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-01, 16:20   #8
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts Kaprekar's constant

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    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 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).   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   2004-06-02, 04:06   #11
jinydu

Dec 2003
Hopefully Near M48

2·3·293 Posts 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.
Attached Files Kaprekar Constant.zip (5.7 KB, 383 views)

Last fiddled with by jinydu on 2004-06-02 at 04:08  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post badbud65 Software 46 2016-05-02 23:18 kar_bon Riesel Prime Data Collecting (k*2^n-1) 5 2009-06-22 23:00 Zeta-Flux Math 4 2007-11-30 08:56 kar_bon Riesel Prime Search 45 2007-11-27 19:15 R.D. Silverman Math 14 2006-08-17 19:58

All times are UTC. The time now is 12:43.

Tue Jul 5 12:43:25 UTC 2022 up 82 days, 10:44, 1 user, load averages: 0.77, 0.99, 1.18