mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-05-31, 16:59   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Cool 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
mfgoode is offline   Reply With Quote
Old 2004-05-31, 20:11   #2
apocalypse
 
Feb 2003

2×3×29 Posts
Default

With only about 10000 numbers to test, I'd expect a proof by exhaustive search to be feasible, if not particularly insightful.
apocalypse is offline   Reply With Quote
Old 2004-06-01, 02:43   #3
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

I found a counter-example: 9998

Its digits are not all equal, but:

9998 - 8999 = 999

And of course, 999 - 999 = 0
jinydu is offline   Reply With Quote
Old 2004-06-01, 02:57   #4
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

3×191 Posts
Default

Perhaps it should be
9998 - 8999 = 0999
9990 - 0999 = 8991
which does become 6174 in three more steps.
markr is offline   Reply With Quote
Old 2004-06-01, 05:02   #5
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default 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
devarajkandadai is offline   Reply With Quote
Old 2004-06-01, 10:13   #6
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Red face 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
mfgoode is offline   Reply With Quote
Old 2004-06-01, 12:45   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

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.
jinydu is offline   Reply With Quote
Old 2004-06-01, 16:20   #8
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Cool 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
mfgoode is offline   Reply With Quote
Old 2004-06-02, 01:00   #9
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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 is offline   Reply With Quote
Old 2004-06-02, 02:59   #10
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

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
jinydu is offline   Reply With Quote
Old 2004-06-02, 04:06   #11
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

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
File Type: zip Kaprekar Constant.zip (5.7 KB, 315 views)

Last fiddled with by jinydu on 2004-06-02 at 04:08
jinydu is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 03:34.

Mon May 17 03:34:35 UTC 2021 up 38 days, 22:15, 0 users, load averages: 2.04, 2.54, 2.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.