<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage{subfig}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Conway's RATS Sequences in Base 3
}
\vskip 1cm
\large
Johann Thiel\\
Department of Mathematical Sciences \\
United States Military Academy \\
West Point, NY 10996 \\
USA \\
\href{mailto:johann.thiel@usma.edu}{\tt johann.thiel@usma.edu} \\
\end{center}

\vskip .2 in

\newcommand{\be}{\begin{enumerate}
\renewcommand{\labelenumi}{\upshape{(\roman{enumi})}}}
\newcommand{\ee}{\end{enumerate}}

\begin{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\H os-Kac and Hardy-Ramanujan type results for the periods of such sequences.
\end{abstract}

\section{Introduction}
\label{sec:intro}

John H. Conway has invented many mathematical games, including the well
known Game of Life. In 1990, Conway \cite{Co} created a new game
inspired by Kaprekar \cite{Ka} 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.

\begin{example} We play the RATS game beginning with $n=9$ (sequence \seqnum{A066711} in \cite{OEIS}).
\begin{align*}
 \begin{tabular}{r}
     $9$ \\
     $+\text{ }9$\\
     \hline
     $18$
 \end{tabular}
 \phantom{\rightarrow}
 \begin{tabular}{r}
     $18$ \\
     $+\text{ }81$\\
     \hline
     $99$
 \end{tabular}
 \phantom{\rightarrow}
 \begin{tabular}{r}
     $99$ \\
     $+\text{ }99$\\
     \hline
     $198$
 \end{tabular}
 \phantom{\rightarrow}
 \begin{tabular}{r}
     $189$ \\
     $+\text{ }981$\\
     \hline
     $1170$
 \end{tabular}
 \phantom{\rightarrow}
 \begin{tabular}{r}
     $117$ \\
     $+\text{ }711$\\
     \hline
     $828$
 \end{tabular}
 \phantom{\rightarrow}
 \begin{tabular}{r}
     $288$ \\
     $+\text{ }882$\\
     \hline
     $1170$
 \end{tabular}
\end{align*}
In this particular case, the game ends after six iterations and yields the sequence
\begin{align}
 9\mapsto 18\mapsto 99\mapsto 189\mapsto 117\mapsto 288\mapsto 117\mapsto\cdots,\label{firstexample}
\end{align}
with the terms $288$ and $117$ forming a cycle with period $2$.
\end{example}

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.

\begin{definition} 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\colon \mathbb{N}\rightarrow\mathbb{N}$ by $R(n)=(n+\overline{n})'$.
\end{definition}

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\geq 1$ and $R^0(n)=n$.

\begin{definition}
We call $\{R^i(n)\}_{i=0}^\infty$ the \textit{RATS sequence generated by} $n$ \textit{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.
\end{definition}

\begin{example}
\begin{align*}
 R^2(10012) &amp; = R((10012+21001)')\\
                 &amp; = R((101020)')\\
                 &amp; = R(112)\\
                 &amp; = (112+211)'\\
                 &amp; = (1100)'\\
                 &amp; = 11
\end{align*}
\end{example}

\begin{definition}
 If $R^p(n)=n$ for some $p&gt;0$, we say that $n$ and the RATS sequence generated by $n$ are \textit{periodic}. If $p$ is the least integer with this property, we say that the \textit{period} is $p$. If $R^t(n)$ is periodic for some $t\geq 0$, we say that $n$ and the RATS sequence generated by $n$ are \textit{ultimately periodic}. (Periodic sequences are sometimes referred to as ``cycles'' and ultimately periodic sequences are ``tributaries'' to a cycle \cite[p.\ 404]{Gu2}.)
\end{definition}

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 \emph{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\geq 0$; that is, the sequence $\{R^t(n)\}_{t=0}^\infty$ is periodic, in the usual sense, with period $p$.

\section{Periodic behavior}

Gentges \cite{Ge}  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.

\begin{theorem}[Gentges, \cite{Ge}]\label{base3char}
 Every RATS sequence in base $3$ is ultimately periodic. Furthermore, if $\mathcal{P}$ is the set of all $p$ for which there are periodic elements with period $p$, then $\mathcal{P}=\{p:p\geq 3\}$.
\end{theorem}

Before proving Theorem \ref{base3char}, we introduce some helpful notation and prove some necessary, auxiliary lemmas.

\begin{definition}\label{base3vec}
 We define a one-to-one correspondence between sorted integers in base $3$ and $X:=\mathbb{Z}_{\geq 0}^2\setminus\{(0,0)\}$ by $\underbrace{1\cdots 1}_{u\phantom{a}1\text{'s}}\underbrace{2\cdots 2}_{v\phantom{a}2\text{'s}}\leftrightarrow (u,v)$. With this correspondence, we use $R(u,v)$ to mean $R(\underbrace{1\cdots 1}_{u\phantom{a}1\text{'s}}\underbrace{2\cdots 2}_{v\phantom{a}2\text{'s}})$ and we extend any terminology from Section \ref{sec:intro} to $(u,v)$.
\end{definition}

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.

\begin{lemma}\label{base3Rchar}
 Given any element $(u,v)$ representing a sorted integer, we have that:

\be
\item if $v=0$, $R(u,v)=(0,u)$;
\item if $u&gt;v&gt;0$, $R(u,v)=(2v,0)$;
\item if $0&lt;u\leq v$, $R(u,v)=(2u,v-u)$;
\item if $u=0$, $R(u,v)=(2,v-1)$.
\ee
\end{lemma}

\begin{proof} If $u=0$, we have that
\begin{align*}
 \begin{tabular}{r}
     $22\cdots 22$\\
     + $22\cdots 22$\\
     \hline
     $122\cdots 21$
 \end{tabular}
\end{align*}
So $R(0,v)=(2,v-1)$, proving (iv).

The assertions (i)--(iii) can all be proved in a similar fashion.
\end{proof}

\begin{lemma}\label{eventualbase3}
 Given any $(u,v)$, there is a $t&gt;0$ such that $R^t(u,v)=(0,v')$ for some $v'$.
\end{lemma}

\begin{proof}
\textbf{Case 1.} If $v=0$, then $R(u,0)=(0,u)$, by Lemma \ref{base3Rchar}(i), so the statement holds with $t=1$.

\textbf{Case 2.} If $u&gt;v&gt;0$, then $R^2(u,v)=R(2v,0)=(0,2v)$ by using Lemma \ref{base3Rchar} (ii) and (i). So the statement holds with $t=2$.

\textbf{Case 3.} If $0&lt;u\leq v$, then $R(u,v)=(2u,v-u)$, again by Lemma \ref{base3Rchar}. If $2u\leq 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'&gt;v'\geq 0$, i.e., an element that falls into case 1 or case 2.

\textbf{Case 4.} If $u=0$, then $R(0,v)=(2,v-1)$, which leads to case $3$ if $v\geq 3$, to case 2 if $v=2$, and to case 1 if $v=1$.
\end{proof}

The above argument can be illustrated by the directed graph in Figure \ref{fig:directedbase3}. 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$.

\begin{figure}[ht]
  \centering
 \includegraphics{graph1thiel.eps}
 \caption{Directed graph of cases in Lemma \ref{eventualbase3}.}
  \label{fig:directedbase3}
\end{figure}

It follows from Lemma \ref{eventualbase3} that for any $(u,v)$, there is a minimal $t&gt;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\neq 2^k-1$ for $k\geq 1$.

\begin{lemma}\label{decreaseb}
 If $2^k-1&lt;v&lt;2^{k+1}-1$ for some $k\geq 1$ and $t&gt;0$ is minimal such that $R^t(0,v)=(0,v')$ for some $v'$, then $t=k+2$ and
\begin{align}
 v'=2v-2^{k+1}+2.\label{vprime}
\end{align}
In particular,
\begin{align}
 v'\leq v,
\end{align}
 since $v\leq 2^{k+1}-2$.
\end{lemma}

\begin{proof}By repeated applications of cases (iv) and (iii) from Lemma \ref{base3Rchar}, it follows that
\begin{align}
R^s(0,v)=(2^s,v-2^s+1)\label{case3s}
\end{align}
for $0&lt;s\leq k$. (Note that \eqref{case3s} holds even in the case $v=2^k-1$.)

If $v=2^k$, then, by \eqref{case3s} and two further applications of cases (ii) and (i) from Lemma \ref{base3Rchar}, $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\geq 2$, the assertion holds in this case.

If $2^k&lt;v&lt;2^{k+1}-1$, then, by \eqref{case3s} and Lemma \ref{base3Rchar},
\begin{align}
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).\label{multiR}
\end{align}
The upper bound $v&lt;2^{k+1}-1$ is equivalent to the inequality $2v-2^{k+1}+2\leq v$, so the assertion also holds in this case.
\end{proof}

\begin{proposition}\label{charperiodbase3}
 In base $3$, for any integer $p\geq 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\geq 3$.
\end{proposition}

\begin{proof}
$(\Leftarrow)$ If $v=2^{p-1}-2$ for some $p\geq 3$, then, by \eqref{case3s} and Lemma \ref{base3Rchar}, the RATS sequence generated by $(0,2^{p-1}-2)$ after $p$ iterations is
\begin{align}\label{periodseq}
(0,2^{p-1}-2)\overset{\text{(iv)}}{\mapsto} (2,2^{p-1}-3)\overset{\text{(iii)}}{\mapsto}\underbrace{\cdots}_{p-3\text{ times}}\overset{\text{(iii)}}{\mapsto} (2^{p-2},2^{p-2}-1)\overset{\text{(ii)}}{\mapsto}(2^{p-1}-2,0)\overset{\text{(i)}}{\mapsto}(0,2^{p-1}-2).
\end{align}
Therefore, $(0,v)$ is periodic with period $p$.

$(\Rightarrow)$ Let $(0,v)$ be periodic with period $p$. Now if $2^k-1\leq v&lt;2^{k+1}-1$ for some integer $k&gt;1$, then $R^k(0,v)=(2^k,v-2^k+1)$ by \eqref{case3s}.

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)\overset{\text{(iv)}}{\mapsto}(2,1)\overset{\text{(ii)}}{\mapsto}(2,0)\overset{\text{(i)}}{\mapsto}(0,2)$ and hence is itself not periodic if $k&gt;1$:
\begin{equation}\label{2per3}
(0,2^k)\overset{\text{(iv)}}{\mapsto}(2,2^k-1)\overset{\text{(iii)}}{\mapsto}\cdots\overset{\text{(iii)}}{\mapsto}(2^k,1)\overset{\text{(ii)}}{\mapsto}(2,0).
\end{equation}
This shows that $v\notin\{2^k-1,2^k\}$.

Hence we must have that $2^k&lt;v&lt;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+\cdots+p_N$ for some $N&gt;1$ such that $0&lt;p_1&lt;p$ is minimal such that $R^{p_1}(0,v)=(0,v_1)$ for some $v_1$, $0&lt;p_2&lt;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&lt;i&lt;N$, $2^{k_i}&lt;v_i&lt;2^{k_i+1}-1$ for some $k_i&gt;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 \eqref{2per3}. By Lemma \ref{decreaseb}, it follows that $v=v_N\leq v_{N-1}\leq\cdots\leq v_1\leq 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 \eqref{multiR}, we get that $v=2v-2^{p-1}+2$, as desired.

The case $1\leq v&lt;3$ can be handled by inspection. This completes the proof of the proposition.
\end{proof}

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

\begin{corollary}
 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 \eqref{periodseq}.
\end{corollary}

\begin{proof}
 $(\Leftarrow)$ By Proposition \ref{charperiodbase3}, $(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$.

 $(\Rightarrow)$ By Lemma \ref{eventualbase3}, 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 \ref{charperiodbase3}, 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 \eqref{periodseq} is the periodic sequence generated by $(0,2^{p-1}-2)$.
\end{proof}

\begin{lemma}\label{preper3}
 Given any $(u,v)$, there is a $t$ such that $R^t(u,v)=(0,2^{p-1}-2)$ for some $p\geq3$.
\end{lemma}

\begin{proof}
 By Lemma \ref{eventualbase3}, there is a minimal $t&gt;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\leq v&lt;2^{k+1}-1$ for some positive integer $k$. Then Lemma \ref{decreaseb} shows that either $v=2^k-1$ or $v'\leq v$.

\textbf{Case 1.} If $v=2^k-1$, then there is a $t$ such that $R^t(0,v)=(0,2)$ (see \eqref{2per3}).

\textbf{Case 2.} If $v=v'$, $(0,v)$ is periodic, so the assertion holds by Proposition \ref{charperiodbase3}.

\textbf{Case 3.} If $v'&lt;v$, we apply Lemma \ref{eventualbase3} 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 \ref{eventualbase3} leads to case 1 or 2.
\end{proof}

\begin{proof}[Proof of Theorem \ref{base3char}]
 Lemma \ref{preper3} establishes that all RATS sequences in base $3$ are ultimately periodic, Proposition \ref{charperiodbase3} shows that $\{p:p\geq 3\}\subset\mathcal{P}$, and a simple modification of a theorem of Cooper and Kennedy \cite[p.\ 7]{KeCo2}
 shows that $1\notin\mathcal{P}$. It remains to show that $2\notin\mathcal{P}$.

 Suppose that $(u,v)$ is periodic with period $2$. Let $(u',v')=R(u,v)$. By studying Figure \ref{fig:directedbase3}, 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 \ref{base3char}), or, alternatively, one would need to have $0&lt;u\leq v$ and $0&lt;u'\leq v'$ (both case 3 of Lemma \ref{base3char}).

 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&lt;u\leq v$ and $0&lt;u'\leq 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\notin\mathcal{P}$.
\end{proof}

\section{Distribution of periods}
%\label{sec:ch3dist}

In the previous section we showed that every RATS sequence in base 3 is ultimately periodic and we constructed elements $(u,v)\in X$ that are periodic with any desired period $p\geq 3$. In this section, we seek to answer the following question: Given $p\geq 3$ and a set $Y\subset X$, how many elements $(u,v)\in Y$ are ultimately periodic with period $p$? In other words, given some collection of sorted integers $\underbrace{1\cdots 1}_{u\phantom{a}1\text{'s}}\underbrace{2\cdots 2}_{v\phantom{a}2\text{'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\leq v&lt; 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.

\begin{figure}[ht]
  \centering
  \subfloat{
\begin{tabular}{|c|c|c|}
\hline
$v$ &amp; base $2$&amp; period of $(0,v)$\\
\hline
 32&amp; 100000&amp; 3\\
\hline
 33&amp; 100001&amp; 3\\
\hline
 34&amp; 100010&amp; 4\\
\hline
 35&amp; 100011&amp; 3\\
\hline
 36&amp; 100100&amp; 4\\
\hline
 37&amp; 100101&amp; 4\\
\hline
 38&amp; 100110&amp; 5\\
\hline
 39&amp; 100111&amp; 3\\
\hline
 40&amp; 101000&amp; 4\\
\hline
 41&amp; 101001&amp; 4\\
\hline
 42&amp; 101010&amp; 5\\
\hline
\end{tabular}
}
\subfloat{
\begin{tabular}{|c|c|c|}
\hline
$v$ &amp; base $2$&amp; period of $(0,v)$\\
\hline
 43&amp; 101011&amp; 4\\
\hline
 44&amp; 101100&amp; 5\\
\hline
 45&amp; 101101&amp; 5\\
\hline
 46&amp; 101110&amp; 6\\
\hline
 47&amp; 101111&amp; 3\\
\hline
 48&amp; 110000&amp; 4\\
\hline
 49&amp; 110001&amp; 4\\
\hline
 50&amp; 110010&amp; 5\\
\hline
 51&amp; 110011&amp; 4\\
\hline
 52&amp; 110100&amp; 5\\
\hline
 53&amp; 110101&amp; 5\\
\hline
\end{tabular}
}
  \caption{Base $2$ representation of $v$ and period of $(0,v)$.}
  \label{fig:b2per}
\end{figure}

\begin{definition}
For a positive integer $p\geq 3$, let
\begin{align*}
B(p):=\{v\in\mathbb{Z}_{&gt;0}: v=1\underbrace{{\ast}\cdots{\ast}0}_{p-3\phantom{a}1\text{'s}}1\cdots 1\text{ in binary}\},
\end{align*}
where we allow for the possibility that the bracketed block or the rightmost block of consecutive $1$'s is empty.
\end{definition}

\begin{example}
From Figure \ref{fig:b2per}, we see that $45, 50\in B(5)$, since $45=1\underbrace{0110}_{2\phantom{a}1\text{'s}}1$ and $50=1\underbrace{10010}_{2\phantom{a}1\text{'s}}$. We also have that $7,35\in B(3)$, since $7=111$ and $35=1\underbrace{000}_{0\phantom{a}1\text{'s}}11$.
\end{example}

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\in 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 \ref{fig:b2per} suggests that if $v\in B(p)$, then $(0,v)$ is ultimately periodic with period $p$. Indeed this is the case, as we will show in Proposition \ref{keybase3}.

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.

\begin{lemma}\label{keylemma}
If $v\in B(q)$ for some $q\geq 3$ and there is a $t&gt;0$ such that $R^t(0,v)=(0,v')$, then $v'\in B(q)$.
\end{lemma}

\begin{proof}
 Suppose that we are given $(0,v)$ with $v\in B(q)$ for some $q\geq 3$. Furthermore, suppose that $2^{k-1}\leq v&lt;2^k$; i.e., that $v$ is $k$ digits long.

\textbf{Case 1.} If $v=2^{k-1}$, then $v\in B(3)$ since $v=10\cdots 0$. By Lemma \ref{decreaseb}, $R^{k+2}(0,v)=R^2(2^{k-1},1)=R(2,0)=(0,2)$. Since $2\in B(3)$, the assertion of the lemma holds in this case.

\textbf{Case 2.} If $v=2^k-1$, then $v\in B(3)$ since $v=1\cdots 1$. By \eqref{case3s}, $R^{k+1}(0,v)=R(2^k,0)=(0,2^k)$. Since $2^k\in B(3)$, the assertion of the lemma holds in this case.

\textbf{Case 3.} If $2^{k-1}&lt;v&lt;2^k-1$, then, by \eqref{multiR}, $R^{k+2}(0,v)=(0,2v-2^k+2)$. As in the previous two cases, we aim to show that if $v\in B(q)$ for some $q\geq 3$, then $2v-2^k+2\in B(q)$.

Subtracting $2^{k-1}$ from $v$ simply plucks the leftmost zero from the binary representation of $v$. If $v\in B(q)$ for some $q&gt;3$, then
\begin{align*}
 v-2^{k-1} &amp; = 1\underbrace{{\ast}\cdots{\ast}0}_{p-3\text{ 1's}}1\cdots 1 -10\cdots 0\\
   	 &amp; = 1\underbrace{{\ast}\cdots{\ast}0}_{p-4\text{ 1's}}1\cdots 1,
\end{align*}
so $v-2^{k-1}\in B(q-1)$. Adding $1$ to the result gives
\begin{align}
 v-2^{k-1}+1 &amp; = 1\underbrace{{\ast}\cdots{\ast}0}_{p-4\text{ 1's}}1\cdots 1 +1\label{b(q)&gt;3}\\
   	 &amp; = 1\underbrace{{\ast}\cdots{\ast}1}_{p-3\text{ 1's}}0\cdots 0,\notag
\end{align}
so $v-2^{k-1}+1\in B(q)$. If $v\in B(3)$, then
\begin{align}
 v-2^{k-1}+1 &amp; = 10\cdots 01\cdots 1-10\cdots0+1\label{b(q)=3}\\
   	 &amp; = 1\cdots 1+1\notag\\
   	 &amp; = 10\cdots0,\notag
\end{align}
so $v-2^{k-1}+1\in B(3)$. Therefore, for any $v$ in case $3$, if $v\in B(q)$ for some $q\geq 3$, then $v-2^{k-1}+1\in 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 \eqref{b(q)&gt;3} and \eqref{b(q)=3}, we see that if $v-2^{k-1}+1\in B(q)$ for some $q\geq 3$, then $2v-2^k+2\in B(q).$

What this shows is that, by appealing to Lemma \ref{decreaseb}, if $v\in B(q)$ for some $q\geq 3$ and $t&gt;0$ is minimal such that $R^t(0,v)=(0,v')$, then $v'\in B(q)$. We now remove the word ``minimal'' from the previous statement with the following argument. If $t&gt;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+\cdots+t_N$ for some $N&gt;1$ such that $0&lt;t_1&lt;t$ is minimal such that $R^{t_1}(0,v)=(0,v_1)$ for some $v_1$, $0&lt;t_2&lt;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,\cdots, v_N\in B(q)$. Since $v'=v_N$, the assertion of the lemma holds.
\end{proof}

\begin{proposition}\label{keybase3}
 For any positive integer $v$, $(0,v)$ is ultimately periodic with period $p\geq 3$ if and only if $v\in B(p)$.
\end{proposition}

\begin{proof}
 $(\Rightarrow)$ If $(0,v)$ is ultimately periodic with period $p\geq 3$, then, by Proposition \ref{charperiodbase3} and Lemma \ref{preper3}, there is a $t$ such that $R^t(0,v)=(0,2^{p-1}-2)$. By Lemma \ref{keylemma}, if $v\in B(q)$ for some $q\geq 3$, then $2^{p-1}-2\in B(q)$. Now $2^{p-1}-2=1\underbrace{1\cdots 1}_{p-3\text{ 1's}}0$, so $2^{p-1}-2\in B(p)$. Since the sets $B(q)$ and $B(p)$ are disjoint if $p\neq q$, we must have that $p=q$. Therefore, we have $v\in B(p)$.

$(\Leftarrow)$ By Lemma \ref{preper3}, there is a $t$ such that $R^t(0,v)=(0,2^{q-1}-2)$ for some $q\geq 3$. If $v\in B(p)$, then so $2^{q-1}-2\in B(p)$. In particular, reasoning as above, $p=q$, so $(0,v)$ is ultimately periodic with period $p$ by Proposition \ref{charperiodbase3}.
\end{proof}

The importance of Proposition \ref{keybase3} is due to Lemma \ref{eventualbase3}. Since, for any $(u,v)\in 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'$.

\begin{definition}
 For any set $Y\subset X$ and any integer $p\geq 3$, let
\begin{displaymath}
 N(Y,p)=\#\{(u,v)\in Y: (u,v)\text{ is ultimately periodic with period }p\}.
\end{displaymath}
\end{definition}

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

\begin{proposition}\label{reallinecount}
 For $p\geq 3$ and $k\geq p-1$, let $Y_k:=\{(0,v): 1\leq v &lt; 2^k\}$. Then $$N(Y_k,p)=\begin{cases}
 \binom{k}{p-1}, &amp; \text{if $p&gt;3$;}\\
 \binom{k}{2}+\binom{k}{1}, &amp; \text{if $p=3$.}
 \end{cases}$$
\end{proposition}

\begin{proof}
By Proposition \ref{keybase3}, $(0,v)$ is ultimately periodic with period $p$ if and only if $v\in B(p)$.

Suppose first that $p&gt;3$. If $2^{j-1}\leq v&lt;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 $\displaystyle v=1\underbrace{{\ast}\cdots{\ast}0}_{p-3\text{ 1's}}1\cdots 1$. Suppose that the rightmost block of all $1$'s of $v$ is of length $i$, where $0\leq i\leq 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}+\cdots+\binom{p-3}{p-3}=\binom{j-1}{p-2}.$$ Summing over all possible $j\leq k$, we get that  $$N(Y_k,p)=\sum_{j=p-1}^{k}\binom{j-1}{p-2}=\binom{k}{p-1}.$$

Now suppose that $p=3$. If $2^{j-1}\leq v&lt;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 $\displaystyle v=10\cdots 01\cdots 1$. Clearly there are only $j$ numbers of this form. Summing over all possible $j\leq k$, we get that $$N(Y_k,3)=\sum_{j=1}^{k}j=\frac{k(k+1)}{2}=\binom{k+1}{2}=\binom{k}{2}+\binom{k}{1}.$$
\end{proof}

\begin{corollary}\label{normline}
 Let $P(v)$ denote the period of $(0,v)$. Then, for any fixed $M$,
\begin{align}
\lim_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M\Bigg\}&amp;=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^M e^{-t^2/2}\;dt.\label{ver2}
\end{align}
and
\begin{align}
\lim_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M\Bigg\} &amp;=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^M e^{-t^2/2}\;dt\label{ver1}
\end{align}
In other words, asymptotically, the periods of $(0,v)$ for $1\leq v\leq 2^k$ have a Gaussian distribution with mean $\frac{1}{2}\log_2{v}$ and standard deviation $\sqrt{\frac{1}{2}\log_2{v}}$.
\end{corollary}

\begin{proof}
 First note that, by Theorem \ref{base3char}, $P(v)\geq 3$ for any $v$. Also note that $P(2^k)=3$ by Proposition \ref{keybase3}. By Proposition \ref{reallinecount}, for $k$ sufficiently large,
\begin{align*}
 \#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M\Bigg\} &amp; = \#\Bigg\{v\leq 2^k: P(v)\leq k/2+M\sqrt{k/2}\Bigg\}\\
 &amp;= 1+N(Y_k,3)+\sum_{3&lt; p\leq k/2+M\sqrt{k/2}}N(Y_k,p)\\
 &amp;= \binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\sum_{3&lt; p\leq k/2+M\sqrt{k/2}}\binom{k}{p-1}\\
 &amp;= \sum_{1\leq p\leq k/2+M\sqrt{k/2}}\binom{k}{p-1}.
\end{align*}
An application of the de Moivre--Laplace limit theorem \cite[p.\ 186]{Fe} gives \eqref{ver2}.

To prove \eqref{ver1}, notice first that, for $v\leq 2^k$,  $$\frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\geq\frac{P(v)-k/2}{\sqrt{k/2}},$$
so
\begin{align*}
\limsup_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M\Bigg\} &amp; \leq \lim_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M\Bigg\}\\
&amp; = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^M e^{-t^2/2}\;dt
\end{align*}
by \eqref{ver2}. This proves the upper bound in \eqref{ver1}.

It remains to show prove the lower bound in \eqref{ver1}. Observe that for any $v$ with $2^{k-k^{1/3}}\leq v\leq 2^k$, we have $k-k^{1/3}\leq \log_2{v}\leq k$. In particular, for such $v$,
\begin{align}
\frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}} &amp; \leq \frac{P(v)-(k-k^{1/3})/2}{\sqrt{(k-k^{1/3})/2}}\label{reversedircorollary}\\
&amp; = \frac{P(v)-k/2}{\sqrt{(k-k^{1/3})/2})}+\frac{k^{1/3}/2}{\sqrt{(k-k^{1/3})/2}}\notag\\
&amp; = \frac{1}{\sqrt{1-k^{-2/3}}}\Bigg(\frac{P(v)-k/2}{\sqrt{k/2}}+\frac{1}{\sqrt{2}k^{1/6}}\Bigg)\notag\\
&amp; \leq \Bigg(1+\frac{2}{k^{2/3}}\Bigg)\Bigg(\frac{P(v)-k/2}{\sqrt{k/2}}+\frac{1}{\sqrt{2}k^{1/6}}\Bigg),\notag
\end{align}
provided $k$ is sufficiently large. So, for any $\epsilon&gt;0$, we have that
\begin{align}
\#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M-\epsilon\Bigg\}
 &amp; = \#\Bigg\{2^{k-k^{1/3}}\leq v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M-\epsilon\Bigg\}\label{longline}\\
 &amp;\qquad+O\big(2^{k-k^{1/3}}\big).\notag
\end{align}
By \eqref{reversedircorollary}, the right-hand side of (\ref{longline}) is
\begin{align*}
&amp;  \leq \#\Bigg\{2^{k-k^{1/3}}\leq v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M-\epsilon+\frac{2(M-\epsilon)}{k^{2/3}}+\frac{1}{\sqrt{2}k^{1/6}}+\frac{\sqrt{2}}{k^{5/6}}\Bigg\}\\
&amp;\qquad+O\big(2^{k-k^{1/3}}\big)\\
&amp;  \leq \#\Bigg\{2^{k-k^{1/3}}\leq v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M-\epsilon+\frac{2M}{k^{2/3}}+\frac{3}{\sqrt{2}k^{1/6}}\Bigg\}+O\big(2^{k-k^{1/3}}\big)\\
&amp;  \leq \#\Bigg\{v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M-\epsilon+\frac{2M}{k^{2/3}}+\frac{3}{\sqrt{2}k^{1/6}}\Bigg\}+O\big(2^{k-k^{1/3}}\big).
\end{align*}
In particular, for all $k$ large enough such that
\begin{align*}
\frac{2M}{k^{2/3}}+\frac{3}{\sqrt{2}k^{1/6}}&lt;\epsilon\label{kepsilon},
\end{align*}
we have
\begin{align*}
\#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M-\epsilon\Bigg\} &amp; \leq \#\Bigg\{v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M\Bigg\}+O\big(2^{k-k^{1/3}}\big).
\end{align*}
Therefore, taking the limit as $k\to\infty$, we get that
\begin{align*}
\liminf_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-\frac{1}{2}\log_2{v}}{\sqrt{\frac{1}{2}\log_2{v}}}\leq M\Bigg\} &amp; \geq
\lim_{k\to\infty}\frac{1}{2^k}\#\Bigg\{v\leq 2^k: \frac{P(v)-k/2}{\sqrt{k/2}}\leq M-\epsilon\Bigg\}\\
&amp; =\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{M-\epsilon} e^{-t^2/2}\;dt
\end{align*}
for all $\epsilon&gt;0$. This proves the lower bound in \eqref{ver1}.
\end{proof}

\begin{proposition}
For $p&gt;3$, let $Y(j,i)=\{(u,v): 2^j\leq u&lt;2^{j+1},2^i\leq v&lt;2^{i+1}\}$. Then,

 \begin{displaymath}
   N(Y(j,i),p) = \begin{cases}
   2^j\binom{i}{p-3}, &amp; \text{ if $i&lt;j$;}\\
   2^i\Big[\binom{i}{p-2}+\binom{i-1}{p-3}\Big]+\binom{i}{p-3}-\sum_{k=p-2}^{i}2^{k-1}\Big[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Big], &amp; \text{ if $i=j$.}
   \end{cases}
\end{displaymath}
\end{proposition}

\begin{proof}
Suppose first that $i&lt;j$. Then $0&lt;v&lt;2^{i+1}\leq 2^j\leq u$, so, by Lemma \ref{base3Rchar}, $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)$,
\begin{align}
 N(Y(j,i),p)  &amp; = \mathop{\mathop{\sum_{2^j\leq u&lt;2^{j+1}}}_{2^i\leq v&lt;2^{i+1}}}_{P(u,v)=p}1\label{i&gt;jsum}\\
 	&amp; = 2^j\mathop{\sum_{2^i\leq v&lt;2^{i+1}}}_{P(0,2v)=p}1\notag\\
 	&amp; = 2^j\mathop{\sum_{2^{i+1}\leq v&lt;2^{i+2}}}_{P(0,v)=p,\text{ }2|v}1.\notag
\end{align}

The last sum in (\ref{i&gt;jsum}) is counting integers $v$ that have $i+2$ base $2$ digits that are of the form $\displaystyle v=1\underbrace{{\ast}\cdots{\ast}0}_{p-3\text{ 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&lt;j$.

Now suppose that $i=j$. Then,
\begin{align}
 N(Y(i,i),p)  &amp; = \mathop{\sum_{2^i\leq v,u&lt;2^{i+1}}}_{P(u,v)=p}1\label{2partugly}\\
 	&amp; = \mathop{\sum_{2^i\leq v\leq u&lt;2^{i+1}}}_{P(u,v)=p}1+\mathop{\sum_{2^i\leq u&lt; v&lt;2^{i+1}}}_{P(u,v)=p}1\notag.
\end{align}

Of the last two sums in (\ref{2partugly}), the first is
\begin{align}
 \mathop{\sum_{2^i\leq v\leq u&lt;2^{i+1}}}_{P(u,v)=p}1 &amp; = \mathop{\sum_{2^i\leq v&lt;2^{i+1}}}_{P(0,2v)=p}\sum_{v\leq u&lt;2^{i+1}}1\label{sumsumming}\\
  &amp; = \mathop{\sum_{2^i\leq v&lt;2^{i+1}}}_{P(0,2v)=p}(2^{i+1}-v)\notag\\
  &amp; = \mathop{\sum_{2^{i+1}\leq v&lt;2^{i+2}}}_{P(0,v)=p\text{, }2|v}\bigg(2^{i+1}-\frac{v}{2}\bigg)\notag\\
  &amp; = 2^{i+1}\binom{i}{p-3}-\frac{1}{2}\mathop{\sum_{2^{i+1}\leq v&lt;2^{i+2}}}_{P(0,v)=p,\text{ }2|v}v,\notag
\end{align}
where the last equality holds due to \eqref{i&gt;jsum}. We now evaluate the last sum in \eqref{sumsumming}. Notice that the last sum is summing all numbers of the form $v=2^{i+1}+a_i2^i+\cdots+a_12$ 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\leq m\leq i$, there are $\binom{i-1}{p-4}$ integers in the sum with $a_m=1$. Hence the last sum in \eqref{sumsumming} is
\begin{align}
\mathop{\sum_{2^{i+1}\leq v&lt;2^{i+2}}}_{P(0,v)=p,\text{ }2|v}v &amp; = 2^{i+1}\binom{i}{p-3}+\binom{i-1}{p-4}\sum_{m=1}^i2^m\label{sumsumming2}\\
&amp; = 2^{i+1}\binom{i}{p-3}+2\binom{i-1}{p-4}(2^i-1)\notag.
\end{align}
Combining \eqref{sumsumming} and \eqref{sumsumming2}, we get that
\begin{align}
 \mathop{\sum_{2^i\leq v\leq u&lt;2^{i+1}}}_{P(u,v)=p}1 &amp; = 2^i\Bigg[\binom{i}{p-3}-\binom{i-1}{p-4}\Bigg]+\binom{i-1}{p-4}\label{uglysum1}.
\end{align}

For the second sum in (\ref{2partugly}), we get that
\begin{align*}
 \mathop{\sum_{2^i\leq u&lt;v&lt;2^{i+1}}}_{P(u,v)=p}1 &amp; = \mathop{\sum_{2^i\leq u&lt;v&lt;2^{i+1}}}_{P(0,2(v-u))=p}1\\
 &amp; = \mathop{\sum_{1\leq v&lt;2^i}}_{P(0,2v)=p}(2^i-v)\\
 &amp; = \mathop{\sum_{1&lt;v&lt;2^{i+1}}}_{P(0,v)=p\text{, }2|v}\bigg(2^i-\frac{v}{2}\bigg),
\end{align*}
where the first equality follows from the fact that, by Lemma \ref{base3Rchar}, $R^3(u,v)=(0,2(v-u))$, since $u&lt;v\leq 3u$. So,
\begin{align}
 \mathop{\sum_{1\leq v&lt;2^{i+1}}}_{P(0,v)=p\text{, }2|v}\bigg(2^i-\frac{v}{2}\bigg) &amp; = \sum_{k=0}^i\mathop{\sum_{2^k\leq v&lt;2^{k+1}}}_{P(0,v)=p\text{, }2|v}\bigg(2^i-\frac{v}{2}\bigg)\label{uglysum2}\\
 &amp; = \sum_{k=p-2}^i \Bigg[2^i\binom{k-1}{p-3}-\frac{1}{2}\mathop{\sum_{2^k\leq v&lt;2^{k+1}}}_{P(0,v)=p\text{, }2|v}v                                                                                                                                                                         \Bigg]\notag\\
 &amp; = 2^i\binom{i}{p-2}-\sum_{k=p-2}^i\Bigg[2^{k-1}\binom{k-1}{p-3}+\binom{k-2}{p-4}(2^{k-1}-1)\Bigg]\notag\\
 &amp; = 2^i\binom{i}{p-2}-\sum_{k=p-2}^i2^{k-1}\Bigg[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Bigg]+\sum_{k=p-2}^i\binom{k-2}{p-4}\notag\\
 &amp; = 2^i\binom{i}{p-2}+\binom{i-1}{p-3}-\sum_{k=p-2}^i2^{k-1}\Bigg[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Bigg],\notag
\end{align}
using similar reasoning as was used for the first sum in (\ref{2partugly}).

Combining (\ref{uglysum1}) and (\ref{uglysum2}) gives that
\begin{align*}
N(Y(i,i),p)  &amp; = 2^i\Bigg[\binom{i}{p-3}-\binom{i-1}{p-4}\Bigg]+\binom{i-1}{p-4}\\
&amp; +2^i\binom{i}{p-2}+\binom{i-1}{p-3}-\sum_{k=p-2}^i2^{k-1}\Bigg[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Bigg]\\
&amp; = 2^i\Bigg[\binom{i}{p-2}+\binom{i}{p-3}-\binom{i-1}{p-4}\Bigg]+\binom{i-1}{p-3}+\binom{i-1}{p-4}\\
&amp; \qquad\qquad-\sum_{k=p-2}^i2^{k-1}\Bigg[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Bigg]\\
&amp; = 2^i\Bigg[\binom{i}{p-2}+\binom{i-1}{p-3}\Bigg]+\binom{i}{p-3}
 -\sum_{k=p-2}^i2^{k-1}\Bigg[\binom{k-1}{p-3}+\binom{k-2}{p-4}\Bigg].
\end{align*}
The last equality follows after two applications of the binomial coefficient identity $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$.
\end{proof}

The exact formula for $N(Y(j,i),p)$ when $j&lt;i$ is significantly harder to compute. This is because, in this case, we are given elements $(u,v)$ with $u&lt;v$. If $k$ is the smallest integer such that $v\leq (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 \ref{normline}.

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

\begin{theorem}\label{HRresult}
 Let $Y(V)=\{(u,v): 0\leq u,v&lt;V\}$ and let $P(u,v)$ denote the period of $(u,v)$. Then, for every $\epsilon &gt;0$,
 \begin{align}
   \lim_{V\to\infty}\frac{1}{V^2}\#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V) \Big\}=0.\label{avgbox}
\end{align}
\end{theorem}

\begin{proof}
 Let $\epsilon&gt;0$ be given. Fix a positive integer $M&gt;0$. Then
\begin{align*}
 \Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V) \Big\} &amp; = A_1(V)\cup A_2(V)\cup A_3(V)\cup A_4(V),
\end{align*}
where
\begin{align*}
 A_1(V) &amp; = \Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }(2^M-1)u\leq v \Big\},\\
 A_2(V) &amp; = \bigcup_{i=1}^{M-1}A_{2,i}(V),\\
 A_3(V) &amp; = \bigcup_{i=1}^{M-1}\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, } (2^i-1)u=v\Big\},\\
 A_4(V) &amp; = \Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }v&lt; u \Big\},
\end{align*}
with
\begin{align}
A_{2,i}(V)=\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, } (2^i-1)u&lt; v&lt;(2^{i+1}-1)u \Big\}
\end{align}
for $1\leq i\leq M-1$.

We first estimate $\#A_1(V)$ by
\begin{align}
 \#A_1(V) &amp; =\#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }(2^M-1)u\leq v \Big\}\label{a1est}\\
 &amp; \leq \#\{(u,v)\in Y(V): (2^M-1)u\leq v\}\notag\\
 &amp; \leq \frac{V}{2^M-1}\cdot V+O(V).\notag
\end{align}

For $\#A_3(V)$, we estimate this quantity crudely by
 \begin{align}
 \#A_3(V) &amp; \leq \bigcup_{i=1}^{M-1}\#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, } (2^i-1)u=v\Big\}\label{a3est}\\
&amp; \leq \bigcup_{i=1}^{M-1}\#\{(u,v)\in Y(V): (2^i-1)u=v\}\notag\\
&amp; \leq 2MV.\notag
\end{align}

Recall that, by Lemma \ref{base3Rchar}, for $0&lt;v&lt;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
\begin{align}
 \#A_4(V) &amp; =\#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }v&lt; u \Big\}\label{a4est}\\
 &amp; \leq V\cdot\#\Big\{v\leq V: \Big|P(0,2v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\Big\}\notag\\
 &amp; \leq V\cdot\#\Big\{v'\leq 2V: \Big|P(0,v')-\frac{1}{2}\log_2(2V)\Big|&gt;\frac{\epsilon}{2}\log_2(2V)-\frac{1+\epsilon}{2}\Big\}\notag\\
&amp; = o(V^2)\notag
\end{align}
as $V\to\infty$, where the little--oh bound follows from Corollary \ref{normline}. (Note that, in the notation in Corollary \ref{normline}, $P(0,2v)=P(2v)$.)

For $\#A_2(V)$, we first estimate $\#A_{2,i}(V)$ for $1\leq i\leq M-1$. Note that, by \eqref{multiR}, if $(2^i-1)u&lt;v&lt;(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
\begin{align}
\#A_{2,i}(V) &amp; = \#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }\notag\\
 &amp; \qquad\qquad(2^i-1)u&lt; v&lt;(2^{i+1}-1)u \Big\}\notag\\
&amp; = \#\Big\{(u,v)\in Y(V): \Big|P(0,2(v-(2^i-1)u)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\text{, }\notag\\
&amp; \qquad\qquad 0&lt; 2(v-(2^i-1)u)&lt;2^{i+1}u \Big\}\notag\\
&amp; \leq V\cdot \#\Big\{v\leq V: \Big|P(0,2v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V)\Big\}\notag\\
&amp; =o(V^2)\notag
\end{align}
by \eqref{a4est}. It follows that
\begin{align}
 \#A_2(V) &amp; \leq \sum_{i=1}^{M-1}\#A_{2,i}(V)\label{a2est}\\
 &amp; = o(V^2)\notag
\end{align}
as $V\to\infty$, for any fixed $M$.

Combining all four estimates \eqref{a1est}, \eqref{a3est}, \eqref{a4est}, and \eqref{a2est}, we get that
\begin{align}
 \limsup_{V\to\infty}&amp;\frac{1}{V^2}\#\Big\{(u,v)\in Y(V): \Big|P(u,v)-\frac{1}{2}\log_2(V)\Big|&gt;\frac{\epsilon}{2}\log_2(V) \Big\}\label{lastineq}\\
  \qquad &amp; \leq \limsup_{V\to\infty}\frac{1}{V^2}\sum_{i=1}^4\#A_i(V)\notag\\
\qquad &amp; \leq \frac{1}{2^M-1}.\notag
\end{align}
Since \eqref{lastineq} holds for all fixed $M$, letting $M\to\infty$, we get \eqref{avgbox}.
\end{proof}

Theorem \ref{HRresult} roughly states that most sorted integers $\underbrace{1\cdots 1}_{u\phantom{a}1\text{'s}}\underbrace{2\cdots 2}_{v\phantom{a}2\text{'s}}$, in base $3$, have their period close to $\frac{1}{2}\log_2{v}$.

\section{Acknowledgments}

The author would like to thank his advisor, A. J. Hildebrand, for all
of his helpful suggestions, particularly regarding Theorem \ref{HRresult}.

\begin{thebibliography}{9}
\bibitem{Co}
John~H. Conway, Play it again..and again..., {\em Quantum} {\bf 63} (1990), 30--31.

\bibitem{KeCo2}
Curtis Cooper and Robert~E. Kennedy, On {C}onway's {RATS}, {\em Mathematics in College} (1998), 28--35.  Available at \newline
\url{http://www.math-cs.ucmo.edu/~curtisc/articles/rats2.pdf}.

\bibitem{Fe}
William Feller, {\em An Introduction to Probability Theory and its
Applications, {V}ol.\ {I}}, 3rd edition, John Wiley \&amp; Sons Inc.,
1968.

\bibitem{Ge}
Karen Gentges, On {C}onway's {RATS}, Master's thesis, Central Missouri
State University, 1998.

\bibitem{Gu2}
Richard~K. Guy, {\em Unsolved Problems in Number Theory}, third
edition, Springer-Verlag, 2004.

\bibitem{Ka}
D.~R. Kaprekar, Another solitaire game, {\em Scripta Math.} {\bf 15}
(1949), 244--245.

\bibitem{OEIS} The On-Line Encyclopedia of Integer Sequences,
\url{http://www.oeis.org}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A63.

\noindent \emph{Keywords: }
Conway's RATS, ultimately periodic, digital problems, iterate.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A066711}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  May 30 2012;
revised version received   November 1 2012.
Published in {\it Journal of Integer Sequences}, November 4 2012.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>