Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.2

The Kaprekar Numbers


Douglas E. Iannucci
The University of the Virgin Islands
2 John Brewers Bay
St. Thomas, VI 00802
Email address: diannuc@uvi.edu

Abstract: The (decimal)  n-Kaprekar numbers  are defined and are shown to be in one-one correspondence with the unitary divisors of 10n - 1. In particular, this establishes the correctness of an algorithm for generating the Kaprekar numbers proposed by Charosh in 1981. The even perfect numbers are shown to be Kaprekar numbers in the binary base.
 

1.     INTRODUCTION

    The  Kaprekar numbers  (sequence A006886  in [4])  were introduced by the eponymous D. R. Kaprekar [3] in 1980.  They have been the subject of several articles, and are mentioned in David Wells's Dictionary of Curious and Interesting Numbers [5].
    What makes the Kaprekar numbers curious or interesting? Let's consider an example. The number 703 is Kaprekar because

                      7032 = 494209            and             494 + 209 = 703 .

Here are some further examples:

                                 92 = 81 ,                                      8 + 1 = 9 ;
                                 452 = 2025 ,                                20 + 25 = 45 ;
                                 2972 = 88209 ,                            88 + 209 = 297 ;
                                 48792 = 23804641 ,                    238 + 4641 = 4879 ;
                                 173442 = 300814336 ,                3008 + 14336 = 17344 ;
                                 5384612 = 289940248521 ,        289940 + 248521 = 538461 .

Formally, an n-Kaprekar number k >= 1 (for n = 1, 2, ...) satisfies the pair of equations

                                    k = q + r ,

                                  k2 = q * 10n + r

where q >= 1 and 0 <= r < 10n. As the 5-Kaprekar number k = 4879 shows, r may have fewer than n digits. We adopt the convention that 1 is an n-Kaprekar number for all n >= 1, since

                                 12 = 0 * 10n + 1,          1 = 0 + 1 ;

but by fiat 0 and 10m for m >= 1 are not Kaprekar numbers.
    Kaprekar [3] listed 9 as a Kaprekar number, but failed to list 99,  999,  ...  However,   10n - 1 (for all  n >= 1) is n-Kaprekar since

     99 . . . 992  =  9 . . . 9980 . . . 001 ,              9 . . . 998  +  0 . . . 001  =  99 . . . 99 ;
     \______/        \______/  \_____/                    \_____/         \_____/         \______/
       n  nines            n-1  nines     n-1  zeros                        n-1  nines        n-1  zeros           n  nines

that is,

         (10n - 1)2  =  (10n - 2) * 10n  +  1 ,             10n - 1  =  (10n  - 2)  +   1 .

Charosh [2] noted Kaprekar's omission of the numbers  10n - 1  (n >= 1), as well as the 6-Kaprekar numbers 181819 and 818181. In fact, Charosh correctly devised a method by which to construct  Kaprekar numbers of any size. In this paper, we will refine Charosh's result by establishing a bijection between the  n-Kaprekar numbers and the unitary divisors of  10n -1 (thus refining and proving Charosh's result). Recall that  a  is a  unitary divisor of if  ab = m  and  (a, b) = 1 .
 

2.     THE MAIN RESULT

    For each integer  N > 1, let K(N) denote the set of positive integers  k  for which there exists integers  and  such that
 
                                k2  =  qN  +  r                  ( 0  <=  r  <  N )                         (1)
                                 k  =  q  +  r     .                                                                  (2)

As a matter of convention, we shall ignore the vacuous solution  k = N  (for which  q = N  and  r = 0). (1) and (2) imply
 
                                          k(k - 1)  =  q(N - 1)                                                  (3)

    Since we disregard the vacuous solution, we have 1 <= k <= N - 1 (for if k >= N then (3) implies q > k, contradicting (2)).
    The set  K(N)  is nonempty, for always  1 is in  K(N). Suppose were  in  K(N). Since (k, k - 1) = 1, it follows from (3) that  d | k and d' |  k - 1  for some positive  d  and d'  such that dd' = N - 1 and  (d, d' ) = 1. Let  k' = N - k . Because  1 <= k  <=  N - 1 ,  we have  k' > 0 .  Since  k' = (N - 1) - (k - 1) ,  we have  d' | k' . Thus  k = dm  and  k' = d'm'  for some positive m  and  m' ,  whence follows
 
                                     dm  +  d'm'  =  N  =  dd'  + 1                                        (4)


 

Definition:  If  (a , b ) = 1 , we denote by  Inv(a , b ) the least positive integer m such that  am  = 1 (mod b). It follows that  m = Inv(a , b )  if and only if  1 <= mb  and am  =1 (mod b).

It is not difficult to show the next result.

Lemma 1:  Suppose (a , b ) = 1 . Then  m = Inv( a , b )  and    n = Inv( b , a )  if and only if m and n are positive and am+ bn = ab + 1 .

Applying Lemma 1 to (4) gives
 
                k  =  d Inv(d , d' ) ;                k'  =  d' Inv(d ', d ) .                       (5)

    Conversely, let  dd' = N - 1 ,  (d, d') = 1, and let  m = Inv(d, d' )  and  m' = Inv(d', d ) . Then by Lemma 1 we have dm + d'm' = N .  Therefore

                                 d2m2  =  (N - d'm')2
                                           =  N 2 - N d'm' - (dm + d'm') d'm' + (d'm')2
                                           =  N 2 - N d'm' - mm'dd'
                                           =  (N - d'm' - mm'N +  mm' .

Thus
                              (dm)2  =  (N - d'm' - mm') N  +  mm'               (mm' < N) ,
                                 dm   =  (N - d'm' - mm')  +  mm' .

That is,  dm  satisfies (1) and (2)  (with q = N - d'm' - mm'  and  r = mm'), whence dm is in  K(N). Note that   d'm'  is in K(N)  by symmetry.  We have proved the following results:
 

Theorem 1:  is in K(N)  if and only if  k = d Inv(d, (N-1)/d)  for some unitary divisor  d  of  N - 1 .

 
Corollary A:  The elements  of K(N) occur in complementary pairs.  For each  k  in K(N),   N - k  is in K(N).

    Let w(M) denote the number of distinct primes dividing M; then M has exactly 2w(M)  unitary divisors. The following result is immediate:
 

Corollary B:  K(N)  contains exactly  2w(N - 1)  elements. 

    The convention that  N  not be an element of  K(N)  was taken to ensure the bijection between the elements of  K(N)  and the unitary divisors of N - 1 .
 

3.     APPLICATIONS

    If we let  N = 10n  for some  n >= 1  in Theorem 1, we get the set of n-Kaprekar numbers, which is thus given by

                  K(10n)  =  {Inv(d , d' :  dd' = 10n - 1 ,  (d , d' ) = 1 }.

The following table lists all  n-Kaprekar numbers k for  1 <= n <= 6, along with the associated unitary divisors d of  10n - 1 . These same Kaprekar numbers were given by Charosh [2]. By Corollary A, the n-Kaprekar numbers occur in complementary pairs which sum to  10n .
 
   n       d           k   n        d           k   n       d            k   n       d           k
  1        1            1   4      909      7272        11      181819       259     208495
            9            9          1111     7777           297     329967         6993    356643
  2        1            1          9999     9999           77       38962          407     533170
            9           45   5       1            1        2079     187110       10989    681318
           11          55            9        77778           13      461539        2849     390313
           99          99           41        4879          351     609687       76923    538461
        1            1          369      82656           91      318682         481      812890
           27         297          271      17344        2457     466830       12987    961038
           37         703         2439     95121         143      643357        3367     670033
          999        999         11111   22222        3861     791505       90909    818181
  4        1            1         99999   99999        1001     500500        5291     994708
            9         2223        1            1      27027     648648     142857    142857
           11        2728           27     148149          37       351352       37037    851851
           99        4950            7      857143         999      499500      999999   999999
          101       5050          189       5292

    For example, consider n = 3: 27 and 37 are unitary divisors of 103 - 1 = 27 * 37. Then Inv(27, 37) = 11 and Inv(37, 27) = 19, and we obtain the complementary 3-Kaprekar numbers 27 * 11 = 297 and 37 * 19 = 703.
    The universal Kaprekar number 1 corresponds to the unitary divisor 1 of 10n - 1, which is why we allow unity as a Kaprekar number. For each  n >= 1 , we disallow  10n  as a Kaprekar number since it is the vacuous solution to (1) and (2) when  N = 10n .
    If we let  N = bn  in Theorem 1 for some  b >= 2  and  n >= 1 , we get the base-b generalization of the Kaprekar numbers. The case b = 2 is especially interesting.
 

Theorem 2: Every even perfect number is a Kaprekar number in the binary base.

Proof: Let  n >= 1. It is clear that  2n - 1  and  2n + 1  are relatively prime, and that

             2n-1 (2n - 1)  =  1  (mod 2n + 1) ,          0 <  2n-1  <  2n + 1  .

Therefore  2n-1 = Inv(  2n - 1 ,  2n + 1), and so  2n-1 (2n - 1)  is in  K(22n)by Theorem 1. It is well known that every even perfect number has the form   2n-1 (2n - 1)  where   2n - 1  is prime; hence the result follows.  QED

To illustrate Theorem 2,  we see that  28 = 22 (23 - 1)  is perfect and 6-Kaprekar in the binary base:  (28)2 = 11100, and

                 111002 = 1100010000 ,                      1100 + 010000 = 11100 .

Similarly,  bn-1 (bn - 1)  and   bn-1 (bn + 1)  are complementary 2n-Kaprekar numbers in the base b whenever  b  is even. This pattern, among others, was noted by Charosh [2] in the case when  b = 10.
 

4.     CONCLUDING REMARKS
    It is not worth compiling a more extensive list of Kaprekar numbers, since they can be obtained from the prime factorization of  10n - 1 cf. Brillhart et al. [1].
    Corollary B shows that the Kaprekar numbers have natural density zero.
 

REFERENCES.

[1]   Brillhart, J.,   Lehmer, D.H.,  Selfridge, J.,  Tuckerman, B.,  Wagstaff, S.  "Factorizations of   (bn   +/-  1) , b = 2, 3, 5, 6, 7, 10, 11, 12  up to high powers."  2nd ed., Contemporary Mathematics,  v. 22,  American Mathematical Society, Providence, RI, 1988.

[2]   Charosh, M.  "Some Applications of Casting Out 999...'s." Journal of Recreational Mathematics, v. 14, no. 2 (1981-82), pp. 111-118.

[3]   Kaprekar, D.   "On Kaprekar Numbers." Journal of Recreational Mathematics, v. 13, no. 2 (1980-81), pp. 81-82.

[4]   Sloane, N.J.A.  The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org

[5]   Wells, D.  The Penguin Dictionary of Curious and Interesting Numbers,  Penguin Books USA, Inc., New York 1986.
 


(Concerned with sequences A006886, A037042, A053394, A053395, A053396, A053397 .)


Received Feb 3, 1999; revised version received Mar 21, 1999. Published in Journal of Integer Sequences, Jan. 13, 2000.


Return to Journal of Integer Sequences home page