\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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}
\usepackage{mathtools}
\usepackage{enumitem}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\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 Young Graphs: 1089 et al.
}
\vskip 1cm
\large
L. H. Kendrick \\
Massachusetts Institute of Technology \\
77 Massachusetts Avenue \\
Cambridge, MA 02139\\
USA \\
\href{mailto:lkendrick@mit.edu}{\tt lhk@mit.edu}
\end{center}
\vskip .2 in
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\begin{abstract}
This paper deals with those positive integers $N$ such that, for given
integers $g$ and $k$ with $2\le k0$. For convenience we may define $r_{-1}=r_{n-1}=0$ so that for all $i$, $0\le i \le n-1$, we have
\begin{equation}\label{eq:rmdig}
ka_i+r_{i-1}=a_{n-1-i}+r_ig.
\end{equation}
\begin{remark}\label{rem:notation}
We use the notation of Young and Sloane. Holt uses a similar setup, focusing on the numbers $r_i$, but his notation is closer to that of Sutcliffe, Pudwell, and Kaczynski: $g$, $k$, $n$, $a_i$, and $r_i$ are denoted in his papers by $b$, $n$, $k+1$, $d_{k-i}$, and $c_{i+1}$, respectively.
\end{remark}
\subsection{Generating the graph $H(g, k)$}\label{subsec:hgraph}
$H(g, k)$ is a kind of directed graph. Young's \cite{youngRM} main results demonstrate a correspondence between a subset of the paths of $H(g, k)$ and $(g, k)$ reverse multiples, which we state in Section~\ref{subsec:youngsthm}. The nodes in $H(g, k)$ will be labeled with pairs $[r_{n-2-i}, r_i]$ of the $r_i$s and the edges with pairs $(a_{n-1-i}, a_i)$ of the $a_i$s. To construct this graph, we take the above equations (\ref{eq:rmdig}) in pairs
\begin{equation}\label{eq:eqnpair}
\begin{array}{rcl}
ka_i+r_{i-1} & = &a_{n-1-i}+r_ig \\
ka_{n-1-i}+r_{n-2-i} & = & a_i+r_{n-1-i}g
\end{array}
\end{equation}
and solve recursively for the pairs $[r_{n-2-i}, r_i]$: given a pair $[r_{n-1-i}, r_{i-1}]$, we can check through all values of $a_i$ and $a_{n-1-i}$ (which must be between $0$ and $g-1$ inclusive) for the pairs $(a_{n-1-i}, a_i)$ that give integer values for $r_{n-2-i}$ and $r_i$ between $0$ and $k-1$ inclusive. If a pair $(a_{n-1-i}, a_i)$ gives a satisfactory pair $[r_{n-2-i}, r_i]$ then a directed edge, labeled $(a_{n-1-i}, a_i)$, is drawn from the node labeled $[r_{n-1-i}, r_{i-1}]$ to the node labeled $[r_{n-2-i}, r_i]$ (with one exception discussed below). As there are a finite number of potential nodes, this process must terminate.
This process begins at $[r_{-1}, r_{n-1}]$, called the \textit{starting node} and indicated as $[[0, 0]]$ with double brackets to distinguish it from the node labeled $[0, 0]$. No edges are to end at the starting node by definition, and no edges leading from the starting node can have labels with $0$s, because this would imply $a_{n-1}=0$ or $a_0=0$, which the definition of $a_{n-1}$ and $a_0$ forbids (although not for Grimm and Ballew). The node $[0, 0]$ cannot function as the starting node for this reason, as edges from $[0, 0]$ are allowed $0$s, and also for the sake of convenience in Young's correspondence and
Sloane's enumerations (Section 3 in his paper; they are not discussed here); this is why we must have a starting node.
$H(g, k)$ is the graph thus generated.
\subsection{Pivot nodes and Young graphs}\label{subsec:youngsthm}
The following definition, due to Sloane, is made to condense the statements of Young's \cite{youngRM} main theorems, Theorems 1 and 2 in her first paper.
\begin{definition}[Pivot Nodes]\label{def:pivnodes}
An \textit{even pivot node} is a node of the form $[a, a]$; an \textit{odd pivot node} is a node of the form $[r, s]$ that is a direct predecessor of the node $[s, r]$ (including even pivot nodes with self-loops). The starting node is not considered a pivot node.
\end{definition}
Note that the edge label between $[r, s]$ and $[s, r]$ must have the form $(a, a)$ because equation (\ref{eq:eqnpair}) implies that the edge label from $[r, s]$ to $[s, r]$ is $((rg-s)/(k-1), (rg-s)/(k-1))$.
Theorems 1 and 2 in Young's \cite{youngRM} first paper link these nodes of $H(g, k)$ to $(g, k)$ reverse multiples, and allow us to read off all $(g, k)$ reverse multiples from $H(g, k)$. The proofs of those theorems are omitted; the results are stated as they are rephrased by Sloane for directed graphs.
\begin{theorem}[Young's Theorem]\label{thm:youngsthm}
There is a one-to-one correspondence between the $(g, k)$ reverse multiples with an even number of digits and the paths in $H(g, k)$ from the starting node to even pivot nodes and a one-to-one correspondence between the $(g, k)$ reverse multiples with an odd number of digits and the paths in $H(g, k)$ from the starting node to odd pivot nodes. The path leading to an even pivot node that consists of the edges labeled $(a_{n-1}, a_0), (a_{n-2}, a_1),\ldots,(a_{n/2}, a_{n/2-1})$, in that order, corresponds to the reverse multiple $(a_{n-1}, a_{n-2}, \ldots, a_1, a_0)_g$. The path leading to the odd pivot node $[r, s]$, which directly precedes $[s, r]$ by the edge labeled $(a_{(n-1)/2}, a_{(n-1)/2})$, that consists of the edges labeled
$$(a_{n-1}, a_0), (a_{n-2}, a_1),\ldots,(a_{(n+1)/2}, a_{(n-3)/2})$$
corresponds to the reverse multiple $(a_{n-1}, a_{n-2}, \ldots, a_1, a_0)_g$.
\end{theorem}
Nodes for which no pivot nodes are successors are therefore unimportant, if we are interested in Young's correspondence between paths and reverse multiples. Thus the Young graph is defined as follows.
\begin{definition}[Young graph]\label{def:ygraph}
The \textit{Young graph} for $g$ and $k$, denoted $Y(g, k)$, is the labeled directed graph obtained by removing from $H(g, k)$ all nodes that are not pivot nodes and that do not precede any pivot nodes, along with all edges starting or ending at these nodes.
\end{definition}
\begin{remark}\label{rem:truncate}
Sutcliffe, Kaczynski, Pudwell, and, most generally, Holt discuss \textit{middle digit truncation} of reverse multiples; that is, the question of when removing the middle digit of a $(g, k)$ reverse multiple with an odd number of digits yields another $(g, k)$ reverse multiple. These discussions arose from Sutcliffe's Theorem 3, which found a correspondence between two-digit reverse multiples and three-digit reverse multiples involving such truncation: namely, that if $(a, b)_g$ is a $(g, k)$ reverse multiple, with $0\le a, b\le g-1$, then $(a, a+b, b)_g$ is also a $(g, k)$ reverse multiple. Theorem 10 of Holt's \cite{holtL} first paper, which characterizes the occurrences of truncations that yield new reverse multiples, states that a $(g, k)$ reverse multiple $(a_{n-1}, a_{n-2}, \ldots, a_1, a_0)_g$, for odd $n$, may be truncated by middle digit removal to obtain a new $(g, k)$ reverse multiple if and only if $r_{(n-3)/2}=r_{(n-1)/2}$; while Holt's proof is algebraic, this result may also be seen as a direct consequence of Young's theorem and the fact that the edge labels $(a_{n-1-i}, a_i)$ in a Young graph are distinct (proven by Sloane), because such reverse multiples correspond to paths to nodes that are both odd and even pivot nodes.
\end{remark}
\subsection{Examples}\label{subsec:ex}
We include several examples to clarify the above material. Consider $Y(10, 9)$, shown in Figure \ref{fig:y109}; to construct this graph, we must first construct $H(10, 9)$ and then remove all nodes that do not precede a pivot node, as per Definition \ref{def:ygraph}. To construct the graph $H(10, 9)$, one begins at the starting node, taking equation (\ref{eq:eqnpair}) with $g=10$, $k=9$, and $i=0$ to obtain
\begin{equation*}
\begin{array}{rcl}
9a_0+0 & = & a_{n-1}+10r_0 \\
9a_{n-1}+r_{n-2} & = & a_0+10\cdot 0.
\end{array}
\end{equation*}
Note that here the value $0$ has been substituted for the terms $r_{i-1}$ and $r_{n-1-i}$ that appear in (\ref{eq:eqnpair}), since $r_{-1}=r_{n-1}=0$ by definition (Section~\ref{subsec:eqtns}). Checking through all pairs $(a_{n-1}, a_0)$ with $00$.
Repeating this argument proves that all successors of a node $[r, r]$ have the form $[r^\prime, r^\prime]$; since all nodes in a Young graph are successors of $[[0, 0]]$, all nodes in $Y(g, k)$ must have the form $[r, r]$, so that $Y(g, k)$ is complete by Lemma \ref{lem:evencomplete}.
\end{proof}
\begin{remark}\label{rem:shiftsym1}
This is related to Theorem 9 in Holt's first paper \cite{holtL} and Corollary 6 in his second \cite{holtS}. Note as well that here, as with 1089 graphs, Holt's partition based on the structure of the carries of reverse multiples aligns nicely with partition by isomorphism, as noted in Remark \ref{rem:isocarry}.
\end{remark}
While not the full result characterizing the occurrences of complete graphs, the following result is still interesting, and gives several further results, and so we digress from the proof of Theorem \ref{thm:completegraph} to include it here.
\begin{proposition}\label{prop:2evenpreccomplete}
If there are two even pivot nodes in $Y(g, k)$ that directly precede the same node, $Y(g, k)$ is a complete graph.
\end{proposition}
\begin{proof}
Suppose there is a node $[x, x]$ which directly precedes the nodes $[r, s]$ by the edge labeled $(a, b)$ and a node $[y, y]$ that directly precedes $[r, s]$ by the edge labeled $(c, d)$, with $x \neq y$. Then, by equation (\ref{eq:eqnpair}), we must have $kb+x=a+sg$, $ka+r=b+gx$, $kd+y=c+sg$, and $kc+r=d+gy$. These yield $y-x=(c-a)-k(d-b)$ and $g(y-x)=k(c-a)-(d-b),$ which together give $(g-k)(c-a)=(kg-1)(d-b)$. This rearranges to
$$d-b=\frac{g-k}{k^2-1}((c-a)-k(d-b))=\frac{g-k}{k^2-1}(y-x),$$
so that $c-a=\left(\frac{kg-1}{k^2-1}\right)(y-x)$. Therefore $\left(\frac{g-k}{k^2-1}\right)|y-x|=|d-b|$ is a positive integer and $|y-x|=\left(\frac{k^2-1}{kg-1}\right)|c-a|\le\left(\frac{k^2-1}{kg-1}\right)gd_1+1$, and $\gcd(m+1, d_2)=1$. Then let $k=(d_2^2-md_1^2)/(m-1)$, and let the pair $(M, N)$ be an integer solution to $d_1(m+1)M-d_2N=1$. Then $(d_2t+kM, d_1(m+1)t+kN, md_2t+mkM+d_1)_g$ is a $(g, m)$ reverse multiple for $g=(m^2-1)t-mNd_1+d_2M(m+1)$, for any $t$ such that $g>m$. Note that $d_1$ is $r_1$ and $d_2$ is $r_0$. From examination of some of these multiples, we make Conjecture \ref{conj:GBiso}.
\begin{conjecture}\label{conj:GBiso}
If $g_1$ and $g_2$ are different bases obtained by performing the Grimm-Ballew procedure for the same $d_1$, $d_2$, and $m$, then $Y(g_1, m)\cong Y(g_2, m)$.
\end{conjecture}
\begin{conjecture}\label{conj:classgrowth}
Let $\text{Classes}(x)$ denote the number of equivalence classes that occur in all $Y(g, k)$ for $g\le x$. $\text{Classes}(x)$ grows roughly proportionately to $x^2$.
\end{conjecture}
Regarding this conjecture, we find that the $r$-value for the set $\{(x, \text{Classes}(x)^{1/2})\mid x\le 336\}$ is around $0.9996$. However, $336$ seems to be a rather low upper bound for this type of problem: for example, the functions $\text{Freq}_{K_m}(x)$, for $x\le 400$ are well-approximated by functions of the form $c\cdot x\ln x$, but for $x\le 10^5$ it becomes apparent that such an approximation fails. Conjecture \ref{conj:classgrowth} is thus made rather hesitantly.
\section{Acknowledgments}\label{sec:acks}
Many thanks to Professor Ramin Takloo-Bighash of the University of Illinois at Chicago for suggesting this problem for research, to Mr. Paul Karafiol of the Ogden International School of Chicago and Prof.~Benjamin Klaff of Tulane University for their mentoring and encouragement, to Dr.~Tanya Khovanova of the Massachusetts Institute of Technology for her help with editing, and to the referee for many helpful comments.
\begin{thebibliography}{10}
\bibitem{gardner}
Martin Gardner.
\newblock {\em Mathematical Magic Show}.
\newblock Mathematical Association of America, 1990.
\bibitem{GB}
C.~A. Grimm and D.~W. Ballew.
\newblock Reversible multiples.
\newblock {\em J. Recreational Math.}, {\bf 8} (1975--6), 89--91.
\bibitem{hoey}
Dan Hoey.
\newblock Untitled online article.
\newblock \url{https://oeis.org/A008919/a008919.txt}, accessed April 10 2015.
\bibitem{holtL}
Benjamin~V. Holt.
\newblock Some general results and open questions on palintiple numbers.
\newblock {\em INTEGERS: Elect. J. Combin. Numb. Theory}, {\bf 14}
(2014), Paper A42. Available at
\url{http://www.integers-ejcnt.org/vol14.html}.
\bibitem{holtAsym}
Benjamin~V. Holt.
\newblock Derived palintiple families and their palinomials.
\newblock Preprint, 2015, available at \url{http://arxiv.org/abs/1412.0231}.
\bibitem{holtS}
Benjamin~V. Holt.
\newblock Some thoughts on determining symmetric palintiples.
\newblock Preprint, 2015, available at \url{http://arxiv.org/abs/1410.2356}.
\bibitem{oeis}
OEIS~Foundation Inc.
\newblock The On-Line Encyclopedia of Integer Sequences.
\newblock Available at \url{http://oeis.org}.
\bibitem{unabomber}
T.~J. Kaczynski.
\newblock Note on a problem of {A}lan {S}utcliffe.
\newblock {\em Math. Mag.}, {\bf 41} (1968), 84--86.
\bibitem{klosinski}
Leonard~F. Klosinski and Dennis~C. Smolarski.
\newblock On the reversing of digits.
\newblock {\em Math. Mag.}, {\bf 42} (1969), 208--210.
\bibitem{pudwell}
Lara Pudwell.
\newblock Digit reversal without apology.
\newblock {\em Math. Mag.}, {\bf 80} (2007), 129--132.
\bibitem{sloane}
N.~J.~A. Sloane.
\newblock 2178 and all that.
\newblock {\em Fibonacci Quart.}, {\bf 52} (2014), 99--120.
\bibitem{sutcliffe}
Alan Sutcliffe.
\newblock Integers that are multiplied when their digits are reversed.
\newblock {\em Math. Mag.}, {\bf 39} (1966),
282--287.
\bibitem{WW}
Roger Webster and Gareth Williams.
\newblock On the trail of reverse divisors: 1089 and all that follow.
\newblock {\em Math. Spectrum}, {\bf 45} (3) (2013), 96.
\bibitem{PengNumb}
David Wells.
\newblock {\em The Penguin Dictionary of Curious and Interesting Numbers}.
\newblock Penguin, revised edition, 1997.
\bibitem{youngRM}
Anne~Ludington Young.
\newblock $k$-reverse multiples.
\newblock {\em Fibonacci Quart.}, {\bf 30} (1992), 166--174.
\bibitem{youngTrees}
Anne~Ludington Young.
\newblock Trees for $k$-reverse multiples.
\newblock {\em Fibonacci Quart.}, {\bf 30} (1992), 126--132.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A63; Secondary 05C20.
\noindent \emph{Keywords: } Young graph, reverse multiple,
palintiple, radix representation.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A001232},
\seqnum{A008918},
\seqnum{A008919},
\seqnum{A031877},
\seqnum{A169824}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 10 2015;
revised version received August 16 2015; August 20 2015.
Published in {\it Journal of Integer Sequences},
August 21 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}