Kaprekar Triples

Douglas E. Iannucci and Bertrum Foster University of the Virgin Islands 2 John Brewers Bay St. Thomas, VI 00802 USA

                        diannuc@uvi.edu
                      bfosterk@yahoo.com

Abstract We say that 45 is a Kaprekar triple because 45^{3} = 91125 and 9 + 11 + 25 = 45. We find a necessary condition for the existence of Kaprekar triples which makes it quite easy to search for them. We also investigate some Kaprekar triples of special forms.

1 Introduction

Kaprekar triples (sequence A006887, Sloan [5]) are numbers with a property which is easily demonstrated by example. Observe that

8^{3} = 512,  5 + 1 + 2 = 8,
45^{3} = 91125,  9 + 11 + 25 = 45,
297^{3} = 26198073,  26 + 198 + 073 = 297,
4949^{3} = 121213882349,  1212 + 1388 + 2349 = 4949,
44443^{3} = 87782935806307,  8778 + 29358 + 06307 = 44443,
565137^{3} = 180493358291026353, 180493 + 358291 + 026353 = 565137.

Therefore 8, 45, 297, 4949, 44443, and 565137 are all examples of Kaprekar triples. Kaprekar triples generalize the Kaprekar numbers (sequence A006886, Sloan [5]), which were introduced by Kaprekar [4], discussed by Charosh[2], and completely characterized by Iannucci [3]. Kaprekar triples are mentioned in Wells’s Dictionary of Curious and Interesting Numbers [6].

Formally, an n-Kaprekar triple k (where n is a natural number) satisfies the pair of equations

k^{3} = p · 10^{2n} + q · 10^{n} + r ,
k = p + q + r ,

where 0 ≤ r < 10^{n}, 0 ≤ q < 10^{n}, and p > 0 are integers. As the 3-Kaprekar triple 297 shows, p may have fewer than n digits, and so may q or r (note the leading zero in r = 073). The stipulation that p > 0 precludes many otherwise trivial examples such as

100^{3} = 0 · 10^{8} + 100 · 10^{4} + 0 ,
100 = 0 + 100 + 0 ,

i.e., 100 as a 4-Kaprekar triple. Having p > 0 also precludes 1 as a Kaprekar triple, in spite of its inclusion in sequence A006887 by Sloan [5].

2 The Set K(N)

Let N be a natural number such that N ≢ 1 (mod 4). We define the set K(N) of positive integers as follows: We say k ∈ K(N) if there exist nonnegative integers r < N, q < N, and a positive integer p, such that

k^{3} = pN^{2} + qN + r  (1)

and such that

k = p + q + r .  (2)

Although N satisfies (1) and (2) (with p = N, q = r = 0), we nonetheless disallow N as an element of K(N). Therefore, it follows that k < N if k ∈ K(N). For, subtracting (2) from (1) yields

k(k − 1)(k + 1) = (N − 1)(p(N + 1) + q) ,  (3)

so that k > N implies

k < p + \frac{q}{k + 1} .

Since q/(k + 1) < 1, we have k ≤ p. Since k < p contradicts (2), we have k = p, but this implies q = r = 0 and hence k = N by (1). Contradiction. Therefore k < N if k ∈ K(N).

Suppose k ∈ K(N). Then (3) implies N − 1 | k(k − 1)(k + 1). Because N ≢ 1 (mod 4), there exist pairwise relatively prime integers d, d_{1}, and d_{2} such that

N − 1 = dd_{1}d_{2} ,  d | k ,  d_{1} | k − 1 ,  d_{2} | k + 1 .  (4)

Since d | k we write

k = dm

for a positive integer m. Then d_{1} | dm − 1 and d_{2} | dm + 1 and so we have

dm ≡ 1 (mod d_{1}) ,  dm ≡ −1 (mod d_{2}) .  (5)

Let

ξ_{1} ≡ d^{−1} (mod d_{1}) ,  ξ_{2} ≡ d^{−1} (mod d_{2}) ,
μ_{1} ≡ d_{1}^{−1} (mod d_{2}) , μ_{2} ≡ d_{2}^{−1} (mod d_{1}) .

Then we have

m ≡ ξ_{1} (mod d_{1}) , m ≡ −ξ_{2} (mod d_{2}) ,

so that by the Chinese remainder theorem we have

m ≡ ξ_{1}μ_{2}d_{2} − ξ_{2}μ_{1}d_{1} (mod d_{1}d_{2}) .  (6)

Moreover, m is the least positive residue such that (6) is satisfied; this is because dm = k < N = dd_{1}d_{2} + 1 and thus m ≤ d_{1}d_{2}.

For a positive integer n, we call d a unitary divisor of n if d | n and (d, \frac{n}{d}) = 1. In this case we write d∥n. We have shown

Theorem 1 If N ≢ 1 (mod 4), then every element k ∈ K(N) is divisible by a unitary divisor d of N − 1. If we write k = dm, then m satisfies (4) for some pair d_{1}, d_{2}, of unitary divisors of N − 1 such that d_{1}d_{2} = (N − 1)/d.

If N ≢ 1 (mod 4), then Theorem 1 gives a necessary condition for finding elements k of K(N), and hence it may be applied to find an upper bound for |K(N)|, the number of elements in K(N). For, if N −1 has the unique prime factorization given by N −1 = ∏_{i=1}^{t} p_{i}^{a_{i}}, then we call the prime powers p_{i}^{a_{i}} the components of N − 1. Then d∥N − 1 if and only if d is a product of components of N − 1 (including the empty product 1). We refer to t, the number of components of N − 1, as ω(N − 1). Thus by Theorem 1, if N ≢ 1 (mod 4) then

|K(N)| ≤ 3^{ω(N−1)} .  (7)

It is possible to define K(N) when N ≡ 1 (mod 4). In this case, the factors d, d_{1}, and d_{2} in (4) will be pairwise relatively prime if and only if d is even. If this is so, we may proceed exactly as above, so that (7) is still true.

Otherwise d is odd. Since 2^{ν}∥N − 1 for some ν ≥ 2, we have either 2∥d_{1}, 2^{ν−1}∥d_{2}, or, 2^{ν−1}∥d_{1}, 2∥d_{2}. Note that these two cases are identical when 2^{2}∥N − 1. In either case, the equations (5) still hold, and since (d, d_{1}) = (d, d_{2}) = 1, we see that m may be determined uniquely modulo [d_{1}, d_{2}]. Here, d∥N − 1, and d_{1} and d_{2} are each some power of 2 multiplied by an odd unitary divisor of N − 1. Thus (7) still holds in the case when N ≡ 1 (mod 4).

3 Kaprekar Triples

In the notation of the previous section,we refer to the set ∪_{n=1}^{∞}K(10^{n}) as the set of Kaprekar triples. If we prefer, we may refer to the set K(10^{n}), for fixed n, as the set of n-Kaprekar triples. To illustrate Theorem 1, consider the set of 6-Kaprekar triples, and note the factorization

10^{6} − 1 = 3^{3} · 7 · 11 · 13 · 37 .

We may take d = 27, d_{1} = 259, and d_{2} = 143. Then

ξ_{1} = 48 ,  ξ_{2} = 53 ,  μ_{1} = 90 ,  μ_{2} = 96 ,

giving

m ≡ 143 · 96 · 48 − 259 · 90 · 53 ≡ 20931 (mod 37037) .

Therefore

m = 20931 ,  d = 27 ,  k = 20931 · 27 = 565137 .

Since

565137^{3} = 180493358291026353 ,
565137 = 180493 + 358291 + 026353 ,

we have 565137 ∈ K(10^{6}). To show that the conditions in Theorem 1 are not sufficient, consider d = 297, d_{1} = 37, and d_{2} = 91. Here,

ξ_{1} = 1 ,  ξ_{2} = 19 ,  μ_{1} = 32 ,  μ_{2} = 24 ,

giving

m ≡ 3257 ,  d = 297 ,  k = 967329 .

However,

967329^{3} = 905154309885752289 ,

but

905154 + 309885 + 752289 = 1967328 ,

and so 967329 ∉ K(10^{6}). Note that 1967328 = 967329 + (10^{6} − 1). Experimentally, we have seen that roughly one fourth of the 3^{ω(N−1)} possible triples (d, d_{1}, d_{2}) of unitary divisors of N − 1 produce an element k ∈ K(N) when Theorem 1 is applied. The other three fourths produce k such that when p, q, and r in (1) are obtained we get

p + q + r = k + (N − 1)

instead of (2). Generally, the larger the value of ω(N − 1), the closer to 1:3 the ratio of elements of K(N) to non-elements becomes.

We provide some data for N = 10^{n}, for various values of n, where “ratio” refers to the ratio |K(10^{n} − 1)|/3^{ω(10^{n}−1)}:

\begin{matrix}n & 3^{ω(10^{n}−1)} & |K(10^{n})| & ratio \\ 5 & 27 & 5 & 0.185185 \\ 6 & 243 & 37 & 0.152263 \\ 7 & 27 & 8 & 0.296296 \\ 10 & 243 & 64 & 0.263374 \\ 12 & 2187 & 527 & 0.240969 \\ 15 & 729 & 195 & 0.267490 \\ 19 & 9 & 1 & 0.111111 \\ 20 & 6561 & 1649 & 0.251334 \\ 21 & 2187 & 538 & 0.245999 \\ 23 & 9 & 1 & 0.111111 \\ 24 & 59049 & 14702 & 0.248980 \\ 30 & 1594323 & 398838 & 0.250161 \\ 42 & 4782969 & 1196902 & 0.250242 \\ 64 & 43046721 & 10759839 & 0.249957 \\ 80 & 14348907 & 3587901 & 0.250047 \end{matrix}

4 Applications

It is a simple matter to search for Kaprekar triples by applying Theorem 1. To do so, one only needs the factorizations of 10^{n} − 1 for n ≥ 1, which are easily available (for example see Brillhart et al. [1]).

In this section we will discuss Kaprekar triples of certain forms. For example, consider the set K(64M^{2}) for some positive integer M. Since

64M^{2} − 1 = (8M − 1)(8M + 1) ,

and since 8M − 1 and 8M + 1 are relatively prime, we can apply Theorem 1 by choosing d, d_{1}, and d_{2} from among the unitary divisors 8M ± 1 and 1 of 64M^{2} − 1. If we let d_{2} = 1, there are at least two ways to do this, one of which is to let d = 8M − 1 and d_{1} = 8M + 1. In this case we have ξ_{1} = 4M and ξ_{2} = μ_{1} = μ_{2} = 1, and thus

m = d_{2}μ_{2}ξ_{1} − d_{1}μ_{1}ξ_{2} = −4M − 1 ≡ 4M (mod 8M + 1) ,

taking the least positive residue modulo 8M + 1. This gives k = dm = 4M(8M − 1). Similarly, taking d = 8M + 1 and d_{1} = 8M − 1 gives k = 4M(8M + 1).

Thus it is possible that 4M(8M ± 1) are both elements of K(64M^{2}). Indeed they are, for

k^{3} = 64M^{3}(8M ± 1)^{3}
= 4096M^{4}(8M^{2} ± 3M) + 64M^{2}(24M^{2} ± M) ,

and,

(8M^{2} ± 3M) + (24M^{2} ± M) = 32M^{2} ± 4M = k .

Note that if n ≥ 3 then 10^{2n} is of the form 64M^{2} with M = 5^{3} · 10^{n−3}. We have

Theorem 2 For n ≥ 3, the integers 5 · 10^{n−1}(10^{n} ± 1) are 2n-Kaprekar triples.

For example, 499500 and 500500 are both 6-Kaprekar triples, 49995000 and 50005000 are both 8-Kaprekar triples, and so forth.

For positive integers r > 1 and n ≥ 1, we refer to an element of K(r^{n}) as a base-r Kaprekar triple. Note that if p ≥ 3 then 2^{2p} has the form 64M^{2} where M = 2^{p−3}. Hence 2^{p−1}(2^{p} ± 1) are binary (or base-2) Kaprekar triples. Since every even perfect number has the form 2^{p−1}(2^{p} − 1) where 2^{p} − 1 is prime (a fact first proved by Euler), we have

Theorem 3 Every even perfect number is a binary Kaprekar triple.

As examples, we see that

28^{3} = 5 · 64^{2} + 23 · 64,  5 + 23 = 28;
496^{3} = 116 · 1024^{2} + 380 · 1024,  116 + 380 = 496;
8128^{3} = 2000 · 16384^{2} + 6128 · 16384, 2000 + 6128 = 8128.

We can also consider the set K(4096M^{4}) for some positive integer M. Similarly as we did above, we can show that 256M^{3} + 4M belongs to this set. Letting M = 5^{3} · 10^{n−3} for n ≥ 3 gives us

Theorem 4 If n ≥ 3 then 5 · 10^{3n−1} + 5 · 10^{n−1} is a 4n-Kaprekar triple.

Hence 500000500 is a 12-Kaprekar triple:

500000500^{3} = 1250003750003750001250000000 ,
125 + 000375000375 + 000125000000 = 500000500 .

Also, 500000005000 is a 16-Kaprekar triple, 500000000050000 is a 20-Kaprekar triple, and so forth.

5 Concluding Remarks

Theorem 2 shows that there always exists an n-Kaprekar triple when n ≥ 6 is even. What about odd n? By (7), there are fewer such triples when ω(10^{n} − 1) is small. In fact, ω(10^{n} − 1) = 2 when n = 19, 23, and 317 (see Brillhart et. al. [1]), although it is not known how long this list may be extended. The table following section 3 shows that an n-Kaprekar exists when n = 19 or 23. However, a simple computer search reveals that no 317-Kaprekar triples exist; thus there do not exist n-Kaprekar triples for every n.

A more general question is, are there certain forms of N for which K(N) is empty? For example, we can show K(N) = ∅ whenever N > 8 is of the form p^{α} + 1 for odd prime p and α ≥ 1; note that K(8) consists of the perfect number 6 by Theorem 3. Indeed, since N − 1 = p^{α}, if k ∈ K(N) then by (4) one of three cases occur: (i) p^{α} | k; (ii) p^{α} | k − 1; (iii) p^{α} | k + 1.

In case (i), as k < N we must have k = p^{α}. But here,

k^{3} = (N − 3)N^{2} + 2N + (N − 1),
(N − 3) + 2 + (N − 1) = k + (N − 1) ≠ k.

In case (ii) we have k ≡ 1 (mod p^{α}) by (6).

In case (iii), k ≡ −1 (mod p^{α}) by (6), which implies k = p^{α} − 1. But

k^{3} = (N − 6)N^{2} + 11N + (N − 8),
(N − 6) + 11 + (N − 8) = k + (N − 1) ≠ k.

All three cases lead to contradiction (case (ii) contradicts 1 < k < N).

On the other hand, there are forms of N for which K(N) ≠ ∅ (as we’ve already seen when N = 10^{2n}). For example, it is straightforward to check that when N = 2^{n} + 1, n ≥ 2, we have k = 2^{n−1} − 1 ∈ K(N).

References

[1] J. Brillhart, D. Lehmer, J. Selfridge, B. Tuckerman, and S. Wagstaff Factorizations of b^{n} ± 1, b =2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers (3rd Ed.), Contemporary Mathematics 22, 2001.

[2] M. Charosh, Some Applications of Casting Out 999… ’s J.Recreational Math. 13 (1980), 111–118.

[3] D. Iannucci, The Kaprekar Numbers, J. Integer Seq. 3 (2000), article 00.1.2.

[4] D. Kaprekar, On Kaprekar Numbers J. Recreational Math. 13 (1980), 81–82.

[5] N. Sloane, The On-Line Encyclopedia of Integer Sequences.

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

2000 Mathematics Subject Classification: Primary 11A63; Secondary 11Y55 . Keywords: Kaprekar triples, division algorithm, Chinese remainder theorem, components, perfect numbers.

(Concerned with sequences \underline{A006886} and \underline{A006887}.)

Received August 30 2004; revised version received October 7 2005. Published in Journal of Integer Sequences, October 20 2005.

Return to Journal of Integer Sequences home page.