Conway’s RATS Sequences in Base 3

Johann Thiel Department of Mathematical Sciences United States Military Academy West Point, NY 10996 USA

                     johann.thiel@usma.edu

Abstract

We study the behavior of Conway’s RATS (reverse-add-then-sort) sequences in base 3. An independent proof is given of Gentges’ result that all RATS sequences in base 3 are ultimately periodic. We also prove Erdős-Kac and Hardy-Ramanujan type results for the periods of such sequences.

1 Introduction

John H. Conway has invented many mathematical games, including the well known Game of Life. In 1990, Conway [1] created a new game inspired by Kaprekar [6] that he dubbed Reverse-Add-Then-Sort (RATS). The rules are simple: begin with any positive integer n written in base 10, add to it the number obtained by reversing the order of the digits of n, then sort the result in order of increasing digits from left to right (discarding any zeros), and repeat. The game stops if the sequence generated by iterating this process ever repeats a term, and therefore becomes periodic.

Example 1. We play the RATS game beginning with n = 9 (sequence \underline{A066711} in [7]).

9 + 9 18  18 + 81 99  99 + 99 198  189 + 981 1170  117 + 711 828  288 + 882 1170

In this particular case, the game ends after six iterations and yields the sequence

9 ↦ 18 ↦ 99 ↦ 189 ↦ 117 ↦ 288 ↦ 117 ↦ ⋯,  (1)

with the terms 288 and 117 forming a cycle with period 2.

Base 10 is a natural starting point for the RATS game, as it coincides well with the arithmetic most individuals are used to; however, there is nothing particularly special about base 10 that prevents the RATS game from being played in other bases. In this paper, we concentrate on the RATS game in base 3.

In order to study the RATS game, we are motivated to formalize the rules mathematically. Using the definitions below, we will translate the RATS game into the language of discrete dynamical systems.

Definition 2. For any positive integer n written in base 3, let \overline{n} be the digit formed by reversing the digits of n, and let n′ be the digit formed by ordering the nonzero digits of n in increasing order from left to right. Define the function R: ℕ → ℕ by R(n) = (n + \overline{n})′.

The function R represents a single iteration of the RATS process in base 3. We are interested in the behavior of the sequence obtained by repeatedly applying R to whatever output it generates. To denote iterates of R, we adopt superscript notation. For any nonnegative integer t, let R^{t}(n) = R(R^{t−1}(n)) if t ≥ 1 and R^{0}(n) = n.

Definition 3. We call {R^{i}(n)}_{i=0}^{∞} the RATS sequence generated by n in base 3. Since our discussion revolves around base 3 RATS sequences, we will typically drop the phrase “in base 3” unless needed for clarification.

Example 4.

R^{2}(10012) = R((10012 + 21001)′)

= R((101020)′) = R(112) = (112 + 211)′ = (1100)′ = 11

Definition 5. If R^{p}(n) = n for some p > 0, we say that n and the RATS sequence generated by n are periodic. If p is the least integer with this property, we say that the period is p. If R^{t}(n) is periodic for some t ≥ 0, we say that n and the RATS sequence generated by n are ultimately periodic. (Periodic sequences are sometimes referred to as “cycles” and ultimately periodic sequences are “tributaries” to a cycle [5, p. 404].)

From the definitions above, we see that all periodic sequences are ultimately periodic, but not vice versa. Also note that in the definition of periodic elements n, we only require that R^{p}(n) = n for some p. This is because if R^{p}(n) = n, then R^{t+p}(n) = R^{t}(R^{p}(n)) = R^{t}(n) for all t ≥ 0; that is, the sequence {R^{t}(n)}_{t=0}^{∞} is periodic, in the usual sense, with period p.

2 Periodic behavior

Gentges [4] showed that all RATS sequences in base 3 are ultimately periodic. We will give an independent proof of this result that yields additional information, including a complete characterization of all periodic elements.

Theorem 6 (Gentges, [4]). Every RATS sequence in base 3 is ultimately periodic. Furthermore, if P is the set of all p for which there are periodic elements with period p, then P = {p : p ≥ 3}.

Before proving Theorem 6, we introduce some helpful notation and prove some necessary, auxiliary lemmas.

Definition 7. We define a one-to-one correspondence between sorted integers in base 3 and X := ℤ_{≥0}^{2} \ \{(0, 0)\} by \underbrace{1 ⋯ 1}_{u 1’s} \underbrace{2 ⋯ 2}_{v 2’s} ↔ (u, v). With this correspondence, we use R(u, v) to

mean R(\underbrace{1 ⋯ 1}_{u 1’s} \underbrace{2 ⋯ 2}_{v 2’s}) and we extend any terminology from Section 1 to (u, v).

Since our aim is to show that every RATS sequence in base 3 is ultimately periodic, we can assume, without loss of generality, that the starting integer for the sequence is already sorted. The following lemma characterizes the output of R for any given, sorted, input.

Lemma 8. Given any element (u, v) representing a sorted integer, we have that:

(i) if v = 0, R(u, v) = (0, u);

(ii) if u > v > 0, R(u, v) = (2v, 0);

(iii) if 0 < u ≤ v, R(u, v) = (2u, v − u);

(iv) if u = 0, R(u, v) = (2, v − 1).

Proof. If u = 0, we have that

\begin{matrix}22 ⋯ 22 \\ + 22 ⋯ 22 \\ 122 ⋯ 21 \end{matrix}

So R(0, v) = (2, v − 1), proving (iv).

The assertions (i)–(iii) can all be proved in a similar fashion.

Lemma 9. Given any (u, v), there is a t > 0 such that R^{t}(u, v) = (0, v′) for some v′.

Proof. Case 1. If v = 0, then R(u, 0) = (0, u), by Lemma 8(i), so the statement holds with t = 1.

Case 2. If u > v > 0, then R^{2}(u, v) = R(2v, 0) = (0, 2v) by using Lemma 8 (ii) and (i). So the statement holds with t = 2.

Case 3. If 0 < u ≤ v, then R(u, v) = (2u, v − u), again by Lemma 8. If 2u ≤ v − u, the output (2u, v − u) falls into the same case, while increasing the first coordinate and decreasing the second. Hence, repeated applications of R can only produce an output of the form of case 3 a finite number of times before reaching an element of the form (u′, v′) with u′ > v′ ≥ 0, i.e., an element that falls into case 1 or case 2.

Case 4. If u = 0, then R(0, v) = (2, v − 1), which leads to case 3 if v ≥ 3, to case 2 if v = 2, and to case 1 if v = 1.

Figure 1: Directed graph of cases in Lemma 9.

The above argument can be illustrated by the directed graph in Figure 1. The vertices are labeled according to the cases in the lemma, and the directed edges show how the RATS process may evolve when iterating R.

It follows from Lemma 9 that for any (u, v), there is a minimal t > 0 such that R^{t}(u, v) = (0, v′) for some v′. The following lemma gives an explicit formula for t and v′ in the special case when u = 0 and v ≠ 2^{k} − 1 for k ≥ 1.

Lemma 10. If 2^{k} − 1 < v < 2^{k+1} − 1 for some k ≥ 1 and t > 0 is minimal such that R^{t}(0, v) = (0, v′) for some v′, then t = k + 2 and

v′ = 2v − 2^{k+1} + 2.  (2)

In particular,

v′ ≤ v,  (3)

since v ≤ 2^{k+1} − 2.

Proof. By repeated applications of cases (iv) and (iii) from Lemma 8, it follows that

R^{s}(0, v) = (2^{s}, v − 2^{s} + 1)  (4)

for 0 < s ≤ k. (Note that (4) holds even in the case v = 2^{k} − 1.)

If v = 2^{k}, then, by (4) and two further applications of cases (ii) and (i) from Lemma 8, R^{k+2}(0, v) = R^{2}(2^{k}, 1) = R(2, 0) = (0, 2v −2^{k+1} +2) = (0, 2). Since v = 2^{k} ≥ 2, the assertion holds in this case.

If 2^{k} < v < 2^{k+1} − 1, then, by (4) and Lemma 8,

R^{k+2}(0, v) = R^{2}(2^{k}, v − 2^{k} + 1) = R(2v − 2^{k+1} + 2, 0) = (0, 2v − 2^{k+1} + 2).  (5)

The upper bound v < 2^{k+1} − 1 is equivalent to the inequality 2v − 2^{k+1} + 2 ≤ v, so the assertion also holds in this case.

Proposition 11. In base 3, for any integer p ≥ 3, there exists a RATS sequence that is periodic with period p. In particular, (0, v) is periodic with period p if and only if v = 2^{p−1}−2 for some p ≥ 3.

Proof. (⇐) If v = 2^{p−1} − 2 for some p ≥ 3, then, by (4) and Lemma 8, the RATS sequence generated by (0, 2^{p−1} − 2) after p iterations is

(0, 2^{p−1} − 2) ↦^{(iv)} (2, 2^{p−1} − 3) ↦^{(iii)} \underbrace{⋯}_{p−3 times} ↦^{(iii)} (2^{p−2}, 2^{p−2} − 1) ↦^{(ii)} (2^{p−1} − 2, 0) ↦^{(i)} (0, 2^{p−1} − 2).

(6)

Therefore, (0, v) is periodic with period p.

(⇒) Let (0, v) be periodic with period p. Now if 2^{k} − 1 ≤ v < 2^{k+1} − 1 for some integer k > 1, then R^{k}(0, v) = (2^{k}, v − 2^{k} + 1) by (4).

If v = 2^{k} − 1, then R^{k+1}(0, v) = R(2^{k}, 0) = (0, 2^{k}). Since, by assumption, (0, v) is periodic, this implies that (0, 2^{k}) is periodic. However, the following calculation shows that

(0, 2^{k}) leads to the periodic cycle (0, 2) ↦^{(iv)} (2, 1) ↦^{(ii)} (2, 0) ↦^{(i)} (0, 2) and hence is itself not periodic if k > 1:

(0, 2^{k}) ↦^{(iv)} (2, 2^{k} − 1) ↦^{(iii)} ⋯ ↦^{(iii)} (2^{k}, 1) ↦^{(ii)} (2, 0).  (7)

This shows that v ∉ {2^{k} − 1, 2^{k}}.

Hence we must have that 2^{k} < v < 2^{k+1} − 1. Suppose that p is not minimal such that R^{p}(0, v) = (0, v′) for some v′. Then we can write p = p_{1} + p_{2} + ⋯ + p_{N} for some N > 1 such that 0 < p_{1} < p is minimal such that R^{p_{1}}(0, v) = (0, v_{1}) for some v_{1}, 0 < p_{2} < p − p_{1} is minimal such that R^{p_{2}}(0, v_{1}) = (0, v_{2}) for some v_{2}, etc. Notice that, for 0 < i < N, 2^{k_{i}} < v_{i} < 2^{k_{i}+1} − 1 for some k_{i} > 1, since, if v_{i_{0}} = 2^{k_{i_{0}}} − 1 or v_{i_{0}} = 2^{k_{i_{0}}} for some k_{i_{0}}, the assumption that (0, v) is periodic implies that (0, v_{i_{0}}) is periodic, a contradiction to the argument leading to (7). By Lemma 10, it follows that v = v_{N} ≤ v_{N−1} ≤ ⋯ ≤ v_{1} ≤ v. Therefore, v_{1} = v. So R^{p_{1}}(0, v) = (0, v), contradicting the assertion that p is the period of (0, v). So p must be minimal such that R^{p}(0, v) = (0, v′) for some v′. By (5), we get that v = 2v − 2^{p−1} + 2, as desired.

The case 1 ≤ v < 3 can be handled by inspection. This completes the proof of the proposition.

We now completely characterize all periodic elements (u, v) with the following key lemma.

Corollary 12. The element (u, v) is periodic with period p if and only if there is some t such that R^{t}(0, 2^{p−1} − 2) = (u, v). In particular, if this condition holds, (u, v) appears in the sequence given by (6).

Proof. (⇐) By Proposition 11, (0, 2^{p−1} − 2) is periodic with period p. Hence if there is a t such that R^{t}(0, 2^{p−1} − 2) = (u, v), (u, v) is also periodic with period p.

(⇒) By Lemma 9, there is a t′ such that R^{t′}(u, v) = (0, v′) for some v′. If (u, v) is periodic with period p, then this implies that (0, v′) is also periodic with period p. By Proposition 11, this gives that v′ = 2^{p−1} − 2. In particular, (u, v) = R^{p}(u, v) = R^{p−t′}(R^{t′}(0, v′)) = R^{p−t′}(0, 2^{p−1−2}). So the assertion holds with t = p − t′.

The final assertion of the corollary follows from the fact that (6) is the periodic sequence generated by (0, 2^{p−1} − 2).

Lemma 13. Given any (u, v), there is a t such that R^{t}(u, v) = (0, 2^{p−1} − 2) for some p ≥ 3.

Proof. By Lemma 9, there is a minimal t > 0 such that R^{t}(u, v) = (0, v′) for some v′. So, it is enough to prove the lemma for u = 0.

Suppose that 2^{k} − 1 ≤ v < 2^{k+1} − 1 for some positive integer k. Then Lemma 10 shows that either v = 2^{k} − 1 or v′ ≤ v.

Case 1. If v = 2^{k} − 1, then there is a t such that R^{t}(0, v) = (0, 2) (see (7)).

Case 2. If v = v′, (0, v) is periodic, so the assertion holds by Proposition 11.

Case 3. If v′ < v, we apply Lemma 9 to (0, v′) in place of (0, v). This third case can only occur a finite number of times before a repeated application of Lemma 9 leads to case 1 or 2.

Proof of Theorem 6. Lemma 13 establishes that all RATS sequences in base 3 are ultimately periodic, Proposition 11 shows that {p : p ≥ 3} ⊂ P, and a simple modification of a theorem of Cooper and Kennedy [2, p. 7] shows that 1 ∉ P. It remains to show that 2 ∉ P.

Suppose that (u, v) is periodic with period 2. Let (u′, v′) = R(u, v). By studying Figure 1, if follows that the only way to have (u, v) periodic with period 2 would be to have u = 0 and v′ = 0 (case 4 followed by case 1 of Lemma 6), or, alternatively, one would need to have 0 < u ≤ v and 0 < u′ ≤ v′ (both case 3 of Lemma 6).

If u = 0, then (u′, v′) = (2, v − 1), so v − 1 = v′ = 0. Since (u, v) has period 2, (0, v) = R(u′, v′) = R(2, 0), which implies that v = 2, a contradiction. Now if both (u, v) and (u′, v′) are such that 0 < u ≤ v and 0 < u′ ≤ v′, then (u, v) = R^{2}(u, v) = (4u, v − 3u), which implies that u = 0, a contradiction to the fact that u must be positive. Therefore, 2 ∉ P.

3 Distribution of periods

In the previous section we showed that every RATS sequence in base 3 is ultimately periodic and we constructed elements (u, v) ∈ X that are periodic with any desired period p ≥ 3. In this section, we seek to answer the following question: Given p ≥ 3 and a set Y ⊂ X, how many elements (u, v) ∈ Y are ultimately periodic with period p? In other words, given some collection of sorted integers \underbrace{1 ⋯ 1}_{u 1’s} \underbrace{2 ⋯ 2}_{v 2’s} in base 3, how are the periods of the RATS

sequences they generate distributed? We will answer this question completely for sets of the form {(0, v) : 0 ≤ v < 2^{k}}, and obtain partial results for other sets.

We begin with a definition followed by a key result that will be used repeatedly in this section. The key result is special in that it allows us to identify the exact period of (0, v) in terms of the binary representation of v with no additional information.

Definition 14. For a positive integer p ≥ 3, let

B(p) := \{v ∈ ℤ_{>0} : v = 1 \underbrace{∗ ⋯ ∗0}_{p−3 1’s} 1 ⋯ 1 in binary\},

where we allow for the possibility that the bracketed block or the rightmost block of consecutive 1’s is empty.

v base 2 period of (0, v)
32 100000  3
33 100001  3
34 100010  4
35 100011  3
36 100100  4
37 100101  4
38 100110  5
39 100111  3
40 101000  4
41 101001  4
42 101010  5

v base 2 period of (0, v)
43 101011  4
44 101100  5
45 101101  5
46 101110  6
47 101111  3
48 110000  4
49 110001  4
50 110010  5
51 110011  4
52 110100  5
53 110101  5

Figure 2: Base 2 representation of v and period of (0, v).

Example 15. From Figure 2, we see that 45, 50 ∈ B(5), since 45 = 1 \underbrace{0110}_{2 1’s} 1 and 50 =

1 \underbrace{10010}_{2 1’s}. We also have that 7, 35 ∈ B(3), since 7 = 111 and 35 = 1 \underbrace{000}_{0 1’s} 11.

The membership of a positive integer v in B(p) is based on the following procedure. Take the integer v in binary, remove the leftmost 1 and all of the 1’s beyond the rightmost 0, count the number of remaining 1’s in the string of digits left and call the count p′. Then v ∈ B(p′ + 3). In particular, this is a well-defined procedure and every v belongs to B(p) for some unique p. A careful examination of Figure 2 suggests that if v ∈ B(p), then (0, v) is ultimately periodic with period p. Indeed this is the case, as we will show in Proposition 17.

As noted above, the sets B(p) are pairwise disjoint and thus form a partition of the positive integers. The key lemma of interest is that, in some sense, the RATS process does not disturb this partition.

Lemma 16. If v ∈ B(q) for some q ≥ 3 and there is a t > 0 such that R^{t}(0, v) = (0, v′), then v′ ∈ B(q).

Proof. Suppose that we are given (0, v) with v ∈ B(q) for some q ≥ 3. Furthermore, suppose that 2^{k−1} ≤ v < 2^{k}; i.e., that v is k digits long.

Case 1. If v = 2^{k−1}, then v ∈ B(3) since v = 10 ⋯ 0. By Lemma 10, R^{k+2}(0, v) = R^{2}(2^{k−1}, 1) = R(2, 0) = (0, 2). Since 2 ∈ B(3), the assertion of the lemma holds in this case.

Case 2. If v = 2^{k} − 1, then v ∈ B(3) since v = 1 ⋯ 1. By (4), R^{k+1}(0, v) = R(2^{k}, 0) = (0, 2^{k}). Since 2^{k} ∈ B(3), the assertion of the lemma holds in this case.

Case 3. If 2^{k−1} < v < 2^{k} − 1, then, by (5), R^{k+2}(0, v) = (0, 2v − 2^{k} + 2). As in the previous two cases, we aim to show that if v ∈ B(q) for some q ≥ 3, then 2v − 2^{k} + 2 ∈ B(q).

Subtracting 2^{k−1} from v simply plucks the leftmost zero from the binary representation of v. If v ∈ B(q) for some q > 3, then

v − 2^{k−1} = 1 \underbrace{∗ ⋯ ∗0}_{p−3 1’s} 1 ⋯ 1 − 10 ⋯ 0

= 1 \underbrace{∗ ⋯ ∗0}_{p−4 1’s} 1 ⋯ 1,

so v − 2^{k−1} ∈ B(q − 1). Adding 1 to the result gives

v − 2^{k−1} + 1 = 1 \underbrace{∗ ⋯ ∗0}_{p−4 1’s} 1 ⋯ 1 + 1  (8)

= 1 \underbrace{∗ ⋯ ∗1}_{p−3 1’s} 0 ⋯ 0,

so v − 2^{k−1} + 1 ∈ B(q). If v ∈ B(3), then

v − 2^{k−1} + 1 = 10 ⋯ 01 ⋯ 1 − 10 ⋯ 0 + 1  (9)
= 1 ⋯ 1 + 1
= 10 ⋯ 0,

so v − 2^{k−1} + 1 ∈ B(3). Therefore, for any v in case 3, if v ∈ B(q) for some q ≥ 3, then v − 2^{k−1} + 1 ∈ B(q).

Multiplication by 2 in binary is equivalent to simply tacking on an extra 0 at the end of v − 2^{k−1} + 1. From (8) and (9), we see that if v − 2^{k−1} + 1 ∈ B(q) for some q ≥ 3, then 2v − 2^{k} + 2 ∈ B(q).

What this shows is that, by appealing to Lemma 10, if v ∈ B(q) for some q ≥ 3 and t > 0 is minimal such that R^{t}(0, v) = (0, v′), then v′ ∈ B(q). We now remove the word “minimal” from the previous statement with the following argument. If t > 0 is such that R^{t}(0, v) = (0, v′) and t is not minimal, then there is a partition of t = t_{1} + t_{2} + ⋯ + t_{N} for some N > 1 such that 0 < t_{1} < t is minimal such that R^{t_{1}}(0, v) = (0, v_{1}) for some v_{1}, 0 < t_{2} < t − t_{1} is minimal such that R^{t_{2}}(0, v_{1}) = (0, v_{2}) for some v_{2}, etc. It follows, from the above case analysis, that v_{1}, v_{2}, ⋯, v_{N} ∈ B(q). Since v′ = v_{N}, the assertion of the lemma holds.

Proposition 17. For any positive integer v, (0, v) is ultimately periodic with period p ≥ 3 if and only if v ∈ B(p).

Proof. (⇒) If (0, v) is ultimately periodic with period p ≥ 3, then, by Proposition 11 and Lemma 13, there is a t such that R^{t}(0, v) = (0, 2^{p−1} −2). By Lemma 16, if v ∈ B(q) for some q ≥ 3, then 2^{p−1} − 2 ∈ B(q). Now 2^{p−1} − 2 = 1 \underbrace{1 ⋯ 1}_{p−3 1’s} 0, so 2^{p−1} − 2 ∈ B(p). Since the sets

B(q) and B(p) are disjoint if p ≠ q, we must have that p = q. Therefore, we have v ∈ B(p).

(⇐) By Lemma 13, there is a t such that R^{t}(0, v) = (0, 2^{q−1} − 2) for some q ≥ 3. If v ∈ B(p), then so 2^{q−1} − 2 ∈ B(p). In particular, reasoning as above, p = q, so (0, v) is ultimately periodic with period p by Proposition 11.

The importance of Proposition 17 is due to Lemma 9. Since, for any (u, v) ∈ X, there is a minimal t such that R^{t}(u, v) = (0, v′) for some v′, to know the period of (u, v) we simply need to know the form of the binary representation of v′.

Definition 18. For any set Y ⊂ X and any integer p ≥ 3, let

N(Y, p) = #{(u, v) ∈ Y : (u, v) is ultimately periodic with period p}.

We now compute N(Y, p) for special cases of Y.

Proposition 19. For p ≥ 3 and k ≥ p − 1, let Y_{k} := {(0, v) : 1 ≤ v < 2^{k}}. Then

N(Y_{k}, p) = \begin{cases}\binom{k}{p−1}, & if p > 3; \\ \binom{k}{2} + \binom{k}{1}, & if p = 3. \end{cases}

Proof. By Proposition 17, (0, v) is ultimately periodic with period p if and only if v ∈ B(p).

Suppose first that p > 3. If 2^{j−1} ≤ v < 2^{j}, then v has j digits in its binary representation. We now count the number of ways in which v can have j digits in its binary representation and be of the form v = 1 \underbrace{∗ ⋯ ∗0}_{p−3 1’s} 1 ⋯ 1. Suppose that the rightmost block of all 1’s of v is of

length i, where 0 ≤ i ≤ j + 1 − p. Then there are j − i − 2 unspecified digits of v of which p − 3 are 1’s and the rest are 0’s. The number of ways this can happen is \binom{j−i−2}{p−3}. So the total number of integers v with j digits in their binary representation of the necessary form is

\binom{j − 2}{p − 3} + \binom{j − 3}{p − 3} + ⋯ + \binom{p − 3}{p − 3} = \binom{j − 1}{p − 2}.

Summing over all possible j ≤ k, we get that

N(Y_{k}, p) = ∑_{j=p−1}^{k} \binom{j − 1}{p − 2} = \binom{k}{p − 1}.

Now suppose that p = 3. If 2^{j−1} ≤ v < 2^{j}, then v has j digits in its binary representation. We now count the number of ways in which v can have j digits in its binary representation and be of the form v = 10 ⋯ 01 ⋯ 1. Clearly there are only j numbers of this form. Summing over all possible j ≤ k, we get that

N(Y_{k}, 3) = ∑_{j=1}^{k} j = \frac{k(k + 1)}{2} = \binom{k + 1}{2} = \binom{k}{2} + \binom{k}{1}.

Corollary 20. Let P (v) denote the period of (0, v). Then, for any fixed M,

lim_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{M} e^{−t^{2}/2} dt.  (10)

and

lim_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M\} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{M} e^{−t^{2}/2} dt  (11)

In other words, asymptotically, the periods of (0, v) for 1 ≤ v ≤ 2^{k} have a Gaussian distribution with mean \frac{1}{2} log_{2} v and standard deviation \sqrt{\frac{1}{2} log_{2} v}.

Proof. First note that, by Theorem 6, P (v) ≥ 3 for any v. Also note that P (2^{k}) = 3 by Proposition 17. By Proposition 19, for k sufficiently large,

#\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M\} = #\{v ≤ 2^{k} : P (v) ≤ k/2 + M\sqrt{k/2}\}

= 1 + N(Y_{k}, 3) + ∑_{3<p≤k/2+M\sqrt{k/2}} N(Y_{k}, p)

= \binom{k}{0} + \binom{k}{1} + \binom{k}{2} + ∑_{3<p≤k/2+M\sqrt{k/2}} \binom{k}{p − 1}

= ∑_{1≤p≤k/2+M\sqrt{k/2}} \binom{k}{p − 1}.

An application of the de Moivre–Laplace limit theorem [3, p. 186] gives (10).

To prove (11), notice first that, for v ≤ 2^{k},

\frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≥ \frac{P (v) − k/2}{\sqrt{k/2}},

so

lim sup_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M\} ≤ lim_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M\}

= \frac{1}{\sqrt{2π}} ∫_{−∞}^{M} e^{−t^{2}/2} dt

by (10). This proves the upper bound in (11).

It remains to show prove the lower bound in (11). Observe that for any v with 2^{k−k^{1/3}} ≤ v ≤ 2^{k}, we have k − k^{1/3} ≤ log_{2} v ≤ k. In particular, for such v,

\frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ \frac{P (v) − (k − k^{1/3})/2}{\sqrt{(k − k^{1/3})/2}}  (12)

= \frac{P (v) − k/2}{\sqrt{(k − k^{1/3})/2})} + \frac{k^{1/3}/2}{\sqrt{(k − k^{1/3})/2}}

= \frac{1}{\sqrt{1 − k^{−2/3}}} (\frac{P (v) − k/2}{\sqrt{k/2}} + \frac{1}{\sqrt{2}k^{1/6}} )

≤ (1 + \frac{2}{k^{2/3}} )(\frac{P (v) − k/2}{\sqrt{k/2}} + \frac{1}{\sqrt{2}k^{1/6}} ),

provided k is sufficiently large. So, for any ϵ > 0, we have that

#\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M − ϵ\} = #\{2^{k−k^{1/3}} ≤ v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M − ϵ\} (13)
+ O(2^{k−k^{1/3}}).

By (12), the right-hand side of (13) is

≤ #\{2^{k−k^{1/3}} ≤ v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M − ϵ + \frac{2(M − ϵ)}{k^{2/3}} + \frac{1}{\sqrt{2}k^{1/6}} + \frac{\sqrt{2}}{k^{5/6}} \}

+ O(2^{k−k^{1/3}})

≤ #\{2^{k−k^{1/3}} ≤ v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M − ϵ + \frac{2M}{k^{2/3}} + \frac{3}{\sqrt{2}k^{1/6}} \} + O(2^{k−k^{1/3}})

≤ #\{v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M − ϵ + \frac{2M}{k^{2/3}} + \frac{3}{\sqrt{2}k^{1/6}} \} + O(2^{k−k^{1/3}}).

In particular, for all k large enough such that

\frac{2M}{k^{2/3}} + \frac{3}{\sqrt{2}k^{1/6}} < ϵ,

we have

#\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M − ϵ\} ≤ #\{v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M\} + O(2^{k−k^{1/3}}).

Therefore, taking the limit as k → ∞, we get that

lim inf_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − \frac{1}{2} log_{2} v}{\sqrt{\frac{1}{2} log_{2} v}} ≤ M\} ≥ lim_{k→∞} \frac{1}{2^{k}} #\{v ≤ 2^{k} : \frac{P (v) − k/2}{\sqrt{k/2}} ≤ M − ϵ\}

= \frac{1}{\sqrt{2π}} ∫_{−∞}^{M−ϵ} e^{−t^{2}/2} dt

for all ϵ > 0. This proves the lower bound in (11).

Proposition 21. For p > 3, let Y (j, i) = {(u, v) : 2^{j} ≤ u < 2^{j+1}, 2^{i} ≤ v < 2^{i+1}}. Then,

N(Y (j, i), p) = \begin{cases}2^{j}\binom{i}{p−3}, & if i < j; \\ 2^{i}[\binom{i}{p−2} + \binom{i−1}{p−3}] + \binom{i}{p−3} − ∑_{k=p−2}^{i} 2^{k−1}[\binom{k−1}{p−3} + \binom{k−2}{p−4}], & if i = j. \end{cases}

Proof. Suppose first that i < j. Then 0 < v < 2^{i+1} ≤ 2^{j} ≤ u, so, by Lemma 8, R^{2}(u, v) = R(2v, 0) = (0, 2v). This means that the period of (u, v) depends only on v. Letting P (u, v) denote the period of (u, v),

N(Y (j, i), p) = ∑_{2^{j}≤u<2^{j+1}} ; 2^{i}≤v<2^{i+1} ; P (u,v)=p 1  (14)

= 2^{j} ∑_{2^{i}≤v<2^{i+1}} ; P (0,2v)=p 1

= 2^{j} ∑_{2^{i+1}≤v<2^{i+2}} ; P (0,v)=p, 2|v 1.

The last sum in (14) is counting integers v that have i + 2 base 2 digits that are of the form v = 1 \underbrace{∗ ⋯ ∗0}_{p−3 1’s} . Note that the lack of trailing 1’s is due to the fact that v is even. Thus,

v has i unspecified digits of which p − 3 must be 1’s and the rest all 0’s. Clearly, there are \binom{i}{p−3} such v. Therefore, the proposition holds for i < j.

Now suppose that i = j. Then,

N(Y (i, i), p) = ∑_{2^{i}≤v,u<2^{i+1}} ; P (u,v)=p 1  (15)

= ∑_{2^{i}≤v≤u<2^{i+1}} ; P (u,v)=p 1 + ∑_{2^{i}≤u<v<2^{i+1}} ; P (u,v)=p 1.

Of the last two sums in (15), the first is

∑_{2^{i}≤v≤u<2^{i+1}} ; P (u,v)=p 1 = ∑_{2^{i}≤v<2^{i+1}} ; P (0,2v)=p ∑_{v≤u<2^{i+1}} 1  (16)

= ∑_{2^{i}≤v<2^{i+1}} ; P (0,2v)=p(2^{i+1} − v)

= ∑_{2^{i+1}≤v<2^{i+2}} ; P (0,v)=p, 2|v (2^{i+1} − \frac{v}{2})

= 2^{i+1}\binom{i}{p − 3} − \frac{1}{2} ∑_{2^{i+1}≤v<2^{i+2}} ; P (0,v)=p, 2|v v,

where the last equality holds due to (14). We now evaluate the last sum in (16). Notice that the last sum is summing all numbers of the form v = 2^{i+1} + a_{i}2^{i} + ⋯ + a_{1}2 with exactly p − 3 a_{m}’s equal to 1 and the rest all 0. The total number of v’s in the last sum is \binom{i}{p−3} by the argument above. Moreover, for any fixed m with 1 ≤ m ≤ i, there are \binom{i−1}{p−4} integers in the sum with a_{m} = 1. Hence the last sum in (16) is

∑_{2^{i+1}≤v<2^{i+2}} ; P (0,v)=p, 2|v v = 2^{i+1}\binom{i}{p − 3} + \binom{i − 1}{p − 4} ∑_{m=1}^{i} 2^{m}  (17)

= 2^{i+1}\binom{i}{p − 3} + 2\binom{i − 1}{p − 4}(2^{i} − 1).

Combining (16) and (17), we get that

∑_{2^{i}≤v≤u<2^{i+1}} ; P (u,v)=p 1 = 2^{i}[\binom{i}{p − 3} − \binom{i − 1}{p − 4}] + \binom{i − 1}{p − 4}.  (18)

For the second sum in (15), we get that

∑_{2^{i}≤u<v<2^{i+1}} ; P (u,v)=p 1 = ∑_{2^{i}≤u<v<2^{i+1}} ; P (0,2(v−u))=p 1

= ∑_{1≤v<2^{i}} ; P (0,2v)=p(2^{i} − v)

= ∑_{1<v<2^{i+1}} ; P (0,v)=p, 2|v (2^{i} − \frac{v}{2}),

where the first equality follows from the fact that, by Lemma 8, R^{3}(u, v) = (0, 2(v − u)), since u < v ≤ 3u. So,

∑_{1≤v<2^{i+1}} ; P (0,v)=p, 2|v (2^{i} − \frac{v}{2}) = ∑_{k=0}^{i} ∑_{2^{k}≤v<2^{k+1}} ; P (0,v)=p, 2|v (2^{i} − \frac{v}{2})  (19)

= ∑_{k=p−2}^{i} [2^{i}\binom{k − 1}{p − 3} − \frac{1}{2} ∑_{2^{k}≤v<2^{k+1}} ; P (0,v)=p, 2|v v]

= 2^{i}\binom{i}{p − 2} − ∑_{k=p−2}^{i} [2^{k−1}\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}(2^{k−1} − 1)]

= 2^{i}\binom{i}{p − 2} − ∑_{k=p−2}^{i} 2^{k−1}[\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}] + ∑_{k=p−2}^{i} \binom{k − 2}{p − 4}

= 2^{i}\binom{i}{p − 2} + \binom{i − 1}{p − 3} − ∑_{k=p−2}^{i} 2^{k−1}[\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}],

using similar reasoning as was used for the first sum in (15).

Combining (18) and (19) gives that

N(Y (i, i), p) = 2^{i}[\binom{i}{p − 3} − \binom{i − 1}{p − 4}] + \binom{i − 1}{p − 4}

+ 2^{i}\binom{i}{p − 2} + \binom{i − 1}{p − 3} − ∑_{k=p−2}^{i} 2^{k−1}[\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}]

= 2^{i}[\binom{i}{p − 2} + \binom{i}{p − 3} − \binom{i − 1}{p − 4}] + \binom{i − 1}{p − 3} + \binom{i − 1}{p − 4}

− ∑_{k=p−2}^{i} 2^{k−1}[\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}]

= 2^{i}[\binom{i}{p − 2} + \binom{i − 1}{p − 3}] + \binom{i}{p − 3} − ∑_{k=p−2}^{i} 2^{k−1}[\binom{k − 1}{p − 3} + \binom{k − 2}{p − 4}].

The last equality follows after two applications of the binomial coefficient identity \binom{n}{k} = \binom{n−1}{k} + \binom{n−1}{k−1}.

The exact formula for N(Y (j, i), p) when j < i is significantly harder to compute. This is because, in this case, we are given elements (u, v) with u < v. If k is the smallest integer such that v ≤ (2^{k+1} − 1)u, then R^{k+2}(u, v) = R^{2}(2^{k}, v − u(2^{k} − 1)) = (0, 2v − 2u(2^{k} − 1)). So the period of (u, v) depends on the base 2 representation of 2v − 2u(2^{k} − 1), which is difficult to predict in the set Y (j, i). We expect, however, that over large subsets of X, periods are distributed nicely, as in Corollary 20.

At this time, we cannot prove an Erdős-Kac type result for sets of the form {(u, v) : 0 ≤ u, v ≤ V } due to the difficulty encountered in the discussion above. Instead, we prove a weaker Hardy-Ramanujan type result for these sets.

Theorem 22. Let Y (V) = {(u, v) : 0 ≤ u, v < V } and let P (u, v) denote the period of (u, v). Then, for every ϵ > 0,

lim_{V →∞} \frac{1}{V^{2}} #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V)\} = 0.  (20)

Proof. Let ϵ > 0 be given. Fix a positive integer M > 0. Then

\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V)\} = A_{1}(V) ∪ A_{2}(V) ∪ A_{3}(V) ∪ A_{4}(V),

where

A_{1}(V) = \{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), (2^{M} − 1)u ≤ v\},
A_{2}(V) = ⋃_{i=1}^{M−1} A_{2,i}(V),

A_{3}(V) = ⋃_{i=1}^{M−1} \{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), (2^{i} − 1)u = v\},
A_{4}(V) = \{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), v < u\},

with

A_{2,i}(V) = \{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), (2^{i} − 1)u < v < (2^{i+1} − 1)u\} (21)

for 1 ≤ i ≤ M − 1.

We first estimate #A_{1}(V) by

#A_{1}(V) = #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), (2^{M} − 1)u ≤ v\} (22)

≤ #{(u, v) ∈ Y (V) : (2^{M} − 1)u ≤ v}

≤ \frac{V}{2^{M} − 1} · V + O(V).

For #A_{3}(V), we estimate this quantity crudely by

#A_{3}(V) ≤ ⋃_{i=1}^{M−1} #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), (2^{i} − 1)u = v\} (23)

≤ ⋃_{i=1}^{M−1} #{(u, v) ∈ Y (V) : (2^{i} − 1)u = v}

≤ 2MV.

Recall that, by Lemma 8, for 0 < v < u, we have R^{2}(u, v) = (0, 2v) and hence P (u, v) = P (0, 2v). So, for #A_{4}(V), we have that

#A_{4}(V) = #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V), v < u\}  (24)

≤ V · #\{v ≤ V : |P (0, 2v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V)\}

≤ V · #\{v′ ≤ 2V : |P (0, v′) − \frac{1}{2} log_{2}(2V)| > \frac{ϵ}{2} log_{2}(2V) − \frac{1 + ϵ}{2}\}

= o(V^{2})

as V → ∞, where the little–oh bound follows from Corollary 20. (Note that, in the notation in Corollary 20, P (0, 2v) = P (2v).)

For #A_{2}(V), we first estimate #A_{2,i}(V) for 1 ≤ i ≤ M − 1. Note that, by (5), if (2^{i} − 1)u < v < (2^{i+1} − 1)u, then R^{i+2}(u, v) = (0, 2(v − (2^{i} − 1)u)) and hence P (u, v) = P (0, 2(v − (2^{i} − 1)u)). So, we have that

#A_{2,i}(V) = #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V),
(2^{i} − 1)u < v < (2^{i+1} − 1)u}

= #\{(u, v) ∈ Y (V) : |P (0, 2(v − (2^{i} − 1)u) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V),

0 < 2(v − (2^{i} − 1)u) < 2^{i+1}u}

≤ V · #\{v ≤ V : |P (0, 2v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V)\}

= o(V^{2})

by (24). It follows that

#A_{2}(V) ≤ ∑_{i=1}^{M−1} #A_{2,i}(V)  (25)
= o(V^{2})

as V → ∞, for any fixed M.

Combining all four estimates (22), (23), (24), and (25), we get that

lim sup_{V →∞} \frac{1}{V^{2}} #\{(u, v) ∈ Y (V) : |P (u, v) − \frac{1}{2} log_{2}(V)| > \frac{ϵ}{2} log_{2}(V)\}  (26)

≤ lim sup_{V →∞} \frac{1}{V^{2}} ∑_{i=1}^{4} #A_{i}(V)

≤ \frac{1}{2^{M} − 1}.

Since (26) holds for all fixed M, letting M → ∞, we get (20).

Theorem 22 roughly states that most sorted integers \underbrace{1 ⋯ 1}_{u 1’s} \underbrace{2 ⋯ 2}_{v 2’s}, in base 3, have their

period close to \frac{1}{2} log_{2} v.

4 Acknowledgments

The author would like to thank his advisor, A. J. Hildebrand, for all of his helpful suggestions, particularly regarding Theorem 22.

References

[1] John H. Conway, Play it again..and again..., Quantum 63 (1990), 30–31.

[2] Curtis Cooper and Robert E. Kennedy, On Conway’s RATS, Mathematics in College (1998), 28–35. Available at

   http://www.math-cs.ucmo.edu/~curtisc/articles/rats2.pdf.

[3] William Feller, An Introduction to Probability Theory and its Applications, Vol. I, 3rd edition, John Wiley & Sons Inc., 1968.

[4] Karen Gentges, On Conway’s RATS, Master’s thesis, Central Missouri State University, 1998.

[5] Richard K. Guy, Unsolved Problems in Number Theory, third edition, Springer-Verlag, 2004.

[6] D. R. Kaprekar, Another solitaire game, Scripta Math. 15 (1949), 244–245.

[7] The On-Line Encyclopedia of Integer Sequences, http://www.oeis.org.

2010 Mathematics Subject Classification: Primary 11A63. Keywords: Conway’s RATS, ultimately periodic, digital problems, iterate.

(Concerned with sequence \underline{A066711}.)

Received May 30 2012; revised version received November 1 2012. Published in Journal of Integer Sequences, November 4 2012.

Return to Journal of Integer Sequences home page.