Fixed Points and Cycles of the Kaprekar Transformation: 1. Odd Bases

Anthony Kay 72 Tiverton Road Loughborough Leicestershire LE11 2RY United Kingdom

                  anthony.kay@sky.com

Katrina Downes-Ward Author Address

Abstract

We extend Yamagami and Matsui’s theory of the Kaprekar transformation in base 3 to higher odd bases. The structure of primitive proper, primitive non-proper and general cycles appears in all odd bases, but many other features differ according to whether the base is congruent to 1 or 3 modulo 4. In the latter case, cycles are derived from subgroups and cosets in multiplicative groups modulo odd numbers. We examine cycles and fixed points in bases 5 and 7 in some detail, and make some broad observations relating to higher bases. There also exist many cycles outside the primitive/general structure.

1 Introduction

The Kaprekar transformation T_{b,n} takes an integer x which has n ≥ 2 digits when represented in base b ≥ 2, rearranges the digits in descending and ascending orders to produce new integers x_{↓} and x_{↑}, and subtracts the latter from the former. Thus, given a_{0}, a_{1}, …, a_{n−1} ∈ ℤ with

0 ≤ a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{n−1} < b,

we take an integer

x = ∑_{j=0}^{n−1} a_{j}b^{α_{j}}

where the set {α_{0}, α_{1}, …, α_{n−1}} is some permutation of the set {0, 1, …, n − 1}, and the transformation is then defined by

T_{b,n} : x ↦ x_{↓} − x_{↑} := ∑_{j=0}^{n−1} a_{j}b^{j} − ∑_{j=0}^{n−1} a_{n−1−j}b^{j}.  (1)

Clearly the result of the transformation depends only on how many occurrences there are of each of the digits 0, 1, …, b − 1 in the set {a_{0}, a_{1}, …, a_{n−1}}. So if there are k_{i} occurrences of the digit i in the base-b expression of an integer x, i.e., in the set {a_{0}, a_{1}, …, a_{n−1}}, we define the Kaprekar index of x in base b to be the b-tuple (k_{0}, k_{1}, …, k_{b−1}), generalizing the definition introduced by Yamagami and Matsui [?] for base 3. We shall also use the shorthand notation k for this b-tuple, and refer to k_{i} as the i-component of k for each i ∈ {0, 1, …, b−1}; components of Kaprekar indices have previously been referred to as digit counters by Lapenta, Ludington, and Prichett [?, ?]. For example, the integer represented as 30133103 in base 4 has the Kaprekar index (2, 2, 0, 4), with 0-component k_{0} = 2, etc.; applying the Kaprekar transformation to this integer involves doing the subtraction in base 4,

T_{4,8} : 30133103 ↦ 33331100 − 00113333 = 33211101,  (2)

in which the result has the Kaprekar index (1, 4, 1, 2); and we would have obtained the same result if we had started with any other integer with a base-4 representation consisting of two 0’s, two 1’s, no 2’s and four 3’s.

The Kaprekar transformation can be iterated: if T_{b,n} : x ↦ T_{b,n}(x), we define T_{b,n}^{m} recursively by

T_{b,n}^{m+1} : x ↦ T_{b,n} (T_{b,n}^{m}(x)) .

Since there are finitely many integers with n-digit representations in base b (for any given b, n ∈ ℕ), then for any x there must be integers d(x) ≥ 0 and l(x) ≥ 1 such that

T_{b,n}^{d(x)+l(x)}(x) = T_{b,n}^{d(x)}(x).  (3)

Taking d(x) and l(x) to be minimal for (3) to be satisfied, we see that iterations of the Kaprekar transformation must lead ultimately to a cycle of length l(x), with

T_{b,n}^{m+l(x)}(x) = T_{b,n}^{m}(x)

for all m ≥ d(x). If l(x) = 1, we have a fixed point, with T_{b,n}^{m}(x) = T_{b,n}^{d(x)}(x) for all m ≥ d(x). The notation and terminology will be applied to Kaprekar indices as well as to integers: for example, we may observe that in base 2 the integer 1001 is a fixed point because

T_{2,4}(1001) = 1100 − 0011 = 1001,

a result which can be written in terms of Kaprekar indices as

T_{2,4}(2, 2) = (2, 2)

so that the Kaprekar index (2, 2) is a fixed point in base 2. The ordered set of integers, or of their Kaprekar indices, produced by iterating the Kaprekar transformation from an integer x with Kaprekar index k, will be called a Kaprekar sequence. The integer T_{b,n}(x) and its Kaprekar index T_{b,n}(k) will be called the successor of x and k, respectively. As shorthand, we shall use primes to denote successors: k′ = T_{b,n}(k), with components k′ = (k′_{0}, k′_{1}, …′ , k′_{b−1}), and multiple primes can be used to denote further terms in the Kaprekar sequence. A formula for k′, or any of its components, in terms of the components of k will be called a succession formula. We shall also avoid the cumbersome T_{b,n}^{m} notation by simply using the symbol ↦ between successive members of a Kaprekar sequence. For example, readers may wish to check that further iterations from the calculation in (2) yield the sequence of integers,

30133103 ↦ 33211101 ↦ 32033211 ↦ 32133111 ↦
22202112 ↦ 21033222 ↦ 31333311 ↦ ⋯

with its corresponding sequence of Kaprekar indices,

(2, 2, 0, 4) ↦(1, 4, 1, 2) ↦ (1, 2, 2, 3) ↦ (0, 4, 1, 3) ↦
(1, 2, 5, 0) ↦ (1, 1, 4, 2) ↦ (0, 3, 0, 5) ↦ · · · .

In the companion paper [?], we show that in base 4 the integer 31333311, obtained after 6 iterations, is in fact the first member of the above sequence to be in a cycle, which is a cycle of length 3. Thus for the starting integer x = 30133103 we have d(x) = 6 and l(x) = 3. We also find that the Kaprekar index (1, 1, 4, 2), obtained after only 5 iterations, is in a cycle of Kaprekar indices, but at that stage this index corresponds to an integer not yet in the cycle; it commonly occurs that the sequence of Kaprekar indices enters a cycle one term before the sequence of integers, since each index corresponds to many integers.

It is important to retain leading zeroes in all calculations, so that the digit-count n remains fixed while iterating with the Kaprekar transformation. For example, in base ten with n = 3, T_{3,10}(877) = 877 − 778 = 99 which we write with three digits as 099, so that the next iteration gives T_{3,10}^{2}(877) = 990 − 099 = 891. If the leading zero had been dropped, the second iteration would have given the spurious result 99 − 99 = 00 (although in fact some authors have operated in this way). Of course, any integer which is a repdigit in base b, i.e., with all its digits the same, will be transformed to 00 … 0 (with n zeroes), which is a fixed point of the Kaprekar transformation. It has been shown by Yamagami [?] that only with 2-digit integers in an odd base can a non-repdigit be transformed to a repdigit; in all other cases, in particular whenever n ≥ 3, we regard repdigits as a trivial case, and exclude them from any further consideration. If every non-repdigit with some given digit-count n in some base b iterates to the same fixed point or cycle by the Kaprekar transformation, that fixed point or cycle is termed unanimous.

The history of the transformation started with the observation by D. R. Kaprekar that when applied to non-trivial 4-digit integers in base ten, it always leads to the fixed point 6174 after no more than seven iterations [?, ?]; so 6174 is a unanimous fixed point for b = 10, n = 4. Kaprekar regarded this merely as a curiosity; but other authors have subsequently studied the transformation in various bases b and with various digit-counts n, and with rather more attention on fixed points than on cycles of length l > 1. A selection of these studies is listed by Yamagami [?], in a paper which also includes a complete theory of the Kaprekar transformation in base 2: the principal result for base 2 is that every Kaprekar index (k_{0}, k_{1}) with k_{0} ≤ k_{1} is a fixed point, and that there do not exist cycles of length l > 1. Yamagami and Matsui [?] then considered the much more complicated case of base 3, and produced a complete and rigorous theory which determines every possible fixed point and cycle, for any number of digits. At the same time, Downes-Ward [?] was using a more empirical approach to study cycles in bases 3 to 8, searching for patterns in lists of integers which are fixed points or members of cycles; those lists have been provided by Joseph Myers in the Online Encyclopedia of Integer Sequences [?], and are complete for digit-counts n up to at least 70 for bases 2 to 10. General formulae for members of cycles in base 3 were found by Downes-Ward [?], and we have checked that these formulae are consistent with the theory of Yamagami and Matsui [?]. The patterns found by Downes-Ward [?] in the data for number and lengths of cycles as a function of digit-count n are much more regular in even bases than in odd bases; in a companion paper [?] we formulate a complete theory of the Kaprekar transformation in base 4 and develop some theory that applies more generally to even bases, while in the present paper we show how Yamagami and Matsui’s theory for base 3 may be generalized to cover all odd bases. We find different behaviour according to whether b ≡ 1 (mod 4) or b ≡ 3 (mod 4), and we illustrate these behaviours by examining bases 5 and 7 in detail.

Thus the remaining sections of this paper are as follows. Section 2 contains a summary of Yamagami and Matsui’s results for base 3, with some further theoretical observations which are useful for consideration of higher odd bases. Section ?? contains theory that applies to all odd bases; some of the theorems here can be deduced from the formulae for difference counters and digit counters in the papers by Lapenta, Ludington, and Prichett [?, ?], but we prove them from first principles to maintain a consistent approach. The following two sections contain more specific results for bases b ≡ 1 (mod 4) and b ≡ 3 (mod 4) respectively, and we draw some general conclusions regarding odd bases in Section ??. There has been a wide variety of notation and terminology used by different researchers on the Kaprekar transformation; much of our usage is that introduced by Yamagami. One notational convention that we introduce is that the letter j always refers to place in a n-digit string, as in (1), while i always refers to a base-b digit, 0 ≤ i ≤ b − 1.

2 Review of Yamagami and Matsui’s results for base 3

A complete characterisation of the fixed points and cycles of the Kaprekar transformation in base 3 has been given by Yamagami and Matsui [?]. The elegance of their theory may not be apparent to readers of their paper, due to the rather lengthy proofs required to demonstrate rigorously that no possible fixed points or cycles have been omitted; so the present authors consider it worthwhile to provide a summary of the results and their theoretical background. We do not address the questions of which cycle or fixed point is reached from a given starting integer x, or the number of iterations of the Kaprekar transformation required to enter a cycle or reach a fixed point from x; Yamagami and Matsui found relatively simple answers to these questions for odd digit-counts n, but the case of even n was found to be too complicated to develop a theory.

Yamagami and Matsui found that all fixed points and cycles in base 3 fit into a classification for which they introduced the terms singular, primitive proper, primitive non-proper, and general, with just two exceptions: with n = 2, the Kaprekar transformation takes all 2-digit integers to the repdigit 11 in no more than 2 iterations, and hence to the fixed point 00, with Kaprekar index (2, 0, 0); while with n = 3, there is a unanimous cycle of length 2,

022 ↦ 121 ↦ 022,

with Kaprekar indices

(1, 0, 2) ↦ (0, 2, 1) ↦ (1, 0, 2).

The latter case was classified by Yamagami and Matsui as a singular cycle, but does not exactly fit into the pattern of singular cycles described below. For n ≥ 4, fixed points in base 3 can simply be treated as cycles of length 1, with no separate theory required (in contrast to the situation in even bases, considered in our companion paper [?]).

The singular cycles are of length l = m + 1 and digit-count n = 2^{m} + 2 for each m ∈ ℕ; the Kaprekar index of one member of a cycle is (0, 2, 2^{m}), and the remaining members are (1, 2^{j}, 2^{m} − 2^{j} + 1) for j = 1, …, m. So with m = 1 we have a cycle of length 2 in 4-digit integers,

1221 ↦ 1012 ↦ 1221,

or in terms of Kaprekar indices,

(0, 2, 2) ↦ (1, 2, 1) ↦ (0, 2, 2).

The cycle of indices in the m’th case is

(0, 2, 2^{m}) ↦ (1, 2, 2^{m} − 2 + 1) ↦ (1, 2^{2}, 2^{m} − 2^{2} + 1) ↦ ⋯
↦ (1, 2^{m−1}, 2^{m} − 2^{m−1} + 1) ↦ (1, 2^{m}, 1) ↦ (0, 2, 2^{m}).

Fundamental to Yamagami and Matsui’s theory for the remaining classes of cycle in base 3 are the following definition and theorem.

Definition 1. For any odd integer r ≥ 3, let σ(r) be the least positive integer such that 2^{σ(r)} ≡ ±1 (mod r). See \underline{A003558} in OEIS.

Theorem 2. For every odd integer r ≥ 3, σ(r) is a divisor of ϕ(r)/2, where ϕ is the Euler totient function (\underline{A000010} in OEIS).

Euler’s totient theorem states that r divides a^{ϕ(r)} − 1 when r ∈ ℕ and a is coprime with r; setting a = 2 confirms the existence of σ(r) satisfying Definition 1. Next, let q_{0} be any even positive integer that is less than and coprime with a given odd r, and define q_{i} for i > 0 recursively by the rules:

q_{i+1} = \begin{cases}2q_{i}, & if q_{i} < \frac{r}{2}; \\ 2(r − q_{i}), & if q_{i} > \frac{r}{2}. \end{cases}  (4)

Clearly q_{i} ≡ ±2^{i}q_{0} (mod r), so from Definition 1 we have that q_{σ(r)} = q_{0} but q_{i} ≠ q_{0} for 1 ≤ i < σ(r); note that although Definition 1 appears to allow q_{σ(r)} = r − q_{0}, this cannot happen since r − q_{0} is odd. Thus we have a cycle of q-values of length σ(r),

q_{0} ↦ q_{1} ↦ ⋯ ↦ q_{σ(r)−1} ↦ q_{σ(r)} = q_{0}.

These q-cycles may be understood by reference to ℤ_{r}^{×}, the multiplicative group of integers modulo r, consisting of the ϕ(r) positive integers less than and coprime with r. The q-cycle starting from q_{0} = r − 1 is obtained as follows: take the cyclic subgroup generated by 2 in ℤ_{r}^{×}, i.e., the ordered set (1, 2, 2^{2} mod r, …, 2^{j−1} mod r) for some j which divides ϕ(r), and replace any odd members q_{i}^{∗} with even integers q_{i} = r − q_{i}^{∗} (in particular, replace q_{0}^{∗} = 1 with q_{0} = r − 1). The subgroup may or may not include r − 1. If it does, the integer r − 1 is reached at the halfway point of generating the subgroup (since (r − 1)^{2} ≡ 1 (mod r)); but the q-cycle is complete at this point. If r − 1 is not in the subgroup, the q-cycle is derived from the entire subgroup. Either way, corresponding to the members of the q-cycle, there are equally many odd integers q_{i}^{∗} = r − q_{i} in ℤ_{r}^{×}, and including the q_{i}^{∗} together with the q_{i} accounts for 2σ(r) members of the group. This may be the entirety of the group; if not, further q-cycles are derived from cosets of our subgroup in ℤ_{r}^{×}, and Lagrange’s Theorem then yields the result in Theorem 2. The number of q-cycles for any given odd r is then

N_{q}(r) = \frac{ϕ(r)}{2σ(r)}.  (5)

Yamagami and Matsui found succession formulae for the 1-component of a Kaprekar index, which in the case where k_{0} = 1 take the form

k′_{1} = \begin{cases}2k_{1}, & if 1 + k_{1} < k_{2}; \\ 2(k_{2} − 1), & if 1 < k_{2} < 1 + k_{1}. \end{cases}  (6)

But with k_{0} = 1, we have k_{2} = n − 1 − k_{1}, and by setting r = n − 2 we can see that these succession formulae are precisely the rules (4) that govern q-cycles. Hence, corresponding to each q-cycle there exists a base-3 Kaprekar cycle for integers of digit-count n = r + 2, with members of the cycle having Kaprekar indices of the form

(1, q_{i}, r − q_{i} + 1).  (7)

Yamagami and Matsui termed these Kaprekar cycles the primitive proper cycles. Corresponding to each of these cycles, there exist primitive non-proper cycles of integers with digit-count n = cr + 2, with members having Kaprekar indices

(1, cq_{i}, cr − cq_{i} + 1),  (8)

for every integer c > 1. Finally, corresponding to each primitive (proper or non-proper) cycle, there exist general cycles of integers with digit-count n = cr + 2s, with members having Kaprekar indices

(s, cq_{i}, cr − cq_{i} + s),  (9)

for every integer s > 1. Being derived from a q-cycle, all these primitive and general cycles have the same length, σ(r).

The fixed points of the Kaprekar transformation in base 3 correspond to any q-cycle of length σ(r) = 1. Only r = 3 satisfies this requirement, with the single member of the q-cycle being q_{0} = 2. So there is the single primitive proper fixed point with Kaprekar index (1, 2, 2) for n = 5, primitive non-proper fixed points (1, 2c, c + 1) for n = 3c + 2, and general fixed points (s, 2c, c + s) for n = 3c + 2s.

While the formulae to generate all cycles and fixed points are simple, if it is required to determine the cycles and fixed points with a given digit-count n, the following procedure needs to be followed. If n is odd with n ≥ 5, there is at least one primitive proper cycle. The number of such cycles is N_{q}(r), found from (5) where r = n − 2. We have seen that a q-cycle can always be generated using the rules (4) from q_{0} = r − 1; this q-cycle corresponds to a subgroup of ℤ_{r}^{×}. If N_{q}(r) > 1, further q-cycles corresponding to cosets in ℤ_{r}^{×} may be found by taking q_{0} as the greatest even positive integer less than and coprime with r and not appearing in a cycle already found. The primitive proper cycles of Kaprekar indices are then obtained from the q-cycles by the formula (7). If n − 2 is prime, there are no non-proper cycles. If n−2 is composite (odd or even), there are non-proper cycles corresponding to each of its odd factors r ≥ 3 such that cr = n − 2 for some c ∈ ℕ; having obtained the q-cycle(s) for each such r, the non-proper cycles of Kaprekar indices of form (8) can be calculated using the multiplier c. Clearly the only primitive cycles for even n are non-proper cycles with even c; but if n = 2^{m} + 2 for any m ∈ ℕ, which is the case where a singular cycle exists, there are no primitive cycles at all. Finally, there are general cycles for the given n corresponding to the primitive cycles for digit-counts n − 2t, for each t ∈ ℕ such that n − 2t ≥ 5 or n − 2t ≥ 8 in the respective cases of odd or even n (since 5 and 8 are the smallest digit-counts for which primitive cycles exist in the respective odd and even cases).

Hence the enumeration of general cycles for a given n requires the enumeration of primitive cycles for all smaller positive integers n′ of the same parity, while the enumeration of