Young Graphs: 1089 et al.

L. H. Kendrick Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139 USA

                      lhk@mit.edu

Abstract

This paper deals with those positive integers N such that, for given integers g and k with 2 ≤ k < g, the base-g digits of kN appear in reverse order from those of N. Such N are called (g, k) reverse multiples. Young, in 1992, developed a kind of tree reflecting properties of these numbers; Sloane, in 2013, modified these trees into directed graphs and introduced certain combinatorial methods to determine from these graphs the number of reverse multiples for given values of g and k with a given number of digits. We prove Sloane’s isomorphism conjectures for 1089 graphs and complete graphs, namely that the Young graph for g and k is a 1089 graph if and only if k +1 | g and is a complete Young graph on m nodes if and only if ⌊gcd(g − k, k^{2} − 1)/(k + 1)⌋ = m − 1. We also extend his study of cyclic Young graphs and prove a minor result on isomorphism and the nodes adjacent to the node [0, 0].

1 Introduction

This paper studies a certain type of positive integer, defined as follows.

Definition 1 (Reverse Multiple). Given g, k ∈ ℤ, with 2 ≤ k < g, a (g, k) reverse multiple is a positive integer N such that the base-g representations of N and kN are reverses of each other. That is, if (c_{n−1}, c_{n−2}, …, c_{1}, c_{0})_{g} denotes ∑_{i=0}^{n−1} c_{i}g^{i}, then N = (a_{n−1}, a_{n−2}, …, a_{1}, a_{0})_{g} and kN = (a_{0}, a_{1}, …, a_{n−2}, a_{n−1})_{g}, for some integers a_{i} with 0 ≤ a_{i} ≤ g−1 and a_{n−1} nonzero.

Ironically, the most prominent mention of these numbers may well have curtailed their prominence: G. H. Hardy, in A Mathematician’s Apology, refers to the fact that 1089 and 2178 are the only four-digit (10, k) reverse multiples as one “very suitable for puzzle columns and likely to amuse amateurs,” but “not serious” and “not capable of any significant generalization.” While we abstain from judgment on the first two counts, it is clear, after the intervening decades, that Hardy misjudged regarding the third.^{1} A number of works generalize the problem, a list of most of which may be found in Sloane’s 2013 paper [11] on the topic; of the four works [3, 6, 4, 5] on the topic cited here not found by Sloane, three were published after his paper, by the same author. Hardy’s comment, however, while perhaps self-fulfilling by way of his stature, may possess some kernel of truth: Sloane’s list of references, while appreciable, is rather short for a problem given such exposure as a mention in Hardy’s book, albeit a disparaging one, and the problem does, in fact, appear with some frequency in texts on recreational mathematics or mathematical curiosities (e.g., by Gardner [1] or Wells [14]).

We take an approach to the problem, using certain labeled graphs, begun by Young [15, 16] in 1992 and developed further by Sloane in 2013. Most serious work takes an approach more algebraic than Young’s, and studies the problem for a small, preset number of digits for a general base n. This is largely due to the influence of Sutcliffe [12], who, in 1966, initiating the largest interlinked body of work on the problem, determined all bases n in which there exists a two-digit reverse multiple; Sutcliffe cites no works other than a general number theory reference. In sequence, Kaczynski [8],^{2} in 1968, proved Sutcliffe’s conjecture on three-digit reverse multiples, and Pudwell [10], in 2007, extended Kaczynski’s methods for reverse multiples of two or three digits to those of four and five, the behavior of the latter proving to be rather more complicated than that of the former. Pudwell also proved that (b, b − 1, g − b − 1, g − b)_{g} is a (g, k) reverse multiple when g = b(k + 1), as did Klosinski and Smolarski [9] in 1969, independently of the above material (they cite none of it). Outside of passing mentions in books on recreational mathematics, Sloane found two other treatments of the problem: a 2013 paper by Webster and Williams [13], which deals with the case in which g = 10, and a 1975 paper by Grimm and Ballew [2]. The latter, after listing all (10, k) reverse multiples less than 10^{9}, presents an algorithm that generates three-digit reverse multiples through a process rather distinct from those of other works, in that it begins with the numbers r_{i} (defined in Section 2.1) and shows how to construct the base g, multiplier k, and digits a_{i} of a reverse multiple, while other sources fix g, and sometimes k, and then construct the digits a_{i} and numbers r_{i}; Grimm and Ballew also differ from other sources by allowing reverse multiples to have leading zeroes. Kaczynski notes that Prasert Na Nagara of Kasetsart University in Thailand arrived at results similar to his independently, but no reference is given, and efforts to contact both regarding this work have failed.

More recently, Holt [6, 4, 5] has taken a variant approach to the problem, considering reverse multiples, which he calls “palintiples,”^{3} with any number of digits. His papers begin the project of classifying palintiples based on “the structure of their carries,” a partitioning rationale similar to that of the equivalence classes developed in this paper, on which similarities we comment, and of characterizing specific classes of palintiples. He also extends Pudwell’s study of four- and five-digit reverse multiples and middle-digit truncation, and begins the study of “palinomials” and palintiple derivation: respectively, polynomials constructed from the digits of a given palintiple and the process of obtaining a new palintiple from the carries of a given palintiple. The latter, as he demonstrates [5], may be fruitfully used to study seemingly rather intractable equivalence classes of reverse multiples. Holt’s approach is more in the algebraic style of Sutcliffe, Kaczynski, and Pudwell, although he notes the utility of Young’s approach, as well as a number of intriguing phenomena among its elements (see Section 6).

1The only refuge for his position being in the nebulous qualifier “significant.”

2“Better known for other work.” [10]

3He credits the term to Hoey [3]. Strictly speaking, “palintiple” refers to a number that is a multiple of its reverse, rather than a divisor, as with reverse multiples.

Young, with two papers in 1992, began studying the problem via a kind of infinite tree, in which edges are labeled with pairs of digits (a_{n−1−i}, a_{i}) and nodes with pairs of numbers [r_{n−2−i}, r_{i}], defined in Section 2, and found a correspondence relating reverse multiples and certain kinds of nodes in the tree. Sloane reformulated these trees into labeled directed graphs, which he calls Young graphs, allowing for the application of the transfer matrix method to find the number of (g, k) reverse multiples with a given number of digits (Section 3 of his paper). He also discusses data gained from constructing all Young graphs for g ≤ 40. While Young’s approach can be used to exhaustively list all (g, k) reverse multiples for given g and k, Sloane’s approach more obviously raises the questions regarding isomorphism that are dealt with in this paper, and so will be used here.

Young graphs, not reverse multiples, are the predominant focus of this paper, and it is partly our object to demonstrate the utility of the graphical approach to this problem. We discuss several types of graphs mentioned by Sloane, proving two of his conjectures on isomorphism, and also include minor results determining two points’ images under isomorphism and describing the nodes around [0, 0]. Section 2 restates the pertinent work of Sloane and Young, Section 3 proves (Theorem 14) Sloane’s conjecture on 1089 graphs, Section 4 proves (Theorem 31) Sloane’s conjecture on complete graphs, and Section 5 proves minor results (Theorems 36 and 37) on cyclic graphs on three and five nodes and contains a conjecture related to cyclic graphs. Section 4 also contains a result on isomorphism (Theorem 29), a result on the predecessors of the node [0, 0] (Corollary 28), and a result on two-digit reverse multiples (Proposition 33), which is related to the work of Sutcliffe. In Section 6, we discuss possible further research on the topic, including several isomorphism conjectures (Section 6.1) made from examination of Young graphs for low values of g, although of a less complete nature than those of Sloane.

2 Background on Young graphs

Young [15] developed a method for exhaustively listing all (g, k) reverse multiples for given values of g and k by generating a labeled infinite tree; Sloane modified this approach so that the tree became a kind of directed graph. We present Young’s method under Sloane’s modification.

2.1 Equations

Let N = (a_{n−1}, a_{n−2}, …, a_{1}, a_{0})_{g} be a (g, k) reverse multiple, with 0 ≤ a_{i} ≤ g − 1 and a_{n−1} ≠ 0. Then kN = Reverse_{g}(N), so there are integers r_{0}, r_{1}, …, r_{n−2} with 0 ≤ r_{i} < g such that

ka_{0} = a_{n−1} + r_{0}g
ka_{1} + r_{0} = a_{n−2} + r_{1}g
ka_{2} + r_{1} = a_{n−3} + r_{2}g
⋮
ka_{n−2} + r_{n−3} = a_{1} + r_{n−2}g
ka_{n−1} + r_{n−2} = a_{0}.

These equations are those that arise from the base-g columns multiplication representing the equation kN = Reverse_{g}(N), written

(r_{n−2}) (r_{n−3}) (r_{n−4}) …  (r_{1})  (r_{0})
a_{n−1} a_{n−2} a_{n−3} … a_{2}  a_{1}  a_{0}
×  k
a_{0}  a_{1}  a_{2} … a_{n−3} a_{n−2} a_{n−1}.

While the r_{i} are defined between 0 and g − 1 inclusive, Young [15] proved that r_{i} ≤ k − 1 for all i and that r_{0} > 0. For convenience we may define r_{−1} = r_{n−1} = 0 so that for all i, 0 ≤ i ≤ n − 1, we have

ka_{i} + r_{i−1} = a_{n−1−i} + r_{i}g.  (1)

Remark 2. 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.

2.2 Generating the graph H(g, k)

H(g, k) is a kind of directed graph. Young’s [15] 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 2.3. 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 (1) in pairs

\begin{aligned}ka_{i} + r_{i−1} & = & a_{n−1−i} + r_{i}g \\ ka_{n−1−i} + r_{n−2−i} & = & a_{i} + r_{n−1−i}g \end{aligned}  (2)

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 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 0s, 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 0s, 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.

2.3 Pivot nodes and Young graphs

The following definition, due to Sloane, is made to condense the statements of Young’s [15] main theorems, Theorems 1 and 2 in her first paper.

Definition 3 (Pivot Nodes). An even pivot node is a node of the form [a, a]; an 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.

Note that the edge label between [r, s] and [s, r] must have the form (a, a) because equation (2) 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 [15] 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.

Theorem 4 (Young’s Theorem). 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}), …, (a_{n/2}, a_{n/2−1}), in that order, corresponds to the reverse multiple (a_{n−1}, a_{n−2}, …, 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}), …, (a_{(n+1)/2}, a_{(n−3)/2})

corresponds to the reverse multiple (a_{n−1}, a_{n−2}, …, a_{1}, a_{0})_{g}.

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.

Definition 5 (Young graph). The 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.

Remark 6. Sutcliffe, Kaczynski, Pudwell, and, most generally, Holt discuss 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 twodigit reverse multiples and three-digit reverse multiples involving such truncation: namely, that if (a, b)_{g} is a (g, k) reverse multiple, with 0 ≤ a, b ≤ g − 1, then (a, a + b, b)_{g} is also a (g, k) reverse multiple. Theorem 10 of Holt’s [4] 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}, …, 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.

2.4 Examples

We include several examples to clarify the above material. Consider Y (10, 9), shown in Figure 1; 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 5. To construct the graph H(10, 9), one begins at the starting node, taking equation (2) with g = 10, k = 9, and i = 0 to obtain

\begin{aligned}9a_{0} + 0 & = & a_{n−1} + 10r_{0} \\ 9a_{n−1} + r_{n−2} & = & a_{0} + 10 · 0. \end{aligned}

Note that here the value 0 has been substituted for the terms r_{i−1} and r_{n−1−i} that appear in (2), since r_{−1} = r_{n−1} = 0 by definition (Section 2.1). Checking through all pairs (a_{n−1}, a_{0}) with 0 < a_{0}, a_{n−1} ≤ g −1 = 9, one finds that the only pair that gives integer values for r_{0} and r_{n−2} between 0 and k − 1 inclusive is the pair (1, 9), and the corresponding pair [r_{n−2}, r_{0}] is [0, 8]. Therefore we draw a directed edge from [[0, 0]] = [r_{n−1}, r_{−1}] to [0, 8] = [r_{n−2}, r_{0}] labeled with the pair (1, 9) = (a_{n−1}, a_{0}). We now repeat the above process with i = 1, substituting the values for r_{0} and r_{n−2} into equation (2) to obtain

\begin{aligned}9a_{1} + 8 & = & a_{n−2} + 10r_{1} \\ 9a_{n−2} + r_{n−3} & = & a_{1} + 10 · 0. \end{aligned}  (3)

Checking through all possible (a_{n−2}, a_{1}), one finds the only solution to (3) to be (a_{n−2}, a_{1}) = (0, 8) and [r_{n−3}, r_{1}] = [8, 8]. The process is then repeated with i = 2, 3 … until no new nodes are found, and the resulting graph is shown in Figure 1. Note that [0, 0] and [8, 8] are both even and odd pivot nodes, and that all nodes in the graph precede both [0, 0] and [8, 8]. Therefore, for g = 10 and k = 9, all nodes in the H graph precede a pivot node, so H(10, 9) = Y (10, 9). For general g and k, one removes all nodes in H(g, k) that do note precede pivot nodes that are not themselves pivot nodes to obtain Y (g, k), as described in Definition 5.

Figure 1: Y (10, 9). The nodes [0, 0] and [8, 8] are both even and odd pivot nodes.

For an illustration of Young’s theorem (Theorem 4) for even pivot nodes, consider Y (19, 4), shown in Figure 2. The node [2, 2] is an even pivot node (by Definition 3), and there is a path to [2, 2] from the starting node that consists of the edge labeled (2, 10). By Young’s theorem, the number (2, 10)_{19} should be a (19, 4) reverse multiple, and, in fact, computation verifies that 4 · (2, 10)_{19} = (10, 2)_{19}. There is also a path from the starting node to [2, 2] that consists of the edges labeled (1, 5), (8, 16), and (17, 13), in that order; here, Young’s theorem tells us that (1, 8, 17, 13, 16, 5)_{19} should be a (19, 4) reverse multiple, and computation will verify that 4 · (1, 8, 17, 13, 16, 5)_{19} = (5, 16, 13, 17, 8, 1)_{19}. Beyond the fact that reverse multiples may be read off the Young graph in such a way, Young’s theorem also states that such reverse multiples constitute all reverse multiples.

For an illustration of Young’s theorem for odd pivot nodes, consider Y (14, 3), shown in Figure 3. The node [1, 0] is an odd pivot node, as it directly precedes [0, 1]. There is a path from the starting node to [1, 0] that consists of the edges labeled (1, 5) and (10, 3); furthermore, [0, 1] directly precedes [1, 0] by the edge (7, 7). Therefore, by Young’s theorem, Figure 2: Y (19, 4). All nodes except the starting node [[0, 0]] are both even and odd pivot nodes.

the number (1, 10, 7, 3, 5)_{14} should be a (14, 3) reverse multiple, and computation confirms that this is true.

Thus, more informally, the essence of Young’s theorem is that, given a path from the starting node to an even pivot node, one can construct a reverse multiple with an even number of digits from left to right by first reading off the left components of the edge labels in the order they appear as one goes from the starting node to the pivot node, and then reading off the right components of the edge labels in the order they appear as one goes from the pivot node back to the starting node; and that, given a path from the starting node to an odd pivot node, the same procedure gives a reverse multiple with an odd number of digits, after one inserts in the middle of the constructed number the single value that appears in the label for the edge from the odd pivot node to its reverse (e.g., the number 7 from the edge between [1, 0] and [0, 1] in Y (14, 3), shown in Figure 3).

In this way, we may read off all reverse multiples for given g and k. For g = 10 and Figure 3: Y (14, 3). The nodes [1, 0], [2, 1], [2, 2] and [0, 0] are odd pivot nodes, and [2, 2] and [0, 0] are also even pivot nodes.

k = 9 (see Figure 1), this gives the list 1089, 10989, 109989, 1099989, 10891089, 10999989, 108901089 …, which is entry \underline{A001232} in the On-Line Encyclopedia of Integer Sequences (OEIS) [7]. The other nontrivial base 10 case, that is, g = 10 and k = 4, gives entry \underline{A008918}, and any of the graphs discussed or shown in this paper will give a similar sequence; Figure 2 gives the (base 10) sequence 24, 48, 72, 480, 960, 1440 …, and Figure 3 gives 67275, 946335, 13253175, 185548935, 2584503675, 2597689575 … (neither are listed in the OEIS [7]).

3 1089 graphs

In this section and the two following it we present our results. This section and Section 4 both prove conjectures of Sloane (Theorems 14 and 31), while Section 5 discusses another type of graph mentioned in his paper. Section 4 also contains a result (Theorem 29) on Young graph isomorphism and a result (Corollary 28) on the nodes adjacent to [0, 0].

The results of this section and of Sections 4 and 5 mostly concern isomorphism of Young graphs, which is a somewhat stronger condition than isomorphism in ordinary directed graphs because of the added structure of node labels in Young graphs. The concept was introduced by Sloane.

Definition 7 (Isomorphism). Two Young graphs Y and Y′ are isomorphic as Young graphs, written Y ≃ Y′, if there is a function ϕ from the nodes of Y to those of Y′ such that, if G and G′ are respectively the directed graphs^{4} obtained by removing the edge and node labels from Y and Y′, ϕ acts as an isomorphism of G and G′, and furthermore such that x is an even pivot node in Y if and only if ϕ(x) is an even pivot node in Y′, and x is an odd pivot node in Y if and only if ϕ(x) is an odd pivot node in Y′ (that is, ϕ is a pivot node-preserving isomorphism of the underlying directed graphs).

Remark 8. Holt classifies reverse multiples based on the “structure of their carries,” “carries” being the numbers r_{i}. Since it is through the labels [r_{n−1−i}, r_{i−1}] that Young graph isomorphism is determined, studying classes of reverse multiples with similar carry structure should be similar to studying reverse multiples with isomorphic Young graphs; indeed, this relation is seen in the correspondence between Holt’s study of symmetric and shifted-symmetric reverse multiples and the material of Sections 3 and 4, as will become evident throughout this paper.

For an example of isomorphic graphs, see Figures 1 and 4. It is noted in Section 3.2 of Sloane’s paper that Young graphs isomorphic to Y (10, 9) (Figure 1) are fairly common, for example Y (10, 4), Y (15, 4), and Y (20, 9); the following definition is then made.

Definition 9 (1089 graph). A Young graph Y such that Y ≃ Y (10, 9) is called a 1089 graph.

The number 1089 is the smallest (10, 9) reverse multiple; thus the name “1089 graph.” Sloane’s Conjecture 3.1 characterizes the occurrences of 1089 graphs; we prove this conjecture in Theorem 14. The work of this section is also related to Holt’s [6] work on 1089 palintiples. We require several preliminary results.

Lemma 10. If a Young graph contains a node [r, s] directly preceding a node [t, u] by an edge (a, b) then it also contains the node [u, t] directly preceding the node [s, r] by the edge (b, a).

We omit the proof; the interested reader is directed to property P3 in Section 2.7 of Sloane or Theorem 2 of Young [16].

Corollary 11. Every node in a Young graph is a predecessor of [0, 0].

Proof. This is a direct consequence of Lemma 10 and the fact that all nodes in a Young graph precede some pivot node and succeed the starting node.

Two more lemmas are needed to prove the main theorem; we now prove the first.

4These are referred to as “underlying directed graphs” by Sloane.

Lemma 12. Let g = b(k + 1), with b a positive integer, and let m be a nonnegative integer. Then, if the (g, k) Young graph contains a node of the form [\frac{s(k−1)}{b^{m}}, \frac{t(k−1)}{b^{m+1}}], where s and t are integers, the following are true:

(i) The edges leading from [\frac{s(k−1)}{b^{m}}, \frac{t(k−1)}{b^{m+1}}] have the form (\frac{s(k−1)}{b^{m−1}} + u, \frac{(t−b^{2}s)(k−1)}{b^{m+1}} + ku), where u is some integer.

(ii) The edge (\frac{s(k−1)}{b^{m−1}} + u, \frac{(t−b^{2}s)(k−1)}{b^{m+1}} + ku) leading from the node [\frac{s(k−1)}{b^{m}}, \frac{t(k−1)}{b^{m+1}}] terminates

at the node [\frac{t(k−1)}{b^{m+1}}, \frac{(t−b^{2}s+b^{m+1}u)(k−1)}{b^{m+2}}]. (iii) t ≡ 0 (mod b).

Proof. First note that 0 ≤ s ≤ b^{m} and 0 ≤ t ≤ b^{m+1}, because [s(k − 1)/b^{m}, t(k − 1)/b^{m+1}] is in the Young graph and 0 ≤ r_{i} ≤ k − 1 for all i. Throughout the following proof let a = a_{i}, A = a_{n−1−i}, r = r_{i}, and R = r_{n−2−i}, where i is the number such that [s(k − 1)/b^{m}, t(k − 1)/b^{m+1}] = [r_{i−1}, r_{n−1−i}]. We will establish the equation rk = \frac{(b^{m+1}a+t)(k−1)}{b^{m+2}} − \frac{s(k−1)}{b^{m}}, whence we directly relate a and A and the desired conclusions (i), (ii), and (iii) follow easily.

By equation (2), A = ka + \frac{t(k−1)}{b^{m+1}} − rg and kA + R = a + \frac{s(k−1)}{b^{m}}g. These two equations imply R + (k^{2} − 1)a + \frac{tk(k−1)}{b^{m+1}} = g (\frac{s(k−1)}{b^{m}} + rk). Because 0 ≤ R ≤ k − 1, we now have

(k^{2} − 1)a + \frac{tk(k − 1)}{b^{m+1}} ≤ g (\frac{s(k − 1)}{b^{m}} + rk) ≤ (k^{2} − 1)a + \frac{tk(k − 1)}{b^{m+1}} + k − 1.

Since g = b(k + 1), multiplying this inequality by b^{m+1}/(k + 1) yields

\begin{aligned}b^{m+2} (\frac{s(k−1)}{b^{m}} + rk) & ≥ & b^{m+1}(k − 1)a + tk − 2t + \frac{2t}{k+1} \\ b^{m+2} (\frac{s(k−1)}{b^{m}} + rk) & ≤ & b^{m+1}(k − 1)a + tk − 2t + \frac{2t}{k+1} + b^{m+1} − \frac{2b^{m+1}}{k+1} . \end{aligned}  (4)

The inequalities in (4) give lower and upper bounds on b^{m+2} (\frac{s(k−1)}{b^{m}} + rk). Note that the difference between these bounds is b^{m+1} − \frac{2b^{m+1}}{k+1} < b^{m+1}, and that b^{m+2} (\frac{s(k−1)}{b^{m}} + rk) is a multiple of b^{m+1}. This implies that b^{m+2} (\frac{s(k−1)}{b^{m}} + rk) is the only multiple of b^{m+1} satisfying the bounds in (4). Now, because k ≥ 2 and 0 ≤ t ≤ b^{m+1}, it may be simply shown that b^{m+1}(k − 1)a + tk − t satisfies the bounds in (4), and because \frac{t(k−1)}{b^{m+1}} is an integer (it is a node label) b^{m+1}(k − 1)a + tk − t must be a multiple of b^{m+1}. This establishes b^{m+1}(k − 1)a + tk − t = b^{m+2} (\frac{s(k−1)}{b^{m}} + rk).

It now follows that b^{m+2} (\frac{s(k−1)}{b^{m}} + rk) = b^{m+1}(k − 1)a + tk − t, which implies

rk = \frac{(b^{m+1}a + t)(k − 1)}{b^{m+2}} − \frac{s(k − 1)}{b^{m}}.  (5)

Equation (2) implies kA + rkg = k^{2}a + \frac{kt(k−1)}{b^{m+1}}. Substituting for rk via equation (5) and substituting b(k + 1) for g, we obtain

a = kA + \frac{t(k − 1)}{b^{m+1}} − \frac{s(k^{2} − 1)}{b^{m−1}}.  (6)

Let u = A − \frac{s(k−1)}{b^{m−1}} ∈ ℤ. Substituting u into equation (6) yields a = \frac{(t−b^{2}s)(k−1)}{b^{m+1}} + ku, establishing (i). Now equation (2) gives A + rg = ka + \frac{t(k−1)}{b^{m+1}} and a + \frac{s(k−1)}{b^{m}}g = kA + R, and substituting in for A and a in terms of the parameter u and for g in terms of b and k yields (ii).

Note that the new node [t(k − 1)/b^{m+1}, (t − b^{2}s + b^{m+1}u)(k − 1)/b^{m+2}] has the same form as the directly preceding node [s(k − 1)/b^{m}, t(k − 1)/b^{m+1}]. Thus all successors of the node [s(k − 1)/b^{m}, t(k − 1)/b^{m+1}] have the form [s′(k − 1)/b^{m′}, t′(k − 1)/b^{m′+1}]. Additionally, we have t ≡ t − b^{2}s + b^{m+1}u (mod b), so that t ≡ s′ ≡ t′ (mod b), inductively. Now, if [s(k −1)/b^{m}, t(k −1)/b^{m+1}] is in Y (g, k), it must precede [0, 0] by Corollary 11, so there must be some t′ = 0, which implies (iii).

One further lemma is required before we may characterize all occurrences of the 1089 graph.

Lemma 13. If, in Y (g, k), a node [r, s] directly precedes [0, 0] and is not an odd pivot node then k + 1 | g.

Proof. By Lemma 10, [0, 0] must directly precede [s, r]; let the edge from [0, 0] to [s, r] be labeled (a, b). We then have kb = a + rg and ka + s = b, by equation (2); adding these equations and rearranging yields (k − 1)(a + b) = rg − s.

It is also known that there can be no edge from [r, s] to [s, r]. If we attempt to find such an edge by solving equation (2) for the edge (x, y) from [r, s] to [s, r], we find x = y = (rg −s)/(k −1) = a+b, and so a+b must be an unsatisfactory edge label. It is only required of edge labels that they be integers between 0 and g − 1 inclusive; a + b is a nonnegative integer, so a + b ≥ g. Now by Sloane’s Theorem 3.4, we have k + 1 | g.

We may now prove the main theorem of this section.

Theorem 14 (Conjecture 3.1 of Sloane). Y (g, k) is a 1089 graph if and only if k + 1 | g. Also, if Y (g, k) is a 1089 graph, with g = b(k + 1), its labels are those shown in Figure 4.

Proof. We first show that k + 1|g implies Y (g, k) is a 1089 graph, and then the converse. The values of the edge and node labels in Figure 4 are established in the first part of the proof.

Suppose g = b(k + 1). We may now determine Y (g, k) by repeated application of Lemma 12. Consider the starting node: [[0, 0]] = [[0(k − 1)/b^{0}, 0(k − 1)/b^{1}]], so by Lemma 12.(ii) the starting node can only directly precede nodes of the form [0(k − 1)/b, bu(k − 1)/b^{2}] = [0(k − 1)/b^{0}, u(k − 1)/b^{1}]. Note that if [0(k − 1)/b^{0}, u(k − 1)/b^{1}] is a node, we have u ≡ 0 (mod b) by Lemma 12.(iii). We also have 0 ≤ u ≤ b because 0 ≤ r_{i} ≤ k − 1 for all i, so u = 0

Figure 4: Y (b(k + 1), k)

or u = b. But the edge leading to this first node has the form (u, ku), by Lemma 12.(i), and a_{0} ≠ 0 so u = b. Therefore the starting node directly precedes only the node [0, k − 1], by the edge (b, bk).

Similar reasoning shows that [0, k − 1] only directly precedes [k − 1, k − 1], by the edge (b−1, bk−1); that [k−1, k−1] only directly precedes itself, by the edge (bk−b−1, bk−b−1), and [k − 1, 0], by the edge (bk − 1, b − 1); that [k − 1, 0] only directly precedes [0, 0], by the edge (bk, b); and that [0, 0] only directly precedes itself, by the edge (0, 0), and [0, k − 1], by the edge (b, bk). The graph Y (g, k) thus determined is shown in Figure 4, and is a 1089 graph.

Now suppose that Y (g, k) is isomorphic to Y (10, 9) (Figure 1). The starting node then has a direct successor [r, s], with r ≠ s, since the node is not a pivot node, by the isomorphism. Again by the isomorphism, this node [r, s] has an even pivot node as its only direct successor, which we call [t, t]. This node [t, t] has a self-loop and directly precedes only one other node; by Lemma 10 this node must be [s, r] – note that [s, r] must be distinct from [t, t] because s ≠ r. The node [s, r] directly precedes only one other node, and by Lemma 10 this must be [0, 0], since [r, s] directly succeeds the starting node. Now [s, r] is not an odd pivot node, because all odd pivot nodes are even pivot nodes in 1089 graphs and s ≠ r, but it directly precedes [0, 0]. Therefore, by Lemma 13, we have k + 1 | g. By the first part of this proof, the Y (g, k) determined is shown in Figure 4.

Remark 15. This theorem is related Holt’s work (Theorem 6 in his first paper [4] and Conjectures 1 and 3 and Corollary 2 in his second [6]) on symmetric reverse multiples (defined in his first paper [4]): reverse multiples such that r_{i−1} = r_{n−2−i}, as is the case with reverse multiples arising from 1089 graphs. In his second paper, Holt conjectures that a (g, k) reverse multiple is symmetric if and only if k + 1 | g. If true, this conjecture would give a further distinction to the 1089 graph, beyond the number theoretical characterization and the corollaries below: it is the graph for which, if [a, b] ⟶ [c, d] is in the graph, then b = c. Note also that, in finding the edge and node labels in 1089 graphs, Theorem 14 also establishes part of Theorem 3.2 in Sloane’s paper, which in addition finds the generating function for the number of reverse multiples with a given number of digits and characterizes the associated reverse multiples for 1089 graphs; Holt [6] makes a related conjecture (Conjecture 3) for the broader problem of symmetric reverse multiples.

It is a consequence of Theorem 14 that, for g = b(k + 1), all (g, k) reverse multiples are contained in the list (b, b − 1, bk − 1, bk)_{g}, (b, b − 1, bk + b − 1, bk − 1, bk)_{g}, (b, b − 1, bk + b − 1, bk + b − 1, bk − 1, bk)_{g}, (b, b − 1, bk + b − 1, bk + b − 1, bk + b − 1, bk − 1, bk)_{g}, (b, b − 1, bk − 1, b − 1, bk, b, b − 1, bk − 1, bk)_{g}, … that may be read off Figure 4 in the manner described in Section 2.4. Furthermore, several minor results follow immediately from Theorem 14.

Corollary 16. In a Young graph that is not a 1089 graph (k + 1 ∤ g), all direct predecessors of [0, 0] are odd pivot nodes.

Proof. This follows from Lemma 13 and Theorem 14.

Corollary 17. All Young graphs contain an odd pivot node other than [0, 0].

Proof. Corollary 11 implies that the node [0, 0] is in all Young graphs Y (g, k) (also see property P4 in Section 2.7 in Sloane [11]). As it is in the Young graph, the node [0, 0] must have some direct predecessor [r, s] ≠ [0, 0]. If [r, s] is not an odd pivot node then the Young graph is a 1089 graph, by Corollary 16, in which case it contains an odd pivot node by definition.

Corollary 18 (Conjecture 3.5 of Sloane). If there is a (g, k) reverse multiple with first and last digits that sum to g, Y (g, k) is a 1089 graph. If Y (g, k) is a 1089 graph then every (g, k) reverse multiple has first and last digits summing to g.

Proof. By Sloane’s Theorem 3.4 [11], if a_{0} + a_{n−1} = g then we must have a_{n−1} = \frac{g}{k+1}, so that Y (g, k) is a 1089 graph by Theorem 14. If Y (g, k) is a 1089 graph then, by Theorem 14, a_{0} = \frac{gk}{k+1} and a_{n−1} = \frac{g}{k+1}, and these numbers sum to g.

Isomorphism is an equivalence relation on Young graphs, and thus defines a corresponding equivalence relation on pairs of integers (g, k): we take (g, k) ∼ (g′, k′) if and only if Y (g, k) ≃ Y (g′, k′). Via these corresponding relations, any equivalence class X of Young graphs corresponds to an equivalence class^{5} C of pairs (g, k), and so for any equivalence class X of Young graphs we can also define a relation R_{X}(g, k) on g and k to be the relation that holds if and only if (g, k) ∈ C; this relation sometimes coincides with a convenient, simply expressed arithmetical condition, as is the case for 1089 graphs and the complete graphs discussed in Section 4. Theorem 14 has a somewhat interesting consequence regarding these relations and equivalence classes.

Corollary 19. The set of 1089 graphs is the only equivalence class X of Young graphs such that R_{X}(g, k) holds if and only if f(k) | g, for some fixed function f : ℤ^{+} → ℤ.

Proof. Suppose there is such an equivalence class X of Young graphs. Then Y (18|f(17)|, 17) is in X, but by Theorem 14 is also a 1089 graph, so X is the set of 1089 graphs.

While not related to 1089 graphs, the following result comes from a line of reasoning similar to that of Lemma 13, and so we include it in this section.

Proposition 20. If a node [r, s] directly precedes, by an edge (a, b), a node [t, t] that has a self-loop (c, c), [r, s] is an odd pivot node if and only if 0 ≤ a + b − c ≤ g − 1, and if it is an odd pivot node then the edge from [r, s] to [s, r] is labeled (a + b − c, a + b − c).

Proof. Taking equation (2) for the given edge (a, b) gives kb + s = a + tg and ka + t = b + rg, yielding (k − 1)(a + b) = rg − s + (g − 1)t. Taking equation (2) for the self-loop at [t, t] gives (g − 1)t = (k − 1)c, so that (rg − s)/(k − 1) = a + b − c. The edge from [r, s] to [s, r] can be found, from equation (2), to be ((rg − s)/(k − 1), (rg − s)/(k − 1)) = (a + b − c, a + b − c). So if 0 ≤ a + b − c ≤ g − 1 then there is an edge from [r, s] to [s, r], and it is labeled (a + b − c, a + b − c), and if there is an edge from [r, s] to [s, r] it must be (a + b − c, a + b − c) and so 0 ≤ a + b − c ≤ g − 1.

4 Complete graphs

We now turn to the proof of another of Sloane’s conjectures (Conjecture 3.7 in his paper), concerning complete Young graphs.

Definition 21 (complete graph). A Young graph Y is called a complete Young graph on m nodes when the nodes that are not [[0, 0]] form the complete directed graph on m nodes and there is an edge from [[0, 0]] to every node except for [0, 0]. The equivalence class of complete Young graphs on m nodes is denoted K_{m}.

5Note that two degenerate Young graphs – graphs for which H(g, k) contains no pivot nodes – are isomorphic. The equivalence class of (g, k) pairs corresponding to the equivalence class of degenerate graphs is of great interest, as characterizing this equivalence class is equivalent to characterizing all g and k for which reverse multiples exist.

Figure 2 shows an example of a complete graph, Y (19, 4) ∈ K_{4}. Sloane’s conjecture characterizes all (g, k) that correspond to graphs in K_{m}; we prove this conjecture in Theorem 31. Several preliminary results are needed, some of which were proven by Sloane, and several other interesting digressions from the course of the proof are included.

Lemma 22. All Young graphs contain the node [0, 0].

Lemma 23. A Young graph is a complete graph if and only if every node has the form [r, r].

We omit the proofs; the interested reader is directed to property P4 in Section 2.7 (or even Corollary 11 here) for Lemma 22 and to Theorem 3.6 for Lemma 23 of Sloane’s paper. We now begin work towards Theorem 31.

Lemma 24. For given g and k, if there is a positive integer s ≤ k − 1 such that s (\frac{g−k}{k^{2}−1}) is an integer then Y (g, k) is a complete Young graph.

Proof. We show that all nodes in Y (g, k) have the form [r, r], so that the conclusion follows from Lemma 23.

Consider a node [r, r] in Y (g, k). Suppose this node directly precedes some node [r_{n−2−i}, r_{i}] by an edge (a_{n−1−i}, a_{i}). We can solve equation (2) for this edge to yield

a_{i} = \frac{rg − rk + r_{i}kg − r_{n−2−i}}{k^{2} − 1} = r\frac{g − k}{k^{2} − 1} + r_{i} \frac{kg − 1}{k^{2} − 1} + \frac{r_{i} − r_{n−2−i}}{k^{2} − 1} .

Therefore, s (\frac{r_{i}−r_{n−2−i}}{k^{2}−1} ) = sa_{i} − r (s\frac{g−k}{k^{2}−1}) − r_{i} (ks\frac{g−k}{k^{2}−1} + s) is an integer. Now

s\frac{|r_{i} − r_{n−2−i}|}{k^{2} − 1} ≤ (k − 1)\frac{|r_{i} − r_{n−2−i}|}{k^{2} − 1} ≤ (k − 1)\frac{k − 1}{k^{2} − 1} < 1.

Therefore s\frac{|r_{i}−r_{n−2−i}|}{k^{2}−1} = 0, so r_{i} = r_{n−2−i}, because s > 0.

Repeating this argument proves that all successors of a node [r, r] have the form [r′, r′]; 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 23.

Remark 25. This is related to Theorem 9 in Holt’s first paper [4] and Corollary 6 in his second [6]. 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 8.

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 31 to include it here.

Proposition 26. If there are two even pivot nodes in Y (g, k) that directly precede the same node, Y (g, k) is a complete graph.

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 ≠ y. Then, by equation (2), 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 = (\frac{kg−1}{k^{2}−1}) (y − x). Therefore (\frac{g−k}{k^{2}−1}) |y − x| = |d − b| is a positive integer and

|y − x| = (\frac{k^{2}−1}{kg−1}) |c − a| ≤ (\frac{k^{2}−1}{kg−1}) g < k, so, by Lemma 24, Y (g, k) is a complete graph.

Note that this proposition applies to the starting node, as well as all even pivot nodes, so long as the other node is not [0, 0].

Corollary 27. If, in a Young graph Y, an even pivot node [s, s], with s ≠ 0, directly precedes or succeeds [0, 0] (the two are equivalent by Lemma 10), Y is a complete graph.

Proof. Under these conditions [s, s] and [0, 0] both directly precede the same node (the node [0, 0]), and are even pivot nodes, so that Y is complete by Proposition 26.

Corollary 28. In Young graphs that are neither complete graphs nor 1089 graphs, all direct predecessors of [0, 0] are odd, and not even, pivot nodes. The direct successors of [0, 0] are not even pivot nodes.

Proof. This follows from Corollaries 16 and 27.

This line of reasoning culminates in a general result on isomorphism.

Theorem 29. If Y and Y′ are isomorphic as Young graphs by an isomorphism ϕ then ϕ([[0, 0]]) = [[0, 0]] and ϕ([0, 0]) = [0, 0].

Proof. Clearly ϕ([[0, 0]]) = [[0, 0]], since [[0, 0]] is the only node which is the successor of no other node. We must now only show that ϕ([0, 0]) = [0, 0]. To this end, suppose ϕ([0, 0]) ≠ [0, 0]. As a preliminary, note that the direct successors of the starting node are also direct successors of the node [0, 0], because [0, 0] is in the graph by Lemma 22 and the equations given by (2) governing the node and edge labels are the same for the starting node and [0, 0].^{6}

Because Y exists and is connected, it must include an edge [[0, 0]] ⟶ [r, s], for some node [r, s]. Since ϕ is an isomorphism, the edge [[0, 0]] ⟶ ϕ([r, s]) is included in Y′, and consequently the edge [0, 0] ⟶ ϕ([r, s]) is also included in Y′. Because [[0, 0]] ⟶ [r, s] is in Y, the edge [0, 0] ⟶ [r, s] must also be in Y, so ϕ([0, 0]) ⟶ ϕ([r, s]) is included in Y′. Thus [0, 0] ⟶ ϕ([r, s]) and ϕ([0, 0]) ⟶ ϕ([r, s]) are both included in Y′, and so Y and Y′ must be complete graphs, by Proposition 26. But in complete graphs, [0, 0] is the only node that does not directly succeed the starting node, so ϕ([0, 0]) = [0, 0], contrary to assumption.

6It is, however, possible for [0, 0] to directly precede a node x that does not directly succeed the starting node because the left label on the edge from [0, 0] to x is 0.

We now return to the proof of Sloane’s conjecture.

Lemma 30. For all of the nodes [r, r] in a complete graph Y (g, k), r (\frac{g−k}{k^{2}−1}) is an integer and r ≤ k − 1.

Proof. Consider a reverse multiple that corresponds, as per Theorem 4, to a path through all nodes in Y (g, k). This is a shifted-symmetric reverse multiple, and so the desired conclusion follows by Theorem 9 of Holt [4]. Alternatively, a proof method similar to that in Lemma 24 may be used, where one proves that if [r, r] satisfies the conditions then all its direct successors do as well, so that all nodes in the graph satisfy the conditions because the starting node does.

We may now prove the main result of this section.

Theorem 31 (Conjecture 3.7 of Sloane). Y (g, k) is in K_{m} if and only if there are exactly m − 1 positive integers s_{1}, s_{2}, …, s_{m−1} such that s_{j} (\frac{g−k}{k^{2}−1}) is an integer and s_{j} ≤ k − 1 for all 1 ≤ j ≤ m − 1.

Proof. We first show that the existence of the s_{j} implies that Y (g, k) is in K_{m}, and then the converse.

Suppose that there exist exactly m − 1 positive integers s_{1}, s_{2}, … s_{m−1} less than k such that s_{j} (\frac{g−k}{k^{2}−1}) is an integer. Since s_{1} exists, by Lemma 24, Y (g, k) must be in K_{l} for some l. By definition graphs in K_{l} have l + 1 nodes, of which one is the starting node and one the node [0, 0] (by Lemma 22). The remaining l − 1 nodes, by Lemmas 23 and 30, have the form [r, r] where r ≤ k − 1 is a positive integer such that r(g − k)/(k^{2} − 1). There are only m − 1 such positive integers, so l ≤ m. Furthermore, for every positive integer r ≤ k − 1 such that r(g − k)/(k^{2} − 1) is an integer, Theorem 9 of Holt [4] gives a reverse multiple that corresponds via Theorem 4 to the path [[0, 0]] ⟶ [r, r]. Therefore every node [r, r] is in Y (g, k), so that m ≤ l.^{7} This completes this part of the proof.

Now suppose that Y (g, k) is in K_{m}. By Lemma 30, all the nodes [r, r] of Y (g, k) are such that r(g − k)/(k^{2} − 1) is an integer and r ≤ k − 1. In particular, we know that there exist such numbers r. Suppose that exactly l − 1 such numbers r exist. Then, by the first part of this proof, Y (g, k) is in K_{l}. Now, because K_{l} ∩ K_{m} is non-empty, we have K_{l} = K_{m}, so l = m.

Note the similarity between the following result, as well as Proposition 33, and Theorem 4 of Holt’s second paper [6], which states that a (g, k) reverse multiple is shifted-symmetric if and only if gcd(g − k, k^{2} − 1) ≥ k + 1.

Corollary 32. Y (g, k) is in K_{m} if and only if ⌊gcd(g − k, k^{2} − 1)/(k + 1)⌋ = m − 1.

Proof. It is easily shown that there exist m − 1 positive integers s ≤ k − 1 such that s(g − k)/(k^{2} − 1) is an integer if and only if m − 1 ≤ gcd(g − k, k^{2} − 1)/(k + 1) < m.

7If one wishes to keep to a Young graphical perspective, it may also be shown computationally from equation (2) that every node [r, r] directly succeeds the starting node.

The earliest paper [12] found in this topic, by Sutcliffe, is largely concerned with reverse multiples with two digits; he concludes (Theorem 2 in his paper) that, for given g, there exists a k such that there exists a (g, k) reverse multiple with two digits if and only if g + 1 is composite. However, he, and Kaczynski [8] after him, are not particularly concerned with the multiplier k: in their terminology, an n-digit (g, k) reverse multiple is known only as an “n-digit solution for g.” Corollaries 27 and 32 now imply a result on two-digit reverse multiples with reference to k, a connection hinted at in property P7 of Sloane.

Proposition 33. A two-digit (g, k) reverse multiple exists if and only if k + 1 ≤ gcd(g − k, k^{2} − 1).

Proof. By Theorem 4, if there is a two-digit reverse multiple, then there exists a path of length 1 in Y (g, k) from the starting node to an even pivot node, so that there must be an even pivot node directly succeeding the starting node. This even pivot node will also directly succeed the node [0, 0], because, as mentioned previously, the equations yielded by equation (2) are the same for the starting node and [0, 0]. This makes Y (g, k) complete, by Corollary 27. Corollary 32, now implies the desired result.

Conversely, suppose k + 1 ≤ gcd(g − k, k^{2} − 1). Now Y (g, k) is complete by Corollary 32, so that there exists a path of length 1 in the graph from the starting node to an even pivot node – namely, from the starting node to any adjacent node – so there exists a (g, k) reverse multiple with two digits, by Theorem 4.

This result could also follow by Theorem 4 of Holt [6] and Young’s theorem (Theorem 4 here).

Indeed, some simple manipulations show that this result agrees exactly with the characterization of g by Sutcliffe.

5 Cyclic graphs

We now include a minor result and a conjecture on another type of graph mentioned by Sloane.

Definition 34 (cyclic graph). A Young graph Y is called a cyclic Young graph on n nodes if the nodes of Y that are neither the starting node nor [0, 0] form the cyclic directed graph on n nodes, and there exist two nodes N_{1} and N_{2} ≠ [0, 0] such that N_{1} directly precedes N_{2}, the only direct predecessor of [0, 0] (other that itself ) is N_{1}, and the only direct successor of [0, 0] (other than itself) and starting node is N_{2}. The equivalence class of cyclic Young graphs on n nodes is denoted Z_{n}.

For examples of cyclic graphs, see Figures 5 and 6. Sloane makes no conjecture analogous to Theorems 14 and 31 for cyclic graphs. We also have no such conjecture; however, examination of data for low values of g suggests the following.

Conjecture 35. For t ≥ 3 and n ≥ 2, the Young graph Y ((n^{2}+n)t−n^{2}+n+1, n^{2}t−(n−1)^{2}) is in Z_{2n−1}.

We now prove two minor results on similar types of graphs.

Theorem 36. For t ≥ 3 and n ≥ 2, the Young graph Y ((n^{2} + n)t − 1, n^{2}t − 1) is in Z_{3}, with node and edge labels as shown in Figure 5.

Figure 5: Y ((n^{2} + n)t − 1, n^{2}t − 1) for n ≥ 2 and t ≥ 3

Proof. Let g = (n^{2} + n)t − 1 and k = n^{2}t − 1. We compute H(g, k) and thence Y (g, k).

We may compute all direct successors of the starting node. By equation (2), any node [r′_{0}, r_{0}] that directly succeeds the starting node by an edge (a′_{0}, a_{0}) must satisfy

\begin{aligned}(n^{2}t − 1)a_{0} & = & a′_{0} + r_{0}((n^{2} + n)t − 1) \\ (n^{2}t − 1)a′_{0} + r′_{0} & = & a_{0}. \end{aligned}  (7)

Because a_{0} ≤ g − 1 and r′_{0} ≥ 0, the second equation of (7) implies a′_{0} ≤ ((n^{2} + n)t − 2)/(n^{2}t − 1) = 1 + 1/n + (1/n − 1)/(n^{2}t − 1) < 2. Recall a′_{0} ≠ 0 because it is the last digit of a reverse multiple. Therefore a′_{0} = 1. Substituting into the first equation of (7) and taking the equation modulo g gives (n^{2}t − 1)a_{0} ≡ 1 (mod g), so that a_{0} ≡ −(n + 1) (mod g). Since 0 < a_{0} ≤ g − 1, this implies a_{0} = (n^{2} + n)t − (n + 2). Substituting the values a′_{0} = 1 and a_{0} = (n^{2} + n)t − (n + 2) into equation (7) gives r′_{0} = nt − (n + 1) and r_{0} = n^{2}t − (n + 1). Therefore the only direct successor, in H(g, k), of the starting node is the node [nt − (n + 1), n^{2}t − (n + 1)], and the corresponding edge is (1, (n^{2} + n)t − (n + 2)).

Similar considerations for [nt−(n+1), n^{2}t−(n+1)] show that its only direct successor in H(g, k) is [(n^{2} −n)t+2n−2, (n^{2} −n)t+2n−2], the corresponding edge being ((n+1)t−(n+ 2), (n^{2} −1)t+2n−1). In turn, similar considerations for [(n^{2} −n)t+2n−2, (n^{2} −n)t+2n−2] show that its only direct successor in H(g, k) is [n^{2}t − (n + 1), nt − (n + 1)], by the edge ((n^{2} − 1)t + 2n − 1, (n + 1)t − (n + 2)), and similar considerations for [n^{2}t − (n + 1), nt − (n + 1)] show that its only two direct successors are [nt − (n + 1), n^{2}t − (n + 1)], by the edge ((n^{2} + n)t − (n + 1), (n^{2} + n)t − (n + 1)), and [0, 0], by the edge ((n^{2} + n)t − (n + 2), 1). It may then be shown that the only direct successors of [0, 0] are [nt − (n + 1), n^{2}t − (n + 1)] and itself, in reasoning almost identical to that of the computation of the direct successors of the starting node. This fully determines H(g, k). All nodes in the graph precede some pivot node, and so Y (g, k) is the same labeled graph as H(g, k), namely the one depicted in Figure 5.

A similar result holds for cyclic graphs on five nodes.

Theorem 37. For t ≥ 3 and n ≥ 3, the Young graph Y ((n^{2} + n)t − (n + 2), n^{2}t − (n + 1)) is in Z_{5}, with node and edge labels as shown in Figure 6.

Figure 6: Y ((n^{2} + n)t − (n + 2), n^{2}t − (n + 1)) for n ≥ 3 and t ≥ 3

Proof. The proof is similar to the proof Theorem 36. Let g = (n^{2} + n)t − (n + 2) and k = n^{2}t − (n + 1). We compute H(g, k) and thence Y (g, k).

We may compute all direct successors of the starting node. By equation (2), any node [r′_{0}, r_{0}] that directly succeeds the starting node by an edge (a′_{0}, a_{0}) must satisfy

\begin{aligned}(n^{2}t − (n + 1))a_{0} & = & a′_{0} + r_{0}((n^{+}n)t − (n + 2)) \\ (n^{2}t − (n + 1))a′_{0} + r′_{0} & = & a_{0}. \end{aligned}  (8)

Because a_{0} ≤ g − 1 and r′_{0} ≥ 0, the second equation of (8) implies a′_{0} ≤ ((n^{2} + n)t − (n + 3))/(n^{2}t − (n + 1)) = 1 + 1/n + (1/n − 1)/(n^{2}t − (n + 1)) < 2. Recall a′_{0} ≠ 0 because it is the last digit of a reverse multiple. Therefore a′_{0} = 1. Substituting into the first equation of (8) and taking the equation modulo g gives (n^{2}t−(n+1))a_{0} ≡ 1 (mod g), so that a_{0} ≡ −(n+1) (mod g). Since 0 < a_{0} ≤ g − 1, this implies a_{0} = (n^{2} + n)t − (2n + 3). Substituting the values a′_{0} = 1 and a_{0} = (n^{2} + n)t − (2n + 3) into equation (8) gives r′_{0} = nt − (n + 2) and r_{0} = n^{2}t − (2n + 1). Therefore the only direct successor, in H(g, k), of the starting node is node [nt − (n + 2), n^{2}t − (2n + 1)], and the corresponding edge is (1, (n^{2} + n)t − (2n + 3)).

Similar considerations for [nt − (n + 2), n^{2}t − (2n + 1)] show that its only direct successor in H(g, k) is [(n^{2}−2n)t+n−1, (n^{2}−n)t+n−2], the corresponding edge being ((n+1)t−(n+ 3), (n^{2} − 1)t + n − 2). In turn, similar considerations for [(n^{2} − 2n)t + n − 1, (n^{2} − n)t + n − 2] show that its only direct successor in H(g, k) is [2nt − 2n, 2nt − 2n], by the edge ((n^{2} − n − 2)t+n, (2n+2)t−(2n+2)); similar considerations for [2nt−2n, 2nt−2n] show that its only direct successor in H(g, k) is [(n^{2} − n)t + n − 2, (n^{2} − 2n)t + n − 1], by the edge ((2n + 2)t − (2n + 2), (n^{2} − n − 2)t + n); similar considerations for [(n^{2} − n)t + n − 2, (n^{2} − 2n)t + n − 1] show that its only direct successor in H(g, k) is [n^{2}t − (2n + 1), nt − (n + 2)], by the edge ((n^{2} −1)t+n−2, (n+1)t−(n+3)); and similar considerations for [n^{2}t−(2n+1), nt−(n+2)] show that its only two direct successors are [nt − (n + 2), n^{2}t − (2n + 1)], by the edge ((n^{2} + n)t − (2n + 2), (n^{2} + n)t − (2n + 2)), and [0, 0], by the edge ((n^{2} + n)t − (2n + 3), 1). It may then be shown that the only direct successors of [0, 0] are [nt − (n + 2), n^{2}t − (2n + 1)] and itself, in reasoning almost identical to that of the computation of the direct successors of the starting node. This fully determines H(g, k). All nodes in the graph precede some pivot node, and so Y (g, k) is the same labeled graph as H(g, k), namely the one depicted in Figure 6.

While lists of reverse multiples arising from Figures 5 and 6 may be given in general form, as with Figure 4, we omit them for the sake of convenience, as the smallest reverse multiple involved, that is, the four-digit reverse multiple corresponding to the path in Y ((n^{2} + n)t − 1, n^{2}t − 1) (Figure 5) from the starting node to [nt − n − 1, n^{2}t − n − 1] to [(n^{2} − n)t + 2n − 2, (n^{2} − n)t + 2n − 2], has the rather cumbersome general form of either (1, (n + 1)t − (n + 2), (n^{2} − 1)t + 2n − 1, (n^{2} + n)t − (n + 2))_{(n^{2}+n)t−1} or n^{2}(n + 1)^{4}t^{3} − n(n^{4} + 6n^{3} + 12n^{2} + 10n + 3)t^{2} + (4n^{3} + 10n^{2} + 8n + 2)t − (4n + 4). In its smallest case, n = 2 and t = 3, the graph in Figure 5 gives the (base 10) sequence 6576, 32314464, 549240672, 9336986208, 158728660320, 158760968208 …, and the graph in Figure 6, in its smallest case, n = t = 3, gives the sequence 34633320, 991522582544640, 30737199019884240, 952853168577411840, 29538448224860767440, 915691894969644791040 …; neither appear in the OEIS [7].

6 Further research

Given the scarcity of work on the problem, it is not particularly surprising that Young graphs, especially the relation between the associated number theory and graph theory, are not well understood. This paper makes some limited progress, mostly concerning specific equivalence classes of Young graphs, from the work of Young and Sloane, but still little is known in general. We now discuss some directions for potential further work on the problem, after which discussion we include several conjectures (Section 6.1).

Section 5 in Sloane’s paper consists of a list of open problems, which the reader may investigate, one of which asks whether there are nonisomorphic Young graphs with isomorphic underlying directed graphs. Regarding this question, our program finds that for g ≤ 336, there are no pairs of nonisomorphic Young graphs with isomorphic underlying directed graphs; the program could not proceed past this point. Holt also lists a number of open problems, in both algebraic and graphical lines. A particularly intriguing issue concerns a kind of graph interrelation: let us say the Young graph Y_{2} is a Holt transform of the graph Y_{1} if there is a one-to-one function ϕ : (a, b) ↦ [a, b] from the edges of Y_{1} to the nodes of Y_{2} such that if the edge (a, b) leads into a node N in Y_{1}, and the edge (c, d) leads out of it, then the node [a, b] directly succeeds the node [c, d] in Y_{2} – the graphs Y (14, 3) (Figure 3) and Y (3, 2) (Figure 4 for k = 2 and b = 1) are an example of such a pair. While this defines a function that most meaningfully pertains only to certain types of graphs,^{8} within that subset of graphs, considered as a map between equivalence classes, rather than the graphs themselves, it often results not only in pairs, as Holt [5] most directly discussed, but sequences of transforms; for example, the class of Y (3, 2) transforms to the class of Y (14, 3), which transforms to the class of Y (44, 13), which transforms to the class of Y (30, 11), which transforms to the class of Y (81, 32). Several questions naturally arise about these sequences, as to their possible lengths, their prevalence, and so on; Holt [5] also demonstrates connections between such graphs and palintiple derivation.

Examination of data also suggests the following line of study: given an equivalence class X of Young graphs, let Freq_{X}(x) be the number of Y (g, k) ∈ X with g ≤ x. The study of these functions may shed light on the characteristics of different equivalence classes. For example, their relative growth rates carry information about the distribution of classes amongst each other. By Theorem 14, if X is the set of 1089 graphs, then Freq_{X}(x) grows roughly as x ln x. The growth rate for the set of K_{m} graphs is presently unknown, although Corollary 32 reduces it to the problem of computing the number of pairs (g, k) with g ≤ x and ⌊gcd(g − k, k^{2} − 1)/(k + 1)⌋ = m − 1, and they have some resemblance to functions of the form x(ln x)^{α(m)}. Some graphs pertaining to this issue are included in the URL mentioned at the start of Section 6.1.

This paper is largely devoted to characterizing a few specific equivalence classes; infinitely more remain, although it is possible that they fall into categories like the K_{m} of complete graphs, where technically different equivalence classes follow a similar pattern. The partition of the set of pairs (g, k) into equivalence classes may well be the central utility of Young’s graphical approach, as it is difficult to meaningfully classify reverse multiples using only algebraic methods. Further work may be done characterizing specific equivalence classes, for example those featured in Section 6.1. The graphs in the Z_{n} present themselves as a natural next step, given the frequency of their occurrence, especially for small values of n, and the results of Section 5. While it would be ideal to characterize all equivalence classes, this is likely a rather difficult task given present methods. However, it might further the study of equivalence classes to study of the graphs H(g, k), in addition to the graphs Y (g, k) that are the focus of this paper. It should be easier to study H graphs, as their generation does not involve the additional, potentially complicating step of removing all nodes that do not precede pivot nodes.

8For example, applied to a graph in which many edges enter and leave a single node, such as a member of K_{m}, it results in a graph that cannot be reliably traced back to the original graph, as this would require a many edges between different nodes to collapse to a single node.

Since Young graph isomorphism is a stronger condition than isomorphism of the underlying directed graphs, and since the set of directed graphs that may occur as the underlying directed graphs of Young graphs is a proper subset of the set of all directed graphs, Young graph isomorphism should be an easier condition to test than normal directed graph isomorphism; indeed, Theorem 29 demonstrates this concretely. This raises the question of identifying the most efficient test for Young graph isomorphism. Answering this question could significantly speed the computations involved in testing isomorphism, as our current program for this purpose is rather slow. The program, given substantial time, was unable to decide whether Y (173, 54) and Y (337, 54) are isomorphic, whether Y (458, 431) and Y (459, 436) are isomorphic, and whether Y (471, 45) and Y (159, 45) are isomorphic; these might be good cases on which to attempt new methods.

6.1 Conjectures

A program in Java was used to generate all graphs with g ≤ 336 and to sort them into the equivalence classes determined by isomorphism. These programs and some data on Young

graphs may be found at https://sites.google.com/site/younggraphs/home; also on this

site may be found a visualization of the curious absence of reverse multiples where k ≈ g, which could be an interesting issue to investigate. From the examination of these graphs and their isomorphism classes, we conjecture the following.

Conjecture 38. For all n ≥ 0, the Young graphs Y (2(n + 2)(n + 3) − 1, 2(n + 2)^{2} − 1), Y (23 + 20n, 13 + 12n), Y (23 + 15n, 17 + 10n), Y (26 + 12n, 10 + 4n), and Y (11 + 6n, 7 + 3n) are all isomorphic to Y (11, 7).

Conjecture 39. For all n ≥ 3, Y (n^{2} − 1, n^{2} − n − 1) ≅ Y (8, 5).

Conjecture 40. For all t ≥ 2 and n ≥ 2, Y ((n^{2} + n)t + n, n^{2}t + n − 1) ≅ Y (14, 3).

Conjecture 41. For all n ≥ 2, Y (17 + 30n, 14 + 25n) ≅ Y (36, 10).

Grimm and Ballew found an algorithm for generating three-digit reverse multiples, which goes as follows: take d_{1}, d_{2} ∈ ℤ^{+} such that gcd(d_{1}, d_{2}) = 1, and then take some m ∈ ℤ such that d_{2}^{2} − d_{1}^{2} ≡ 0 (mod (m − 1)), m ≥ d_{2} + 1, m > d_{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_{2}N = 1. Then (d_{2}t + kM, d_{1}(m + 1)t + kN, md_{2}t + mkM + d_{1})_{g} is a (g, m) reverse multiple for g = (m^{2} − 1)t − mNd_{1} + d_{2}M(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 42.

Conjecture 42. 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) ≅ Y (g_{2}, m).

Conjecture 43. Let Classes(x) denote the number of equivalence classes that occur in all Y (g, k) for g ≤ x. Classes(x) grows roughly proportionately to x^{2}.

Regarding this conjecture, we find that the r-value for the set {(x, Classes(x)^{1/2}) | x ≤ 336} is around 0.9996. However, 336 seems to be a rather low upper bound for this type of problem: for example, the functions Freq_{K_{m}}(x), for x ≤ 400 are well-approximated by functions of the form c · x ln x, but for x ≤ 10^{5} it becomes apparent that such an approximation fails. Conjecture 43 is thus made rather hesitantly.

7 Acknowledgments

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.

References

[1] Martin Gardner. Mathematical Magic Show. Mathematical Association of America, 1990.

[2] C. A. Grimm and D. W. Ballew. Reversible multiples. J. Recreational Math., 8 (1975–6), 89–91.

[3] Dan Hoey. Untitled online article. https://oeis.org/A008919/a008919.txt, accessed April 10 2015.

[4] Benjamin V. Holt. Some general results and open questions on palintiple numbers. INTEGERS: Elect. J. Combin. Numb. Theory, 14 (2014), Paper A42. Available at

    http://www.integers-ejcnt.org/vol14.html.

[5] Benjamin V. Holt. Derived palintiple families and their palinomials. Preprint, 2015,

    available at http://arxiv.org/abs/1412.0231.

[6] Benjamin V. Holt. Some thoughts on determining symmetric palintiples. Preprint,

    2015, available at http://arxiv.org/abs/1410.2356.

[7] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Available at

    http://oeis.org.

[8] T. J. Kaczynski. Note on a problem of Alan Sutcliffe. Math. Mag., 41 (1968), 84–86.

[9] Leonard F. Klosinski and Dennis C. Smolarski. On the reversing of digits. Math. Mag., 42 (1969), 208–210.

[10] Lara Pudwell. Digit reversal without apology. Math. Mag., 80 (2007), 129–132.

[11] N. J. A. Sloane. 2178 and all that. Fibonacci Quart., 52 (2014), 99–120.

[12] Alan Sutcliffe. Integers that are multiplied when their digits are reversed. Math. Mag., 39 (1966), 282–287.

[13] Roger Webster and Gareth Williams. On the trail of reverse divisors: 1089 and all that follow. Math. Spectrum, 45 (3) (2013), 96.

[14] David Wells. The Penguin Dictionary of Curious and Interesting Numbers. Penguin, revised edition, 1997.

[15] Anne Ludington Young. k-reverse multiples. Fibonacci Quart., 30 (1992), 166–174.

[16] Anne Ludington Young. Trees for k-reverse multiples. Fibonacci Quart., 30 (1992), 126–132.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 05C20. Keywords: Young graph, reverse multiple, palintiple, radix representation.

(Concerned with sequences \underline{A001232}, \underline{A008918}, \underline{A008919}, \underline{A031877}, \underline{A169824}.)

Received April 10 2015; revised version received August 16 2015; August 20 2015. Published in Journal of Integer Sequences, August 21 2015.

Return to Journal of Integer Sequences home page.