\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\def\zz{\mathbb Z}
\def\nn{\mathbb N}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\begin{document}
\begin{center}
\includegraphics[width=4in]{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
Fixed Points and Cycles of the Kaprekar \\
\vskip .1in
Transformation: 1. Odd Bases
}
\vskip 1cm
\large
Anthony Kay\\
72 Tiverton Road\\
Loughborough\\
Leicestershire LE11 2RY\\
United Kingdom\\
\href{mailto: anthony.kay@sky.com}{\tt anthony.kay@sky.com}\\
\ \\
Katrina Downes-Ward
\end{center}
\vskip .2in
\begin{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.
\end{abstract}
\section{Introduction} \label{sec1}
The \emph{Kaprekar transformation} $T_{b,n}$ takes an integer $x$ which has $n\ge2$ digits when represented in base $b\ge2$, rearranges the digits in descending and ascending orders to produce new integers $x_\downarrow$ and $x_\uparrow$, and subtracts the latter from the former. Thus, given $a_0,a_1,\ldots,a_{n-1}\in\zz$ with
$$0\le a_0\le a_1\le\cdots\le a_{n-1}**1$. A selection of these studies is listed by Yamagami \cite{yama17}, 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\le k_1$ is a fixed point, and that there do not exist cycles of length $l>1$.
Yamagami and Matsui \cite{yama18} 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 \cite{downesward} 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 \cite{myers} in the
{\it On-line Encyclopedia of Integer Sequences} (OEIS) \cite{OEIS},
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 \cite{downesward}, and we have checked that these formulae are consistent with the theory of Yamagami and Matsui \cite{yama18}.
The patterns found by Downes-Ward \cite{downesward} 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 \cite{kaydw2} 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 \mbox{$b\equiv1$ (mod $4$)} or \mbox{$b\equiv3$ (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 \ref{sec2} 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 \ref{sec3} 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 \cite{llp,pll}, but we prove them from first principles to maintain a consistent approach. The following two sections contain more specific results for bases \mbox{$b\equiv1$ (mod $4$)} and \mbox{$b\equiv3$ (mod $4$)} respectively, and we draw some general conclusions regarding odd bases in Section \ref{sec6}. 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 (\ref{defkt}), while $i$ always refers to a base-$b$ digit, $0\le i\le b-1$.
\section{Review of Yamagami and Matsui's results for base 3}\label{sec2}
A complete characterisation of the fixed points and cycles of the Kaprekar transformation in base 3 has been given by Yamagami and Matsui \cite{yama18}. 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 \emph{singular}, \emph{primitive proper}, \emph{primitive non-proper}, and \emph{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\mapsto121\mapsto022,$$
with Kaprekar indices
$$(1,0,2)\mapsto(0,2,1)\mapsto(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\ge4$, 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 \cite{kaydw2}).
The singular cycles are of length $l=m+1$ and digit-count $n=2^m+2$ for each $m\in\nn$; 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,\ldots,m$. So with $m=1$ we have a cycle of length $2$ in $4$-digit integers,
$$1221\mapsto1012\mapsto1221,$$
or in terms of Kaprekar indices,
$$(0,2,2)\mapsto(1,2,1)\mapsto(0,2,2).$$
The cycle of indices in the $m$'th case is
\begin{align*}(0,2,2^m)\mapsto(1,2,2^m-2+1)&\mapsto(1,2^2,2^m-2^2+1)\mapsto\cdots\\
&\mapsto(1,2^{m-1},2^m-2^{m-1}+1)\mapsto(1,2^m,1)\mapsto(0,2,2^m).
\end{align*}
Fundamental to Yamagami and Matsui's theory for the remaining classes of cycle in base $3$ are the following definition and theorem.
\begin{definition}\label{defsigma}
For any odd integer $r\ge3$, let $\sigma(r)$ be the least positive integer such that $2^{\sigma(r)}\equiv\pm1$ (mod $r$). See \seqnum{A003558} in
the OEIS.
\end{definition}
\begin{theorem}\label{sigdivphi}
For every odd integer $r\ge3$, $\sigma(r)$ is a divisor of $\phi(r)/2$, where $\phi$ is the Euler totient function (\seqnum{A000010} in OEIS).
\end{theorem}
Euler's totient theorem states that $r$ divides $a^{\phi(r)}-1$ when $r\in\nn$ and $a$ is coprime with $r$; setting $a=2$ confirms the existence of $\sigma(r)$ satisfying Definition \ref{defsigma}. 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:
\beq\label{qrules}
q_{i+1}=\begin{cases}
2q_i,&\text{ if }q_i<\frac{r}{2};\\
2(r-q_i),&\text{ if }q_i>\frac{r}{2}.
\end{cases}
\eeq
Clearly $q_i\equiv\pm2^iq_0$ (mod $r$), so from Definition \ref{defsigma} we have that $q_{\sigma(r)}=q_0$ but $q_i\ne q_0$ for $1\le i<\sigma(r)$; note that although Definition \ref{defsigma} appears to allow $q_{\sigma(r)}= r-q_0$, this cannot happen since $r-q_0$ is odd. Thus we have a cycle of $q$-values of length $\sigma(r)$,
$$q_0\mapsto q_1\mapsto\cdots\mapsto q_{\sigma(r)-1}\mapsto q_{\sigma(r)}=q_0.$$
These \emph{$q$-cycles} may be understood by reference to $\zz_r^\times$, the multiplicative group of integers modulo $r$, consisting of the $\phi(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 $\zz_r^\times$, i.e., the ordered set $(1,2,2^2\bmod r,\ldots,2^{j-1}\bmod r)$ for some $j$ which divides $\phi(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\equiv1$ (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 $\zz_r^\times$, and including the $q_i^*$ together with the $q_i$ accounts for $2\sigma(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 $\zz_r^\times$, and Lagrange's Theorem then yields the result in Theorem \ref{sigdivphi}. The number of $q$-cycles for any given odd $r$ is then
\beq\label{ncyc}
N_q(r)=\frac{\phi(r)}{2\sigma(r)}.
\eeq
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
\beq\label{k1rules}
k_1'=\begin{cases}
2k_1,&\mbox{ if }1+k_11$. Finally, corresponding to each primitive (proper or non-proper) cycle, there exist \emph{general cycles} of integers with digit-count $n=cr+2s$, with members having Kaprekar indices
\beq\label{genki}
(s,cq_i,cr-cq_i+s),
\eeq
for every integer $s>1$. Being derived from a $q$-cycle, all these primitive and general cycles have the same length, $\sigma(r)$.
The fixed points of the Kaprekar transformation in base $3$ correspond to any $q$-cycle of length $\sigma(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\ge5$, there is at least one primitive proper cycle. The number of such cycles is $N_q(r)$, found from (\ref{ncyc}) where $r=n-2$. We have seen that a $q$-cycle can always be generated using the rules (\ref{qrules}) from $q_0=r-1$; this $q$-cycle corresponds to a subgroup of $\zz_r^\times$. If $N_q(r)>1$, further $q$-cycles corresponding to cosets in $\zz_r^\times$ 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 (\ref{ppki}). 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\ge3$ such that $cr=n-2$ for some $c\in\nn$; having obtained the $q$-cycle(s) for each such $r$, the non-proper cycles of Kaprekar indices of form (\ref{npki}) 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\in\nn$, 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\in\nn$ such that $n-2t\ge5$ or $n-2t\ge8$ 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 primitive cycles involves the summation of $N_q(r)$ for all odd $r$ that are factors of $n'-2$. This leads to Yamagami and Matsui's \cite{yama18} formulae involving double summations for the total number of cycles (including fixed points) with any given $n$. However, simpler formulae may be found for the enumeration of integers which are members of a cycle with given $n$. For odd $n$ with $n-2$ prime, each positive even number less than $n-2$ is in a $q$-cycle for $r=n-2$, and hence appears as the $1$-component of the Kaprekar index of a member of a primitive proper cycle; so there are $(n-3)/2$ members of such cycles. If $n$ is odd but with $n-2$ composite, each even number less than $n-2$ still appears as the $1$-component of the Kaprekar index of a member of a primitive cycle which may be proper or non-proper, so the formula $(n-3)/2$ remains valid as the number of members of all primitive cycles with the given digit-count $n$. The summation to yield $N_K(n)$, the number of integers which are members of any cycle, primitive or general, with odd digit-count $n$ is then
\beq\label{nkb3}
N_K(n)=\sum_{\mathrm{odd}\,n',\,5\le n'\le n}\frac{n'-3}{2}=\sum_{m'=1}^{(n-3)/2}m'=\frac{(n-3)(n-1)}{8}.
\eeq
For even $n$, we note first that any positive integer $m$ may be written in terms of a $2$-adic valuation $v(m)$ and an odd part $\rho(m)$ as
\beq\label{oddval}
m=2^{v(m)}\rho(m).
\eeq
Since there are primitive cycles corresponding to each of the odd factors of $n-2$, the number of integers which are members of primitive cycles with digit-count $n$ is $(\rho(n-2)-1)/2$. The summation to enumerate members of all cycles, primitive or general, must be made over even $n'$ from $8$ to $n$, but does not yield a simple formula for $N_K(n)$ since there is no simple formula for $\rho(n-2)$. If $n=2^m+2$ for any $m\in\nn$, there are $m+1$ members of a singular cycle, but no members of primitive cycles since $\rho(n-2)=1$.
A table of $q$-cycles for all odd $r$ up to $67$ is given in \ref{appa}, and Figure \ref{kdw4} shows correspondingly all the cycle lengths $l$ that exist for each digit-count $n$ up to $70$: cycle lengths are in sequence \seqnum{A165003} in OEIS, with digit-counts obtained by converting least members of cycles, \seqnum{A165002} in OEIS, to base $3$. For primitive proper cycles, for which the cycle length is $\sigma(r)=\phi(r)/2N_q(r)$ with $r=n-2$, the greatest possible value of $\sigma(r)$ is when $N_q(r)=1$ and $r$ is prime so that $\phi(r)=r-1$. Any non-proper or general cycle of the same length must have a greater digit-count. Thus the leftmost dot on almost every row in Figure \ref{kdw4} represents a primitive proper cycle, and is on the line $l=(n-3)/2$ if $n-2$ is prime with $N_q(n-2)=1$. To the right of the leftmost dot on any row, there are further dots representing general cycles at every greater odd digit-count, but the first dot for an even digit-count is for a primitive non-proper cycle with $c=2$; this has $n=2n_0-2$, where $n_0$ is the digit-count for the proper cycle. The exceptions to the above are dots representing singular cycles at $n=4,6,10,18,34$ and $66$ for cycle lengths up to $7$, and a dot for the special case of $n=3$; no dot is shown for $n=2$ because we have excluded fixed points with Kaprekar indices $(n,0,0)$ as being trivial, but all $2$-digit integers are taken to such a fixed point under the Kaprekar transformation. Apart from these exceptions, there are no dots to the left of the line $l=(n-3)/2$.
\begin{figure}[!h]
\begin{center}
\includegraphics[height=7cm]{base3l.jpg}
\caption{Cycle lengths that exist for digit-counts $n$ up to $70$.}
\label{kdw4}
\end{center}
\end{figure}
We conclude this section with an example of finding all the primitive Kaprekar cycles with a given digit-count: $n=254$. Since $n$ is even, we are only looking for non-proper cycles. The odd factors of $n-2=252$ are $r=3,7,9,21$ and $63$, with respective multipliers $c=84,36,28,12$ and $4$ such that $cr=n-2$. So, from the table in \ref{appa} and formula (\ref{npki}), we have:
\begin{itemize}
\item Corresponding to $r=3$, a fixed point with Kaprekar index $(1,168,85)$;
\item Corresponding to $r=7$, a cycle of length $3$, members having Kaprekar indices
$$(1,72,181)\mapsto(1,144,109)\mapsto(1,216,37)\mapsto(1,72,181);$$
\item Corresponding to $r=9$, a cycle of length $3$, members having Kaprekar indices
$$(1,56,197)\mapsto(1,112,141)\mapsto(1,224,29)\mapsto(1,56,197);$$
\item Corresponding to $r=21$, a cycle of length $6$, members having Kaprekar indices
\begin{align*}(1,24,229)\mapsto(1,48,205)\mapsto(1,96,157)\mapsto(1,192,61)&\mapsto(1,120,133)\mapsto\\
&(1,240,13)\mapsto(1,24,229);
\end{align*}
\item Corresponding to $r=63$, three cycles of length $6$, members having Kaprekar indices
\begin{align*}(1,8,245)\mapsto(1,16,237)\mapsto(1,32,221)\mapsto(1,64,189)&\mapsto(1,128,125)\mapsto\\
&(1,248,5)\mapsto(1,8,245),
\end{align*}
\begin{align*}(1,40,213)\mapsto(1,80,173)\mapsto(1,160,93)\mapsto(1,184,69)&\mapsto(1,136,117)\mapsto\\
&(1,232,21)\mapsto(1,40,213),
\end{align*}
\begin{align*}(1,88,165)\mapsto(1,176,77)\mapsto(1,152,101)\mapsto(1,200,53)&\mapsto(1,104,149)\mapsto\\
&(1,208,45)\mapsto(1,88,165).
\end{align*}
\end{itemize}
Finding the actual $254$-digit integer in a cycle from its Kaprekar index simply requires a base-$3$ subtraction of integers having the previous Kaprekar index in the cycle. For example, the integer with Kaprekar index $(1,72,181)$ in the cycle corresponding to $r=7$ is found from the Kaprekar index $(1,216,37)$ by
\begin{align*}
&\underbrace{2\cdots\cdots2}_{37}\;\underbrace{1\cdots\cdots\cdots1}_{216}0\\
-\;&0\underbrace{1\cdots\cdots\cdots\cdots1}_{216}\;\,\underbrace{2\cdots2}_{37}\\
=\;&2 \underbrace{1\cdots1}_{35}\,0\;\underbrace{2\cdots2}_{180}\;\underbrace{1\cdots1}_{36}1,
\end{align*}
where the result has Kaprekar index $(1,72,181)$ as required.
Observe that every multiple of $8$ that is less than $252$ appears once as the $1$-component of a Kaprekar index in the above primitive cycles. With $n=254$ we have $\rho(n-2)=63$ and $v(n-2)=2$ according to the definition (\ref{oddval}), so there is a member of a primitive cycle corresponding to each even positive integer less than $63$; and the $1$-components of the Kaprekar indices of these cycle members are even multiples of $2^{v(n-2)}=4$.
\section{Theory on primitive and general cycles in any base}\label{sec3}
It is useful to reframe some relevant parts of the theory for base $3$ before considering general bases. We introduce the notation
\beq\label{k2m}
k_2^-:=k_2-1.
\eeq
Then for odd digit-counts $n$ in base $3$, every Kaprekar index of the form $(1,k_1,1+k_2^-)$ with even positive $k_1$, so that $k_2^-$ is odd and $k_1+k_2^-=n-2$, is in a primitive cycle. Let $c:=\gcd(n-2,k_1)=\gcd(k_1,k_2^-)$ and $r:=(n-2)/c$; then the length $l$ of the primitive cycle is equal to $\sigma(r)$, defined in Definition \ref{defsigma}. If $c=1$, the primitive cycle is proper. Letting $q=k_1/c$, the Kaprekar index $(1,k_1,1+k_2^-)$ can be rewritten as $(1,cq,cr-cq+1)$, and is in a cycle in which the succession of indices is given by a $q$-cycle derived from a subgroup or coset of the multiplicative group modulo $r$. With odd $n$, $c$ is also odd; but non-proper primitive cycles with even $n$ may also be obtained from proper cycles by applying even multipliers $c$ in cycles of Kaprekar indices of form $(1,cq,cr-cq+1)$. Furthermore, indices of form $(s,cq,cr-cq+s)$, for any $s>1$, are in associated general cycles. This theory leads to the pattern of cycle lengths vs.\ digit-counts seen in Figure \ref{kdw4}.
We now introduce some terminology for cycles and individual Kaprekar indices, some of which is a generalization to any base $b\ge3$ of the terminology used by Yamagami and Matsui \cite{yama18} for base $3$. To make the notation tidier, we introduce the symbol
$$B:=b-1$$
for the greatest digit that appears in base $b$.
\begin{definition}\label{defregspec}
\leavevmode
\begin{itemize}
\item
A Kaprekar index $\mathbf{k}=(k_0,k_1,\ldots,k_B)$ is \emph{regular} if $k_i\ge1$ for $i=0,1,2,\ldots,B$ and $k_B>k_0$.
\item A cycle is \emph{regular} if every member has a regular Kaprekar index.
\item A cycle is \emph{special} if any member has a Kaprekar index that is not regular.
\end{itemize}
\end{definition}
Thus in base $3$, Yamagami and Matsui's singular cycles are classified here as \emph{special}, as are the unanimous fixed point with $n=2$ and the unanimous cycle of length $2$ with $n=3$. However, our concern in this section is to develop theory applying to regular cycles. These cycles and their members may be classified using an extension of Yamagami and Matsui's terminology.
\begin{definition}\label{defprcy}
\leavevmode
\begin{itemize}
\item A regular Kaprekar index is \emph{primitive} if $k_0=1$.
\item A cycle is \emph{primitive} if each member has a Kaprekar index that is primitive.
\item A regular Kaprekar index is \emph{general} if $k_0>1$.
\item A cycle is \emph{general} if each member has a general Kaprekar index.
\end{itemize}
\end{definition}
Clearly, the existence of regular cycles depends on whether regular Kaprekar indices $\mathbf{k}$ can be guaranteed to have regular successors $\mathbf{k}'$. It is therefore useful to have a general formula for the digits of a successor. Such a formula was given by Prichett, Ludington and Lapenta \cite{pll,llp}; in a variant of their difference notation, we define
\beq\label{diffdef}
d_j:=a_{n-1-j}-a_j\quad\mbox{for}\;\;j=0,1,\ldots,\nu,
\eeq
where $\nu=\lfloor n/2\rfloor-1$, and we observe that $d_0\ge d_1\ge\cdots\ge d_\nu$. We set $\mu=\max \{j:d_j>0\}$, so either $d_{\mu+1}=0$ or $\mu=\nu$.
Performing the subtraction (\ref{defkt}), the digits of $T_{b,n}(x)$ are then found to be \cite{pll}
\beq\label{ktres}
d_0,d_1,\ldots, d_{\mu-1},d_\mu-1,B,\ldots, B,B-d_\mu,B-d_{\mu-1},\ldots ,B-d_1,b-d_0,
\eeq
where commas have been inserted between digits for clarity since some digits are in the form of expressions involving a subtraction. The digit string (\ref{ktres}) may be subdivided into three sections. On the right, there are $\mu+1$ instances of digits $a_{n-1-j}$ of $x_\uparrow$ being subtracted from smaller digits $a_j$ of $x_\downarrow$: the rightmost digit is $b-(a_0-a_{n-1})$, and then $1$ is carried to the left so that each subsequent digit subtraction (going leftward) yields $b-(a_j-a_{n-j-1})-1=B-d_j$. In the centre, there are $n-2\mu-2$ instances where $a_{n-1-j}=a_j$, and the subtraction with $1$ carried yields $B$; but if $\mu=\nu$, then this central string of digits $B$ is absent if $n$ is even, or is reduced to a single such digit if $n$ is odd. On the left, there are $\mu+1$ subtractions of $a_{n-1-j}$ from larger digits $a_j$, yielding $d_j$ except that $1$ is still carried into the rightmost subtraction of this section.
Suppose that $x$ has a regular Kaprekar index $\mathbf{k}$, so the base-$b$ representations of $x_\downarrow$ and $x_\uparrow$ consist of blocks of $k_i$ digits $i$, with $k_i\ge1$ for every value of $i$ between $0$ and $B$, arranged in descending and ascending order, respectively, . Given any $i_\uparrow$ and $i_\downarrow$ with $0\le i_\uparrowk_0$ in a regular Kaprekar index, so $a_{n-1-j}=B$ whenever $a_j=0$).
We would now have proved the theorem if it were not for having ``pattern-breaking'' digits, $d_\mu-1$ instead of $d_\mu$ in the left section of (\ref{ktres}), and $b-d_0$ instead of $B-d_0$ as the rightmost digit. Indeed, we would have each digit from $1$ to $B-1$ appearing in both the left and right sections of (\ref{ktres}), so $k_i'\ge2$ for $i=1,2,\ldots,B-1$; at least one digit $B$ in the central section and in the left section, with each of the latter corresponding to a digit $0$ in the right section, so that $k_B>k_0\ge1$; and $k_0'=k_0$, so that primitive and general Kaprekar indices have respective primitive and general successors. So it remains to resolve the issue of the two pattern-breaking digits; but the inequality condition ensures that $d_\mu=1$, so having $d_\mu-1$ in (\ref{ktres}) provides a digit $0$ instead of $1$; and $d_0=B$, so having $b-d_0$ in (\ref{ktres}) provides a digit $1$ instead of $0$. Hence the pattern-breaking does not affect the Kaprekar index of the successor, under the given conditions.
\end{proof}
Note that the inequality condition is sufficient but not necessary in this theorem: the successor of a regular Kaprekar index may be regular and may have $k_i'\ge2$ for \mbox{$i=1,2,\ldots,B$} even when $\mathbf{k}$ does not satisfy the inequality condition. On the other hand, finding a regular Kaprekar index with a regular successor does not imply that they are members of a regular cycle: our next theorem enables us to write down infinitely many more regular cycles once a primitive cycle has been found, but it is of little help in finding a primitive cycle in the first place. It will be useful for this theorem to generalize the notation (\ref{k2m}) as
$$k_B^-:=k_B-1,$$
so that a primitive Kaprekar index takes the form,
$$(1,k_1,\ldots,k_{B-1},k_B^-+1).$$
\begin{theorem}\label{primgen}
If the primitive Kaprekar index $\mathbf{k}=(1,k_1,\ldots,k_{B-1},k_B^-+1)$ has a primitive successor $\mathbf{k}'=(1,k_1',\ldots,k_{B-1}',k_B'^- +1)$, then:
(i) the primitive Kaprekar index $(1,ck_1,\ldots,ck_{B-1},ck_B^-+1)$ has the primitive successor $(1,ck_1',\ldots,ck_{B-1}',ck_B'^-+1)$, for any integer $c>1$;
(ii) the general Kaprekar index $(s,ck_1,\ldots,ck_{B-1},ck_B^-+s)$ has the general successor $(s,ck_1',\ldots,ck_{B-1},ck_B'^-+s)$, for any integers $s>1$ and $c\ge1$.
\end{theorem}
\begin{proof}
(i) Multiplying components $k_1,\ldots,k_{B-1}$ and $k_B^-$ of the primitive Kaprekar index $\mathbf{k}$ by $c$ means that each digit in the original integers $x_\downarrow$ and $x_\uparrow$ is replaced with $c$ copies of the same digit, except for the first and last digits. So in (\ref{ktres}) the first digit $d_0$ and last digit $b-d_0$ are unchanged, but every other subtraction $a_{n-1-j}-a_j$ is replaced with $c$ copies of the same subtraction. This yields $c$ copies of the same digit in (\ref{ktres}), except that there is still only one instance of the pattern-breaking digit $d_\mu-1$ arising from the last subtraction from the right to have $1$ carried. As in the proof of Theorem \ref{primsucc}, this compensates for the pattern-breaking rightmost digit $b-d_0$.
(ii) Increasing each of $k_0$ and $k_B$ by $s-1$ means that we leave the leftmost and rightmost digits of $x_\downarrow$ and $x_\uparrow$ unchanged, but insert $s-1$ digits $B$ adjacent to the leftmost $B$ of $x_\downarrow$ and the rightmost $B$ of $x_\uparrow$, together with $s-1$ digits $0$ adjacent to the rightmost $0$ of $x_\downarrow$ and the leftmost $0$ of $x_\uparrow$. The subtractions then yield $s-1$ further digits $B$ (from $B-0$) on the left of (\ref{ktres}), and $s-1$ further digits $0$ (from $0-B$ with $1$ carried) on the right of (\ref{ktres}).
\end{proof}
\begin{corollary}\label{cyccmsa}
If the primitive Kaprekar index $(1,k_1,\ldots,k_{B-1},k_B^-+1)$ is a member of a primitive cycle, then:
(i) the Kaprekar index $(1,ck_1,\ldots,ck_{B-1},ck_B^-+1)$, for any integer $c>1$, is also a member of a primitive cycle of the same length;
(ii) the Kaprekar index $(s,ck_1,\ldots,ck_{B-1},ck_B^-+s)$, for any integers $s>1$ and $c\ge1$, is a member of a general cycle of the same length.
\end{corollary}
This follows from Theorem \ref{primgen} because the $c$-multiplication and the $s$-addition can be applied to each succession in the original primitive cycle.
Part (i) of Theorem \ref{primgen} motivates the following definitions, which are again an extension to general bases $b\ge3$ of a definition given for base $3$ by Yamagami and Matsui.
\begin{definition}
\leavevmode
\begin{itemize}
\item A Kaprekar index is \emph{primitive proper} if it is primitive with
$$\gcd(k_1,\ldots,k_{B-1},k_B^-)=1.$$
\item A Kaprekar index is \emph{primitive non-proper} if it is primitive with $\gcd(k_1,\ldots,k_{B-1},k_B^-)=c$ for some integer $c>1$.
\end{itemize}
\end{definition}
It follows from part (i) of Theorem \ref{primgen} that if the successor of a primitive proper index is primitive, then it is proper, and if the successor of a primitive non-proper index is primitive, then it is non-proper with the same multiplier $c$. Hence we can apply similar definitions to cycles.
\begin{definition}
\leavevmode
\begin{itemize}
\item A cycle is \emph{primitive proper} if its members are primitive proper.
\item A cycle is \emph{primitive non-proper} if its members are primitive non-proper.
\end{itemize}
\end{definition}
Once we have found a primitive proper cycle, Corollary \ref{cyccmsa} shows that there are then infinitely many primitive non-proper cycles corresponding to it, and then infinitely many general cycles corresponding to each primitive (proper or non-proper) cycle. In base $3$, each primitive proper cycle corresponds in a simple way to a $q$-cycle derived from a subgroup (generated by $2$) or coset in $\zz_r^\times$. The next theorem suggests a link between $q$-cycles and primitive proper cycles in any odd base, whereas no similar theorem applies in even bases.
\begin{theorem}\label{kb2}
In base $b=B+1$, where $B$ is even, the formula for $k_{B/2}'$ in terms of the components of $\mathbf{k}$ includes a factor of $2$ if $\mathbf{k}$ is regular and satisfies the inequality condition.
\end{theorem}
\begin{proof}
If $d_j=B/2$, then $B-d_j=B/2$ also. Hence each instance of the digit $B/2$ in the right section of (\ref{ktres}) corresponds to an instance of $B/2$ in the left section. So the total number of instances, $k_{B/2}'$, must include a factor of $2$.
\end{proof}
In base $3$, for which $B/2=1$, Yamagami and Matsui's \cite{yama18} Theorem 1.3 shows the factor of $2$ appearing in the formula for $k_1'$ in every case, not merely those in which $\mathbf{k}$ is regular and satisfies the inequality condition. In particular, when those conditions are satisfied, we have the succession formulae (\ref{k1rules}) for $k_1'$, which relate in a simple way to $q$-cycles since the latter are generated by the factor $2$ in the multiplicative group modulo $n-2$. However, in higher odd bases, we shall find that the succession formulae retain the connection between $q$-cycles and cycles in the Kaprekar transformation in bases $b\equiv3$ (mod $4$) but not in bases $b\equiv1$ (mod $4$).
A further theorem that applies to all odd bases and may be of some use, at least to reduce the burden of calculation, is that the Kaprekar index of a successor $\mathbf{k}'$ displays a symmetry (except between $k_0$ and $k_B$) when $\mathbf{k}$ and $\mathbf{k}'$ are both regular:
\begin{theorem}\label{kisym}
In base $b=B+1$ where $B$ is even, if $\mathbf{k}$ is regular and satisfies the inequality condition, then its successor has $k_{B-i}'=k_i'$ for $1\le i\le B-1$.
\end{theorem}
\begin{proof}
Since each digit $d_j$ in the left section of (\ref{ktres}) corresponds to a digit $B-d_j$ in the right section (with the pattern-breaking digits compensating each other as explained above), the count of any digit $i$ equals that of the digit $B-i$. The exception is for digits $0$ and $B$, since the central section of digits $B$ has no corresponding digits $0$.
\end{proof}
We conclude this section by observing that according to Theorem \ref{primsucc} the successor to a regular Kaprekar index satisfying the inequality condition must have a digit-count $n\ge2b-1$, since $k_0'\ge1$ and $k_i'\ge2$ for $i=1,\ldots,B$. In fact, a Kaprekar index with $k_i=2$ for $i=1,\ldots,B$ corresponds to a fixed point in any odd base. This is seen most easily from the example of base $5$, where we have the subtraction,
\begin{align}
&443322110\nonumber\\
-\,&011223344\nonumber\\
=\,&432043211,\label{b5fp}
\end{align}
from which it is clear that in any greater odd base $b$ the fixed-point integer is
\beq\label{ppfp}
B\cdots20B\cdots211,
\eeq
where each ellipsis indicates that there is a complete sequence of decreasing digits from $B(=b-1)$ to $2$. We shall see that the fixed point of this form does have the least digit-count of any regular fixed point in bases $b\equiv1$ (mod $4$), but that regular fixed points with smaller digit-counts (and not satisfying the inequality condition) exist in bases $b\equiv3$ (mod $4$).
\section{Base 5 and higher bases $b\equiv1$ (mod $4$)}\label{sec4}
Much of this section is focussed on base $5$; we have also examined cycles in base $9$, enabling us to draw some general conclusions about bases $b\equiv1$ (mod $4$), although the only rigorous theory beyond that in Section \ref{sec3} is for base $5$. Least members of base $5$ cycles are given in base ten in \seqnum{A165041} in OEIS, with corresponding cycle lengths in \seqnum{A165042}; we convert the least members to base $5$ and then compute further cycle members to obtain the cycles displayed below and in the appendices. For base $9$ the corresponding OEIS sequences are \seqnum{A165119} (least members of cycles) and \seqnum{A165120} (cycle lengths).
We first display in Figure \ref{kdw12} the base-$5$ equivalent to Figure \ref{kdw4} for base $3$, showing the cycle lengths that exist for each digit-count, although only up to $n=50$ in the present case. The pattern is similar in the two figures, with points representing primitive proper cycles on or to the right of the line $l=(n-3)/2$, general cycles represented at intervals of $2$ in $n$ to the right of the primitive proper cycles, and points with even $n$ representing non-proper cycles with multiplier $c=2$ appearing further to the right. However, there are many more exceptions to this pattern, representing special cycles, in base $5$ than in base $3$; in particular, there are many points to the left of the line $l=(n-3)/2$ for small values of $n$ in Figure \ref{kdw12}.
\begin{figure}[!h]
\begin{center}
\includegraphics[height=6cm]{base5l.jpg}
\caption{Cycle lengths that exist for digit-counts $n$ up to $50$ in base $5$.}
\label{kdw12}
\end{center}
\end{figure}
A list of special cycles for digit-counts up to $n=50$ in base $5$ is given in \ref{appb}; there certainly exist special cycles for greater digit-counts. Regular cycles do not exist for $n<9$, so all cycles (including fixed points) with digit-counts $n\le8$ are special; they are unanimous for $3\le n\le8$, as are the special cycles with $n=10$ and $n=12$, but with $n=2$ both the fixed point $13$ and the repdigit fixed point $00$ can be reached from different non-trivial starting integers. Among the special cycles there is a class of singular cycles, with digit-counts $n=2^m+2$ and lengths $l=m+1$ for integers $m$ as in base $3$, but only for $m\ge3$ in base $5$. The structure of these singular cycles is more complicated in base $5$ than in base $3$: the sequence of Kaprekar indices in these cycles is
\begin{align*}(1,0,1,2,2^m-2)&\mapsto(1,2,2,2,2^m-6+1)\mapsto(1,2^2,2^2,2^2,2^m-12+1)\mapsto\cdots\\
&\mapsto(1,2^{m-2},2^{m-2},2^{m-2},2^m-3\times2^{m-2}+1)\mapsto(1,2^{m-1},0,2^{m-1},1)\\
&\mapsto(0,2,2^m-1,0,1)\mapsto(1,0,1,2,2^m-2).
\end{align*}
The cycles with $n=10, n=18$ and $n=34$ in \ref{appb} are examples of this type. While the remaining special cycles in \ref{appb} display many common features, we have not been able to find any further clear patterns analogous to that of the singular cycles.
In base $9$ we have also found numerous special cycles. There does not appear to be any equivalent of the singular cycles in bases $3$ and $5$, but there are interesting classes of fixed points and cycles of length $l=2$. Specifically, for any integers $t\ge1$ and $u\ge0$, there are fixed points with Kaprekar indices
$$(0,0,t,t+u,0,t+u,t,0,t+u)\quad\mbox{and}\quad(0,t,t+u,2t+u,0,2t+u,t+u,t,t+u),$$
with respective digit-counts $n=5t+3u$ and $n=9t+5u$. Apart from the repdigit fixed point $00$ at $n=2$, we have not found any other special fixed points. For any integer $t\ge0$ there is a cycle of length $2$,
\begin{align*}
(0,1,t,t+2,0,t+1,t+2,0,t+1)\mapsto&(0,0,t+2,t+1,0,t+2,t,1,t+1)\mapsto\\
&\qquad(0,1,t,t+2,0,t+1,t+2,0,t+1),
\end{align*}
with digit-count $n=5t+7$. There are also many other special cycles of lengths $l\ge2$ in base $9$, which do not appear to fit into this or any other class. We have not formulated any further theory of special cycles or fixed points in bases $b\equiv1$ (mod $4$).
To develop theory for regular cycles, we require succession formulae, of which a partial list for base $5$ is given in \ref{appc}.
Formula (\ref{ktres}) gives the individual digits of a successor, but the practical means of finding a succession formula is to set out the calculation as in the following example, which is for case (v) of \ref{appc}:
\begin{align}
&\underbrace{4\cdots4}_{k_4}\;\;\,\underbrace{3\cdots\cdots\cdots\cdots\cdots3}_{k_3}\;\underbrace{2\cdots\cdots\cdots\cdots\cdots\cdots\cdots2}_{k_2}\;\underbrace{1\cdots\cdots\cdots\cdots\cdots1}_{k_1}\,0\nonumber\\
-\;&0\underbrace{1\cdots\cdots\cdots1}_{k_1}\;\;\underbrace{2\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots2}_{k_2}\;\underbrace{3\cdots\cdots\cdots\cdots\cdots3}_{k_3}\;\;\underbrace{4\cdots\cdots4}_{k_4}\nonumber\\
=\;&4\underbrace{3\cdots3}_{k_4-1}\underbrace{2\cdots2}_{1+k_1-k_4}\;\underbrace{1\cdots\cdots1}_{k_4+k_3-k_1-2}0\underbrace{4\cdots\cdots\cdots\cdots4}_{1+k_1+k_2-k_3-k_4}\,\underbrace{3\cdots\cdots3}_{k_3+k_4-k_1-1}\;\underbrace{2\cdots\cdots2}_{1+k_1-k_4}\;\underbrace{1\cdots\cdots1}_{k_4}.\label{subtex5}
\end{align}
The list in \ref{appc} covers all cases where $\mathbf{k}$ is primitive (and also some other cases, in particular where $k_4=1=k_0$); from Theorem \ref{primgen}, succession formulae when $\mathbf{k}$ is general follow from primitive cases, so all regular Kaprekar indices are covered. Referring to these formulae, we can prove the next two theorems.
\begin{theorem}
Every member of a regular cycle in base $5$ has a Kaprekar index satisfying the inequality condition.
\end{theorem}
\begin{proof}
In each case in \ref{appc} where the inequality condition is not satisfied, i.e.\ where the conditions on $k_1,k_2,k_3$ and $k_4$ include an equality, the successor $\mathbf{k}'$ is not regular: either $k_0'=0$ or $k_2'=0$ or $k_4'=1=k_0'$.
\end{proof}
Note that this theorem is not trivial: in base $7$ we shall see that the inequality condition is not necessary for membership of a regular cycle. The inequality condition is not sufficient for a regular Kaprekar index to be a cycle member in any base $b\ge5$; but stricter conditions that do appear to be sufficient in base $5$ only are displayed below.
An immediate consequence of this theorem, according to Theorem \ref{primsucc}, is that every member of a regular cycle in base $5$ has $k_i\ge2$ for $i=1,2,3,4$. The case where $k_i=2$ for $1\le i\le4$ is the fixed point (\ref{b5fp}), and we have a further theorem regarding this fixed point.
\begin{theorem}\label{uniqppfp}
The \emph{only} primitive proper fixed point in base $5$ is that displayed in (\ref{b5fp}) above, with Kaprekar index $\mathbf{k}=(1,2,2,2,2)$.
\end{theorem}
\begin{proof} Setting $k_i'=k_i$ for $i=0,1,2,3,4$ in each of the succession formulae in \ref{appc}, we obtain an inconsistency in every case except (v). In that case, setting $k_i'=k_i$ yields that $k_1=k_2=k_3=2(k_4-1)$, which allows just the Kaprekar index $(1,2,2,2,2)$ or any primitive non-proper index derived from it according to Theorem \ref{primgen}(i).
\end{proof}
Based on a survey of regular cycles and fixed points with digit-counts up to $n=35$ in base $9$, we conjecture that the last two theorems apply in all bases $b\equiv1$ (mod $4$): that all members of regular cycles in these bases satisfy the inequality condition, and so have $k_i\ge2$ for $1\le i\le b-1$, implying that regular cycles cannot exist with digit-count $n\le2b-1$; and that the only primitive proper fixed point in any such base is (\ref{ppfp}). The theorems for base $5$ were proved by exhaustive consideration of succession formulae for that particular base, so a more elegant method would need to be devised in order to prove the conjectures for higher bases. And in any case there is evidence from base $9$ of complications that may cast doubt on the truth of such conjectures: there is a set of ``pseudo-regular'' cycles of length $l=2$ in which one member has $k_4=0$ (so is not regular), the other member does not satisfy the inequality condition, but the structure of primitive and general cycles specified in Corollary \ref{cyccmsa} is retained: see the note at the end of \ref{appe}.
Given that the inequality condition is definitely satisfied by cycle members in base $5$, the components of their Kaprekar indices are constrained by Theorems \ref{kb2} and \ref{kisym} to satisfy the requirements,
\beq\label{b5cond}
k_2\mbox{ is even};\quad k_3=k_1\ge2.
\eeq
If we restrict attention to primitive Kaprekar indices, for which $k_0=1$, then once the digit-count $n$ is fixed, only two free parameters remain in an index. These can be taken as $k_1$ and $k_2$, and we then have $k_4=n-2k_1-k_2-1$. If we restrict attention further to odd values of $n$, the Kaprekar indices under consideration are either proper, or non-proper with an odd multiplier $c$. Then, given the conditions (\ref{b5cond}), a further condition that suffices to ensure that a Kaprekar index satisfies the inequality condition is as follows:
\beq\label{b5ineq}
\mbox{\emph{either} }k_1 \mbox{ is even, \emph{or }}k_1\mbox{ is odd and }k_1>k_4.
\eeq
To see why conditions (\ref{b5ineq}) apply, note first that $k_4$ is even when $n$ is odd. Then if $k_1$ is even, the left side of (\ref{ineqc}) is odd (since $k_0=1$) while the right side is even, guaranteeing the inequality; while if $k_1$ is odd the further condition $k_1>k_4$ precludes equalities such as $k_0+k_1=k_4$. In higher bases, the free parameters are $k_i$ for $i=1,2,\ldots,B/2$, and it remains true that the inequality condition is satisfied if these are all even; but we have not determined more general principles governing when the inequality condition is satisfied.
In base $3$, all primitive cycles could be derived from $q$-cycles, as tabulated in \ref{appa} for $r\le67$, because of the simple succession formulae (\ref{k1rules}) for a single free parameter. In base $5$, having established that (\ref{b5cond}) applies throughout any regular cycle, we only require succession formulae for the two free parameters $k_1'$ and $k_2'$, which are as follows (where we have taken all cases from \ref{appc} in which $\mathbf{k}$ is regular and satisfies the inequality condition, with $k_3=k_1$):
\begin{align}\label{b5k1rules}
k_1'=&\begin{cases}2k_4-2,&\text{if $k_4<1+k_1$ and $k_4<1+k_2$};\\
k_2+k_4-1,&\text{if $1+k_29$, due to Theorem \ref{uniqppfp}).
Since the primitive proper cycles cannot be simply derived from $q$-cycles in bases $b\equiv1$ (mod $4$), we have listed them for $n\le33$ in \ref{appd} for base $5$ and \ref{appe} for base $9$. Comparing with values of $\sigma(r)$ in \ref{appa}, we may observe that in the majority of cases, the lengths $l$ of the primitive cycles in base $5$ are equal to $\sigma(n-2)$, even where that number is not prime; but there are also several cases where $l$ is a smaller factor of $\sigma(n-2)$, for example with $n=23$ for which $\sigma(n-2)=6$ and both the possibilities $l=2$ and $l=3$ appear among the primitive cycles listed in \ref{appd}. On the other hand, the lengths of primitive cycles in base $9$ bear no relation to $\sigma(n-2)$ in most cases.
In base $3$, enumerating cycles for any given $n$ leads to complicated expressions involving double summations, whereas enumerating the integers which are members of cycles leads to closed-form expressions in many cases. The same applies in base $5$, although the calculations to enumerate members of cycles are more complicated. We conjecture, on the basis of evidence from all base-$5$ primitive cycles with $n\le41$, that every primitive Kaprekar index $\mathbf{k}$ with odd $n$ in base $5$ which satisfies conditions (\ref{b5cond}) and (\ref{b5ineq}) (which are sufficient but not necessary to satisfy the inequality condition) represents a member of a primitive cycle. [In base $9$ we have not been able to find conditions similar to (\ref{b5cond}) and (\ref{b5ineq}) that guarantee membership of a cycle, which is why we have not attempted any enumeration of cycle members for bases higher than $5$.] Then $k_0=1$, $k_3=k_1$ and $k_4\ge2$, so to enumerate primitive cycle members we need to count the pairs of positive integers $(k_1,k_2)$ satisfying $2k_1+k_2+3\le n$, with $k_2$ even and $k_1$ satisfying (\ref{b5ineq}). The result is given in the following theorem.
\begin{theorem}\label{enumpc5}
In base $5$, the number of members of primitive cycles with odd digit-count $n\ge9$ is:
$((n-5)^2-4)/12$ members if $n\equiv1$ (mod $6$) or $n\equiv3$ (mod $6$);
$(n-5)^2/12$ members if $n\equiv5$ (mod $6$).
\end{theorem}
\begin{proof}
Given $n$ and $k_2$, there are $(n-5-k_2)/2$ integers $k_1$ satisfying $2k_1\le n-3-k_2$ with $k_1\ge2$. Given $n$, the allowed values of $k_2$ are the positive even integers up to $n-7$ (since $k_0=1$ and $k_i\ge2$ for $i=1,3,4$). So the number of pairs $(k_1,k_2)$ satisfying the requirement $2k_1+k_2\le n-3$ and condition (\ref{b5cond}) is (setting $k_2=2i$ and $m=(n-5)/2$)
\beq\label{sumpoddn}
\sum_{i=1}^{(n-7)/2}\frac{n-5-2i}{2}=\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2}=\frac{(n-5)(n-7)}{8}.
\eeq
To satisfy condition (\ref{b5ineq}) we need to subtract the number of \emph{non-compliant pairs}, those in which $k_1$ is odd and does not satisfy $k_1>k_4$, so does satisfy $3k_1\le n-1-k_2$; but not counting pairs with $k_1=1$, which have already been excluded. Now, for any integer $K\ge3$ there are $\lfloor(K-3)/6\rfloor$ odd integers $k_1$ such that $k_1\ge3$ and $3k_1\le K$ (where $\lfloor\cdot\rfloor$ is the floor function); so, given $n$ and $k_2$, there are $\lfloor(n-4-k_2)/6\rfloor$ non-compliant pairs. Thus the number of non-compliant pairs for a given $n$ is
$$\sum_{\mathrm{even}\,k_2,\,2\le k_2\le n-7}\left\lfloor\frac{n-4-k_2}{6}\right\rfloor.$$
\noindent Case (i): if $n\equiv1$ (mod $6$), let $n=6t+1$. As $k_2$ decreases through even integers from $n-7$ to $2$, values of $(n-4-k_2)$ increase through odd integers from $3$ to $6(t-1)+1$, yielding a set of values of $\lfloor(n-4-k_2)/6\rfloor$ including two zeroes, three of each integer from $1$ to $t-2$, and one instance of the integer $t-1$. The sum of all these is
$$3\sum_{i=1}^{t-2}i+(t-1)=3\frac{(t-2)(t-1)}{2}+(t-1)=\frac{(n-9)(n-7)}{24}$$
non-compliant pairs, where we have substituted $t=(n-1)/6$ at the last step.
\medskip
\noindent Case (ii): if $n\equiv3$ (mod $6$), let $n=6t+3$. As $k_2$ decreases through even integers from $n-7$ to $2$, values of $(n-4-k_2)$ increase through odd integers from $3$ to $6(t-1)+3$, yielding a set of values of $\lfloor(n-4-k_2)/6\rfloor$ including two zeroes, three of each integer from $1$ to $t-2$, and two instances of the integer $t-1$. The sum of all these is
$$3\sum_{i=1}^{t-2}i+2(t-1)=3\frac{(t-2)(t-1)}{2}+2(t-1)=\frac{(n-9)(n-7)}{24}$$
non-compliant pairs.
\medskip
\noindent Case (iii): if $n\equiv5$ (mod $6$), let $n=6t+5$. As $k_2$ decreases through even integers from $n-7$ to $2$, values of $(n-4-k_2)$ increase through odd integers from $3$ to $6(t-1)+5$, yielding a set of values of $\lfloor(n-4-k_2)/6\rfloor$ including two zeroes and three of each integer from $1$ to $t-1$. The sum of all these is
$$3\sum_{i=1}^{t-1}i=3\frac{t(t-1)}{2}=\frac{(n-11)(n-5)}{24}$$
non-compliant pairs.
The numbers of non-compliant pairs in each case above are to be subtracted from the result (\ref{sumpoddn}) which does not account for condition (\ref{b5ineq}), and the results for the three cases are as stated in the theorem.
\end{proof}
Counting the members of primitive \emph{proper} cycles for each $n$ in \ref{appc}, the enumerations agree with the formulae in Theorem \ref{enumpc5} for members of \emph{all} primitive cycles except in two cases, $n=23$ and $n=29$. Theorem \ref{enumpc5} includes non-proper cycles with odd multipliers $c$; applying the multiplier $c=3$ to the proper fixed point with $n=9$ and the proper cycle of length $l=3$ with $n=11$, we obtain a non-proper fixed point with $n=23$ and a non-proper cycle with $n=29$, respectively. Obviously, non-proper cycles feature more frequently at higher digit-counts $n$. To count members of primitive cycles with even $n$, an argument similar to that used in base $3$ indicates that we should replace $(n-5)$ with $\rho(n-2)-3$ in the formulae in Theorem \ref{enumpc5}, where $\rho$ denotes the odd part.
To count members of all regular cycles (i.e.\ both primitive and general cycles) for some $n$, we require a summation of numbers of members of primitive cycles with any $n'\le n$ of the same parity, similar to that in (\ref{nkb3}). As in base $3$, results in closed form are only available for odd $n$. From Theorem \ref{enumpc5}, adding the numbers of members of primitive cycles with digit-counts $n$, $n-2$ and $n-4$, for any odd $n\ge13$, yields a total of $(n-7)^2/4$ members with these three digit-counts. This result can then be used with standard summation formulae to yield the formulae for $N_K(n)$, the number of integers with digit-count $n$ which are members of a regular cycle, for any odd $n\ge9$:
\begin{align*}
N_K(n)&=\frac{1}{72}(n-1)(n-4)(n-7)\quad&\mbox{if }n\equiv1\pmod6;\\
N_K(n)&=\frac{1}{72}(n-3)(n^2-9n+12)\quad&\mbox{if }n\equiv3\pmod6;\\
N_K(n)&=\frac{1}{72}(n-5)(n^2-7n+4)\quad&\mbox{if }n\equiv5\pmod6.
\end{align*}
Since the distribution of special cycles is somewhat irregular, including several for odd values of $n$ (see \ref{appb}), we cannot provide completely reliable formulae for the total number of cycle members for any $n$; although since special cycles with odd $n$ are comparatively scarce, the above formulae for $N_K(n)$ are accurate for this purpose in most cases where $n$ is odd.
\section{Base 7 and higher bases $b\equiv3$ (mod $4$)}\label{sec5}
As in previous sections, we start by noting special cycles, but only in base $7$, since we have not made a detailed study of the cycles that exist for any base $b>10$; we have used data for base-$7$ cycles from sequences \seqnum{A165080} (least members of cycles) and \seqnum{A165081} (cycle lengths) in the OEIS. As in base $3$, the fixed point $00$ is unanimous for $n=2$. For each digit-count $3\le n\le9$ there is a unanimous special cycle: for $n=3$ this has length $l=2$,
$$264\mapsto336\mapsto264;$$
for $n=4$ it has length $l=3$,
$$3054\mapsto5052\mapsto5232\mapsto3054;$$
and for $5\le n\le9$ the cycles are longer. For $n\ge10$ there exist three classes of special cycle of length $l=2$:
\noindent(a) For each $t\ge1$, there is a special cycle with digit-count $n=2t+8$, with sequence of Kaprekar indices
\beq\label{sp7a}
(1,1,t+1,2,t,3,0)\mapsto(0,1,t+1,2,t+1,1,2)\mapsto(1,1,t+1,2,t,3,0);
\eeq
\noindent(b) For each $t\ge0$, there is a special cycle with digit-count $n=5t+10$, with sequence of Kaprekar indices
\begin{align}\label{sp7b}
(1,t,t+3,0,t+2,t+2,t+2)\mapsto&(0,t+1,2,2t+3,1,t,t+3)\mapsto\nonumber\\
&\qquad(1,t,t+3,0,t+2,t+2,t+2);
\end{align}
\noindent(c) For each $t\ge2$, there is a special cycle with digit-count $n=5t+10$, with sequence of Kaprekar indices
\begin{align}\label{sp7c}
(1,t+1,t+1,2,t,t+3,t+2)\mapsto&(0,t+3,1,2t+2,2,t+1,t+1)\mapsto\nonumber\\
&\qquad(1,t+1,t+1,2,t,t+3,t+2).
\end{align}
A survey up to $n=53$ has revealed numerous special cycles not falling into these three classes, and these are listed in \ref{appf}; except for those with digit-counts $n=3,4,10,19$ and $51$, they all have lengths $l\ge5$.
Turning now to regular cycles, we find that, in contrast to bases $b\equiv1$ (mod $4$), the regular cycles in bases $b\equiv3$ (mod $4$) are determined by the $q$-cycles arising from subgroups and cosets of $\zz_r^\times$; but the Kaprekar indices of cycle members do not always satisfy the inequality condition, and a wider variety of further cycles can be derived from a primitive cycle than those specified by the $c$-multiples and $s$-additions of Corollary \ref{cyccmsa}. In more detail:
\begin{itemize}
\item Corresponding to each $q$-cycle, there exists a primitive proper base-$7$ cycle of digit-count $n=3r+2$ with members having Kaprekar indices
\beq\label{fundb7}
(1,q_i,r-q_i,q_i,r-q_i,q_i,r-q_i+1)
\eeq
(compare (\ref{ppki}) in base $3$).
\item There is a further degree of generalization beyond that in formulae (\ref{npki}) and (\ref{genki}) in base $3$: corresponding to each primitive proper cycle of type (\ref{fundb7}) with $r=(n-2)/3$, there exist cycles of digit-count $n=3cr+2t+2s$ with members having Kaprekar indices
\beq\label{gen7}
(s,cq_i,c(r-q_i)+t,cq_i,c(r-q_i)+t,cq_i,c(r-q_i)+s)
\eeq
for each integer $c\ge1$, $s\ge1$ and $t\ge0$.
\item This pattern applies for all bases $b=4m+3,m\ge1$; there is a cycle of digit-count $n=(2m+1)r+2$ with members having Kaprekar indices
\beq\label{fundb4m3}
(1,q_i,r-q_i,\ldots,q_i,r-q_i,q_i,r-q_i+1),
\eeq
from which are derived cycles of digit-count $n=(2m+1)cr+2t+2s$ with members having Kaprekar indices
\beq\label{genreg}
(s,cq_i,c(r-q_i)+t,\ldots,cq_i,c(r-q_i)+t,cq_i,c(r-q_i)+s)
\eeq
for each integer $c\ge1$, $s\ge1$ and $t\ge0$, where $q_i$ is in a $q$-cycle as listed in \ref{appa}.
\item There can exist further cycles derived from a cycle of type (\ref{fundb4m3}), with the same patterns of $c$-multiples and $s$-additions but different patterns of $t$-additions to components of its members. Several such generalizations in base $7$ are noted below.
\end{itemize}
Note that if $t$ is coprime with $c$, a Kaprekar index of form (\ref{genreg}) may satisfy the definition of a primitive proper index, even with $c\ge1$. Thus it is useful to introduce the following terminology in bases $b=4m+3,m\ge1$.
\pagebreak
\begin{definition}
\leavevmode
\begin{itemize}
\item
A Kaprekar index with odd digit-count $n$ in a base $b=4m+3$ is \emph{fundamental} if it has the form
$$(1,q,r-q,\ldots,q,r-q,q,r-q+1)$$
with $r=(n-2)/(2m+1)$, for some even $qk_2$. By subtraction calculations similar to (\ref{subtex5}), we find that the successor Kaprekar index $\mathbf{k}'$ satisfies conditions of the form (\ref{b7cond}), and that if $k_1k_2$, then $k_1'=2k_2$ and $k_2'=k_1-k_2$. With the identification $k_1=q_i$ and $k_2=r-q_i$, these succession formulae yield $k_1'=q_{i+1}$ according to the $q$-cycle rules (\ref{qrules}), with $k_2'=r-q_{i+1}$. This explains the existence of fundamental cycles with values of $k_1$ following $q$-cycles. Cycles of form (\ref{genreg}) with any positive $c$ and $s$ but with $t=0$ are then explained by Theorem \ref{primgen} and Corollary \ref{cyccmsa}, and it remains to explain why cycles of this form with positive $t$ exist. So we suppose that $k_0=s$, $k_j=k_1$ for all odd $j$, $k_j=k_2+t$ for even $j$ with $2\le j****k_2$ confirms that in all cases, addition of $t$ to the even components of a Kaprekar index satisfying conditions (\ref{b7cond}) carries through to its successor, and so can apply throughout a regular cycle.
Unlike in bases $b\equiv1$ (mod $4$), it is not necessarily true that $k_j\ge2$ for all $j\ge1$ in Kaprekar indices of members of regular cycles in bases $b\equiv3$ (mod $4$). Indeed, since a $q$-cycle derived from a subgroup, as opposed to a coset, of $\zz_r^\times$ includes the number $r-1$, any fundamental cycle corresponding to such a $q$-cycle must include a member in which $k_2=k_4=\cdots=k_{B-2}=1$. In particular, the fundamental fixed point has Kaprekar index $(1,2,1,\ldots,2,1,2,2)$ and digit-count $n=6m+5$ in base $b=4m+3$, and all fixed points and cycles with lesser digit-count must be special.
In base $7$ we have found some classes of general cycle with $t$-additions not of the form (\ref{genreg}). Derived from the fundamental cycle corresponding to the $q$-cycle with $r=5$, there is a class of general cycles of length $l=2$ with digit-count $n=15c+5t+2s$:
\begin{align*}
&(s,2c+t,3c+t,2c,3c+t,2c+t,3c+t+s)\mapsto(s,4c+t,c,4c+2t,c,4c+t,c+t+s)\mapsto\\
&\qquad(s,2c+t,3c+t,2c,3c+t,2c+t,3c+t+s),
\end{align*}
in which the pattern of $t$-additions to components is the same as in the special cycles (\ref{sp7b}) and (\ref{sp7c}); similarly the $t$-additions in the special cycles of form (\ref{sp7a}) correspond to the standard pattern of $t$-additions in regular cycles (\ref{gen7}). Derived from the fundamental cycle corresponding to the $q$-cycle with $r=7$, there is a class of general cycles of length $l=3$ with digit-count $n=21c+7t+2s$:
\begin{align*}
&(s,2c+t,5c+2t,2c,5c+2t,2c+t,5c+t+s)\mapsto\\
&\qquad(s,4c+t,3c+t,4c+2t,3c+t,4c+t,3c+t+s)\mapsto\\
&\qquad(s,6c+2t,c,6c+2t,c,6c+2t,c+t+s)\mapsto\\
&\qquad(s,2c+t,5c+2t,2c,5c+2t,2c+t,5c+t+s),
\end{align*}
for which we have not found a corresponding class of special cycles. Rather more anomalously, we have found a class of cycles of length $l=3$ with digit-count $n=19c+8t+2s$:
\begin{align}\label{reg7anom}
&(s,2c,4c+3t,2c,4c+3t,2c,5c+2t+s)\mapsto\nonumber\\
&\qquad(s,3c+t,4c+t,2c+2t,4c+t,3c+t,3c+2t+s)\mapsto\nonumber\\
&\qquad(s,5c+3t,c,6c+2t,c,5c+3t,c+s)\mapsto\nonumber\\
&\qquad(s,2c,4c+3t,2c,4c+3t,2c,5c+2t+s),
\end{align}
which exists only for $0\le t\le c$. The fundamental cycle of this class has $n=21$, so should be associated with the $q$-cycle for $r=19$, for which $\sigma(r)=9$; so the length of these cycles is a divisor of $\sigma(r)$, in a way reminiscent of cycles in base $5$, with the progression of Kaprekar index components not tied to a $q$-cycle in any obvious way. Curiously, the cycle of this class with $c=1,t=1,s=1$ is the fundamental cycle corresponding to the $q$-cycle with $r=9$, with further cycles of the type (\ref{reg7anom}) with $t=c$ being identified as higher $c$-multiples of the $r=9$ fundamental cycle; but no similar identification of those cycles with $t1+k_1+k_2$, then
\qquad\qquad\qquad$\mathbf{k'}=(1,k_4+k_2-1,2k_1-2k_4+2,k_4+k_2-1,k_4+k_3-k_2-k_1)$
\noindent(viii) If $k_4=1+k_1$ and $k_3**