On Radius 1 Nontrivial Reversible and Number-Conserving Cellular Automata

Abstract

Reversibiliity and number-conservation are widely studied physics-like constraints for cellular automata (CA). Although both seem to be ‘natural’ constraints for a CA, it was conjectured that one-dimensional reversible and number-conserving CA (RNCCA) only has a limited computing ability. Particularly in the case of radius 1/2 (2-neighbor), it was shown that the class of RNCCA is equal to a trivial class of CA, so called shift-identity product cellular automata (SIPCA). But recently it was also shown that a RNCCA of neighborhood size four is computation-universal. In this paper, we list radius 1 (3-neighbor) RNCCAs up to 4-state by exhaustive search. In contrast to the radius 1/2 case, there are three new types of nontrivial RNCCA rules in the case of 4-state. We also show that it is possible to compose new nontrivial RNCCAs by modifying a SIPCA even when the state number is larger than four.

1 Introduction

A reversible cellular automaton (RCA) is a cellular automaton (CA) whose global function is injective. A number-conserving cellular automaton (NCCA) is a cellular automaton whose states are integers and whose transition function keeps the sum of all cells constant throughout its evolution. Both can be seen as some kind of modeling of the physical conservation laws of mass or energy. Although both constraints seem to be ‘natural’ constraints for a cellular automaton [6], it was conjectured that one-dimensional reversible and number-conserving cellular automata (RNCCA) only have a limited computing ability. Particularly in the case of radius 1/2 (2-neighbor), it was shown that RNCCAs are characterized by shift-identity product cellular automata (SIPCA) [5]. But recently it was also shown that a 4-neighbor RNCCA is computation-universal [7]. In this paper we explore the whole list of radius 1 (3-neighbor) RNCCAs up to 4-state by exhaustive search. In contrast to the radius 1 / 2 case, there are three new types of nontrivial RNCCAs in the case of 4-state. We also show that one of the types is useful because it is possible to compose new associated nontrivial RNCCAs of this type by modifying a trivial RNCCA when the number of states is larger than four.

2 Preliminaries

Definition 1

A n-state deterministic one-dimensional cellular automaton is defined by $A=(\mathbb {Z}, N, Q, f)$, where $\mathbb {Z}$ is the set of all integers, the neighborhood $N=\{n_1,\ldots ,n_k\}$ is a finite subset of $\mathbb {Z}$, $Q=[\![0,\ldots , n-1]\!]$ is the set of states of each cell, $f : Q^k\rightarrow Q$ is a mapping called the local transition function.

A configuration over Q is a mapping $\alpha :\mathbb {Z}\rightarrow Q$. Then $\mathrm{Conf}(Q) = \{\alpha \mid \alpha :\mathbb {Z}\rightarrow Q\}$ is the set of all configurations over Q. The global function of A is $F:\mathrm{Conf}(Q) \rightarrow \mathrm{Conf}(Q)$ defined as $F(\alpha )(i)=f(\alpha (i+n_1),\ldots ,\alpha (i+n_k)) \text{ for } \text{ all } \alpha \in \mathrm{Conf}(Q), \ i\in \mathbb {Z}.$

We call the value $r=(\max _{1\le i\le k}n_i-\min _{1\le i\le k}n_i)/2$ the radius of A. A neighborhood $\{-1,0,1\}$ corresponds to radius 1, while a neighborhood $\{0,1\}$ corresponds to radius 1 / 2. In these cases we replace N by r in the notation of cellular automata. We employ the Wolfram numbering [9] W(f) to represent the local function f: $W(f)=\sum f(x_1,\ldots ,x_{2r+1}) n^{ n^{2r} x_1 +n^{2r-1} x_2+\ldots +n^0 x_{2r+1} }$ where the sum is applied on $(x_1,\ldots ,x_{2r+1})\in Q^{2r+1}$. Note that the Wolfram numbering of a n-state CA, expressed in radix n form is the concatenation of the values of its local transition function.

In the sequel, we denote any finite configuration with the finite sequence of its states: $[x_{0}, x_1, x_2,\ldots , x_m]$ where $x_i \in Q$.

Definition 2

A CA A is reversible iff its global function F is injective. A is said to be number-conserving iff $\forall c \in \mathrm{Conf}_F(Q), \sum _{i\in \mathbb {Z}} \{F(c)(i)-c(i)\}=0$ where $\mathrm{Conf}_F(Q)$ denotes the set of all finite configurations (i.e. configurations in which the number of nonzero cells is finite.)

Definition 2 is equivalent to the general definition in the infinite case [3].

Definition 3

For a state $q\in Q\setminus \{0\}$ of $A = (\mathbb {Z}, 1, Q, f)$, we call q a stable state if $f(0,q,0)=q,f(q,0,0)=0,f(0,0,q)=0$, q is a right (resp. left) propagating state, if $f(0,q,0)\!=\!0,f(q,0,0)\!=\!q,f(0,0,q)\!=\!0$ (resp. $f(0,q,0)\!=\!0,f(q,0,0)\!=\!0,f(0,0,q)\!=\!q$). For a state $q\in Q\setminus \{0\}$ of $A = (\mathbb {Z}, 1/2, Q, g)$, we call q a stable state if $g(q,0)\!=\!q,g(0,q)\!=\!0$, q is a left propagating state, if $g(q,0)\!=\!0,g(0,q)\!=\!q$. We denote the set of stable, right propagating, left propagating states by $Q_{\downarrow },Q_{\searrow }$, and $Q_{\swarrow }$ ($\subset Q$) respectively.

We recall a necessary and sufficient condition for radius 1 CAs to be number-conserving, as a special case of results from [2].

Proposition 1

A deterministic one-dimensional CA $A = (\mathbb {Z}, 1, Q, f)$ is number-conserving iff there exists a function $\varphi :Q^2 \rightarrow \mathbb {Z}$ such that

$$f(\ell ,c,r) = c - \varphi (\ell , c) + \varphi (c, r) \text{ for } \text{ all } c, \ell , r \in Q.$$

The function $\varphi$ represents the movement of numbers between two neighboring cells. We call this function $\varphi$ the flow function.

3 Radius 1 RNCCAs and Their Composition Methods

In this section we denote each RNCCA with an expression of the form $q\!-\!n\!-\!i$ where q is the size of its neighborhood, n the number of states, and $i\quad (=1,2,\ldots )$ is an index which indicates the local rules arranged in the ascending order of the Wolfram numbering ($W(f_i) < W(f_{i+1})$). See Table 1 and Appendix.

Table 1 Flow function values of radius 1 (3-neighbor) 4-state RNCCAs

As far as the radius 1 / 2 case, RNCCAs are characterized by shift-identity product cellular automata (SIPCA) [5]. The possible function by SIPCA signals is only a crossing of a stable state and a left propagating state. Thus a typical behavior is trivial and its time evolution is similar to the one depicted in Fig. 1 3-4-4 (Type I). Its state set Q is $Q_{\downarrow }\cup Q_{\swarrow }\cup Q_{\swarrow \downarrow }$ where $Q_{\swarrow \downarrow }=\{a+b\quad |\quad a\in Q_{\downarrow }, b\in Q_{\swarrow } \}$. An RNCCA whose state number is a prime, is only a left shift or the identity [5], thus $2\!-\!p\!-\!1$ is a left shift and $2\!-\!p\!-\!2$ is the identity, when p is a prime number. Appendix 1 proposes the cases up to 10-state.

Schranko and Oliveira [8] introduced a way of constructing RNCCA rules with a large neighborhood by the composition of radius 1 / 2 RNCCA rules. Their scheme in the cases ranging from radius 1 / 2 to 1 is as follows:

Proposition 2

 [8] Given two radius 1 / 2 RNCCAs: $A_1 = (\mathbb {Z}, 1/2, Q, g_1)$ and $A_2 = (\mathbb {Z}, 1/2, Q, g_2)$, $A = (\mathbb {Z}, 1, Q, f)$ is a radius 1 RNCCA, where $f(\ell ,c,r) \equiv g_1 \circ g_2(\ell ,c,r)=g_1(g_2(\ell ,c),g_2(c,r))$ for any $\ell ,c,r \in Q$.

This procedure does not produce any complex behavior. If $a \in Q$ is a left propagating (resp. a stable) state of both $A_1$ and $A_2$ then a is a left propagating (resp. a right propagating) state of A. Otherwise a is a stable state of A. So they also conjectured that every q-state n-neighbor RNCCA rule is a composition of q-state radius 1 / 2 RNCCA rules. This is not true because there is a counter-example in [5] and we show it even in the case of radius 1 and 4-state. By exhaustive search, there are 21 RNCCAs with radius 1 and 4-state (among 89588 NCCAs). Appendix 2 shows the result. Although enumeration of RCAs is hard even in the 4-state case, enumeration of NCCAs is easier because it is possible to reduce the search domain by Proposition 1 (see also [2]). So we first enumerated NCCAs and checked their reversibility by [1].

Fig. 1

Time space diagrams of 4-state RNCCAs of each type

Their flow function values are shown in Table 1. They are classified into four types (see Fig. 1). 3-1, 4, 5, 8, 9, 16, 18, 20, 21 (type I) are composed by the above method. Type II rules: 3-2,6,17,19 have one left (or right) propagating state and one stable state and their collision shifts the stable state to the right (or to the left). Each type II rule can be induced by a related type I rule: $3\!-\!4\!-\!4 \rightarrow 3\!-\!4\!-\!2, 3\!-\!4\!-\!8 \rightarrow 3\!-\!4\!-\!6, 3\!-\!4\!-\!18 \rightarrow 3\!-\!4\!-\!17, 3\!-\!4\!-\!20 \rightarrow 3\!-\!4\!-\!19$ respectively by replacing two flow functions values. Type III rules: $3\!-\!4\!-\!3,7,11,13$ have two left (or right) propagating states and one stable state. Their collision is performed by swapping two signals (i.e. it does not make the sum of two signal values). Type IV rules: 3-4-10, 12, 14, 15 have no propagating state.

Next, we show that a type II RNCCA can be induced by a type I RNCCA even when the state number is larger than four.

Proposition 3

Let $A = (\mathbb {Z}, 1, Q, f)$. Suppose A is a RNCCA composed by Proposition 2 and $s\in Q$ is a stable state and $r\in Q$ is a right (resp. left) propagating state, then there is an injective NCCA which has an associated type II rule.

Proof

We only show the result when r is a right propagating state. The proof in the case of a left propagating state is similar.

Let $r,r',r'' \in Q_{\searrow } \cup \{0\}$ and $s,s' \in Q_{\downarrow } \cup \{0\}$. Choose two states $r_0$ and $s_0$ such that $r_0 \in Q_{\searrow }$ and $s_0 \in Q_{\downarrow }$. The CA A must attain the transition: $[r+s,0,r_0+s_0,r'+s'] {\mathop {\rightarrow }\limits ^{f}} [r''+s,r,s_0,r_0+s']$ since r and $r_0$ are right-propagating states and the flow function $\varphi$ of f should have the value: $\varphi (0, r_0+s_0)=0$. If we modify the value of the flow function $\varphi (0, r_0+s_0)$ to $s_0$, the transition becomes $[r+s,0,r_0+s_0,r'+s'] {\mathop {\rightarrow }\limits ^{f}} [r''+s,r+s_0,0,r_0+s']$. But the transition to the configurations already exists, i.e., $[r+s,s_0,r_0,r'+s'] {\mathop {\rightarrow }\limits ^{f}} [r''+s,r+s_0,0,r_0+s']$. These transitions have to be changed to the transition $[r+s,s_0,r_0,r'+s'] {\mathop {\rightarrow }\limits ^{f}} [r''+s,r,s_0,r_0+s']$. This can be done by changing the flow function value of $\varphi (s_0, r_0)=0$ to $-s_0$. This modification swaps the configurations $[r''+s,r+s_0,0,r_0+s']$ and $[r''+s,r,s_0,r_0+s']$. Even if a configuration contains the sequence more than once (maybe infinitely often), the modification only affects every finite length sequence, keeping thus injectivity because the number of configurations for which preimages are changed is equal. The modification also keeps the number-conservation since it is applied to the values of the flow function. $\quad \square$

Example 1

A type I 6-state radius 1 RNCCA $A_6$ can be combined from two radius 1 / 2 RNCCAs 2-6-4 and 2-6-6 (in Appendix 1). 2-6-6 is the identity and 2-6-4 has a stable state 1 and two left propagating state 2 and 4. Thus $A_6$ has $Q_{\searrow }=\{1\}$, $Q_{\downarrow }=\{2,4\}$, and $Q_{\swarrow }=\varnothing$. Its flow function $\varphi (x, y)$ has the following values:

$\begin{array}{lrlrlrlrlrlrlrlr} (5, 5) &{} -1, &{} (5, 4) &{} -1, &{} (5, 3) &{} -1, &{} (5, 2) &{} -1, &{} (5, 1) &{} -1, &{} (5, 0) &{} -1, &{} (4, 5) &{} 0, &{} (4, 4) &{} 0, \\ (4, 3) &{} 0, &{} (4, 2) &{} 0, &{} (4, 1) &{} -4, &{} (4, 0) &{} 0, &{} (3, 5) &{} -1, &{} (3, 4) &{} -1, &{} (3, 3) &{} -1, &{} (3, 2) &{} -1, \\ (3, 1) &{} -1, &{} (3, 0) &{} -1, &{} (2, 5) &{} 0, &{} (2, 4) &{} 0, &{} (2, 3) &{} 0, &{} (2, 2) &{} 0, &{} (2, 1) &{} 0, &{} (2, 0) &{} 0, \\ (1, 5) &{} -1, &{} (1, 4) &{} -1, &{} (1, 3) &{} -1, &{} (1, 2) &{} -1, &{} (1, 1) &{} -1, &{} (1, 0) &{} -1, &{} (0, 5) &{} 4, &{} (0, 4) &{} 0, \\ (0, 3) &{} 0, &{} (0, 2) &{} 0, &{} (0, 1) &{} 0, &{} (0, 0) &{} 0. \\ \end{array}$

Replacing two values, $\varphi (0, 3) = 2, \varphi (2, 1) = -2$ gives a 6-state type II RNCCA. Moreover replacing two values, $\varphi (0, 5) = 4, \varphi (4, 1) = -4$ gives another 6-state type II RNCCA.

4 Conclusion

In this paper, we present the exhaustive search result of radius 1 RNCCAs up to four states. There are three types of nontrivial RNCCA rules in the case of four states. Although our result deny Schranko and Oliveira’s conjecture [8], it remains still open whether the complexity of radius 1 RNCCA is sufficient to provide a universal CA or not. Collision of two propagating (or stable) signals cannot change their states as far as this method is employed. To obtain a more complex behavior, another way of collisions seems to be required.

Appendix: The List of RNCCAs

Each rule is described in Wolfram numbering and its suffix is the radix of the number. The sets followed by $\swarrow ,\downarrow$ and $\searrow$ denote left propagating, stable and right propagating state sets, respectively.

1. Radius 1 / 2

$\begin{array}{ll} n=4: \\ 2\text {-}4\text {-}1: 3210321032103210_4 \swarrow \{1,2,3\} \\ 2\text {-}4\text {-}2: 3232323210101010_4 \swarrow \{1\}\downarrow (2\} \\ 2\text {-}4\text {-}3: 3311220033112200_4 \swarrow \{2)\downarrow \{1\} \\ 2\text {-}4\text {-}4: 3333222211110000_4 \downarrow \{1,2,3\}\\ \end{array}$

$\begin{array}{ll} n=6:\\ 2\text {-}6\text {-}1: 543210543210543210543210543210543210_6 \swarrow \{1,2,3,4,5\}\\ 2\text {-}6\text {-}2: 543543543543543543210210210210210210_6 \swarrow \{1,2\}\downarrow \{3\}\\ 2\text {-}6\text {-}3: 545454545454323232323232101010101010_6 \swarrow \{1\}\downarrow \{2,4\}\\ 2\text {-}6\text {-}4: 553311442200553311442200553311442200_6 \swarrow \{2,4\}\downarrow \{1\}\\ 2\text {-}6\text {-}5: 555222444111333000555222444111333000_6 \swarrow \{3\}\downarrow \{1,2\}\\ 2\text {-}6\text {-}6: 555555444444333333222222111111000000_6 \downarrow \{1,2,3,4,5\}\\ \end{array}$

$\begin{array}{ll} n=8: \\ 2\text {-}8\text {-}1: &{} \mathtt{7654321076543210765432107654321076543210765432107654321076543210_8} \swarrow \{1,2,3,4,5,6,7\}\\ 2\text {-}8\text {-}2: &{} \mathtt{7654765476547654765476547654765432103210321032103210321032103210_8} \swarrow \{1,2,3\}\downarrow \{4\}\\ 2\text {-}8\text {-}3: &{} \mathtt{7676323276763232545410105454101076763232767632325454101054541010_8} \swarrow \{1,4,5\}\downarrow \{2\}\\ 2\text {-}8\text {-}4: &{} \mathtt{7676767676767676545454545454545432323232323232321010101010101010_8} \swarrow \{1\}\downarrow \{2,4,6\}\\ 2\text {-}8\text {-}5: &{} \mathtt{7755331166442200775533116644220077553311664422007755331166442200_8} \swarrow \{2,4,6\}\downarrow \{1\}\\ 2\text {-}8\text {-}6: &{} \mathtt{7755775566446644775577556644664433113311220022003311331122002200_8} \swarrow \{2\}\downarrow \{1,4,5\}\\ 2\text {-}8\text {-}7: &{} \mathtt{7777333366662222555511114444000077773333666622225555111144440000_8} \swarrow \{4\}\downarrow \{1,2,3\}\\ 2\text {-}8\text {-}8: &{} \mathtt{7777777766666666555555554444444433333333222222221111111100000000_8} \downarrow \{1,2,3,4,5,6,7\}\\ \end{array}$

$\begin{array}{ll} n=9: \\ 2\text {-}9\text {-}1: &{} \mathtt{876543210876543210876543210876543210876543210876543210876543210876543210876543210_9} \\ &{} \swarrow \{1,2,3,4,5,6,7,8\}\\ 2\text {-}9\text {-}2: &{} \mathtt{876876876876876876876876876543543543543543543543543543210210210210210210210210210_9} \\ &{} \swarrow \{1,2\}\downarrow \{3,6\}\\ 2\text {-}9\text {-}3: &{} \mathtt{888555222777444111666333000888555222777444111666333000888555222777444111666333000_9} \\ &{} \swarrow \{3,6\}\downarrow \{1,2\}\\ 2\text {-}9\text {-}4: &{} \mathtt{888888888777777777666666666555555555444444444333333333222222222111111111000000000_9} \\ &{} \downarrow \{1,2,3,4,5,6,7,8\}\\ \end{array}$

$\begin{array}{ll} n=10: \\ 2\text {-}10\text {-}1: &{} \mathtt{9876543210987654321098765432109876543210987654321098765432109876543210987654321098765}\\ &{} 432109876543210_{10}, \swarrow \{1,2,3,4,5,6,7,8,9\}\\ 2\text {-}10\text {-}2: &{} \mathtt{9876598765987659876598765987659876598765987659876543210432104321043210432104321043210} \\ &{} 432104321043210_{10}, \swarrow \{1,2,3,4\}\downarrow \{5\}\\ 2\text {-}10\text {-}3: &{} \mathtt{9898989898989898989876767676767676767676545454545454545454543232323232323232323210101} \\ &{} 010101010101010_{10}, \swarrow \{1\}\downarrow \{2,4,6,8\}\\ 2\text {-}10\text {-}4: &{} \mathtt{9977553311886644220099775533118866442200997755331188664422009977553311886644220099775} \\ &{} 533118866442200_{10}, \swarrow \{2,4,6,8\}\downarrow \{1\}\\ 2\text {-}10\text {-}5: &{} \mathtt{9999944444888883333377777222226666611111555550000099999444448888833333777772222266666} \\ &{} 111115555500000_{10}, \swarrow \{5\}\downarrow \{1,2,3,4\}\\ 2\text {-}10\text {-}6: &{} \mathtt{9999999999888888888877777777776666666666555555555544444444443333333333222222222211111} \\ &{} 111110000000000_{10}, \downarrow \{1,2,3,4,5,6,7,8,9\}\\ \end{array}$

2. Radius 1

$\begin{array}{llll} n=2: &{}\qquad n=3:\\ 3\text {-}2\text {-}1: \mathtt{10101010_2} \swarrow \{1\} &{}\qquad 3\text {-}3\text {-}1: &{} \mathtt{210210210210210210210210210_3} \swarrow \{1,2\}\\ 3\text {-}2\text {-}2: \mathtt{11001100_2} \downarrow \{1\} &{} \qquad 3\text {-}3\text {-}2: &{} \mathtt{222111000222111000222111000_3} \downarrow \{1,2\}\\ 3\text {-}2\text {-}3: \mathtt{11110000_2} \searrow \{1\} &{} \qquad 3\text {-}3\text {-}3: &{} \mathtt{222222222111111111000000000_3} \searrow \{1,2\}\\ \end{array}$

$\begin{array}{ll} n=4: \\ 3\text {-}4\text {-}1: &{} \mathtt{3210321032103210321032103210321032103210321032103210321032103210_4} \swarrow \{1,2,3\}\\ 3\text {-}4\text {-}2: &{} \mathtt{3230323212103232323032321210101032301010121010103230323212101010_4} \swarrow \{1\}\downarrow \{2\}\\ 3\text {-}4\text {-}3: &{} \mathtt{3232321210103010323232123232301032323212101030101010321210103010_4} \swarrow \{1,3\}\downarrow \{2\}\\ 3\text {-}4\text {-}4: &{} \mathtt{3232323210101010323232321010101032323232101010103232323210101010_4} \swarrow \{1\}\downarrow \{2\}\\ 3\text {-}4\text {-}5: &{} \mathtt{3232323232323232323232323232323210101010101010101010101010101010_4} \swarrow \{1\}\searrow \{2\}\\ \end{array}$

$\begin{array}{ll} 3\text {-}4\text {-}6: &{} \mathtt{3310221033113311331022102200220033102210331122003310221033112200_4} \swarrow \{2\}\downarrow \{1\}\\ 3\text {-}4\text {-}7: &{} \mathtt{3311220032113200331122003211320033113311321132002200220032113200_4} \swarrow \{2,3\}\downarrow \{1\}\\ 3\text {-}4\text {-}8: &{} \mathtt{3311220033112200331122003311220033112200331122003311220033112200_4} \swarrow \{2\}\downarrow \{1\}\\ 3\text {-}4\text {-}9: &{} \mathtt{3311331133113311220022002200220033113311331133112200220022002200_4} \swarrow \{2\}\searrow \{1\}\\ 3\text {-}4\text {-}10: &{} \mathtt{3331222213112222333122221311000033310000131100003331222213110000_4} \downarrow \{1,2\}\\ 3\text {-}4\text {-}11: &{} \mathtt{3331333313113333222022220200000033311111131111112220222202000000_4} \downarrow \{2\}\searrow \{1,3\}\\ 3\text {-}4\text {-}12: &{} \mathtt{3332223211111111333222320000000033322232111100003332223211110000_4} \downarrow \{1,2\}\\ 3\text {-}4\text {-}13: &{} \mathtt{3332223233333333333222322222222211100010111100001110001011110000_4} \downarrow \{1\}\searrow \{2,3\}\\ 3\text {-}4\text {-}14: &{} \mathtt{3333220211112000333322023333200033332202111120001111220211112000_4} \downarrow \{1,2\}\\ 3\text {-}4\text {-}15: &{} \mathtt{3333222210111000333322221011100033333333101110002222222210111000_4} \downarrow \{1,2\}\\ 3\text {-}4\text {-}16: &{} \mathtt{3333222211110000333322221111000033332222111100003333222211110000_4} \downarrow \{1,2,3\}\\ 3\text {-}4\text {-}17: &{} \mathtt{3333222232333222333322223233322211111111101110000000000010111000_4} \downarrow \{1\}\searrow \{2\}\\ 3\text {-}4\text {-}18: &{} \mathtt{3333222233332222333322223333222211110000111100001111000011110000_4} \downarrow \{1\}\searrow \{2\}\\ 3\text {-}4\text {-}19: &{} \mathtt{3333331311113111222222022222200033333313111131110000220200002000_4} \downarrow \{2\}\searrow \{1\}\\ 3\text {-}4\text {-}20: &{} \mathtt{3333333311111111222222220000000033333333111111112222222200000000_4} \downarrow \{2\}\searrow \{1\}\\ 3\text {-}4\text {-}21: &{} \mathtt{3333333333333333222222222222222211111111111111110000000000000000_4} \searrow \{1,2,3\}\\ \end{array}$

$\begin{array}{ll} n=5: \\ 3\text {-}5\text {-}1: &{} \mathtt{432104321043210432104321043210432104321043210432104321043210432104321043210432104321} \\ &{} \mathtt{04321043210432104321043210432104321043210_5} \\ 3\text {-}5\text {-}2: &{} \mathtt{444243333324202333330200044424333332420211111020004442411111242023333302000444243333} \\ &{} \mathtt{32420211111020004442411111242021111102000_5} \\ 3\text {-}5\text {-}3: &{} \mathtt{444443333322202111110200044444333332220211111020004444433333222023333302000444443333} \\ &{} \mathtt{32220211111020004444411111222021111102000_5} \\ 3\text {-}5\text {-}4: &{} \mathtt{444443333322222100111100044444333332222210011110004444433333222221001111000444444444} \\ &{} \mathtt{43333310011110003333322222222221001111000_5} \\ 3\text {-}5\text {-}5: &{} \mathtt{444443333322222110110100044444333332222211011010004444433333222221101101000444443333} \\ &{} \mathtt{33333311011010004444422222222221101101000_5} \\ 3\text {-}5\text {-}6: &{} \mathtt{444443330322222111113000044444333032222244444300004444433303222221111130000444443330} \\ &{} \mathtt{32222211111300001111133303222221111130000_5} \\ 3\text {-}5\text {-}7: &{} \mathtt{444443333321222201111000044444333332122220111100004444444444212222011110000333334444} \\ &{} \mathtt{42122220111100003333333333212222011110000_5} \\ 3\text {-}5\text {-}8: &{} \mathtt{444443333322222101111000044444333332222210111100004444433333222221011110000444444444} \\ &{} \mathtt{42222210111100003333333333222221011110000_5} \\ 3\text {-}5\text {-}9: &{} \mathtt{444443333122222113110000044444333312222211311222224444433331222221131100000444443333} \\ &{} \mathtt{10000011311000004444433331222221131100000_5} \\ 3\text {-}5\text {-}10: &{} \mathtt{444443313122222313110000044444331314444431311222224444433131222223131100000222223313} \\ &{} \mathtt{10000031311000004444433131222223131100000_5} \\ 3\text {-}5\text {-}11: &{} \mathtt{444413333322222141113333344441333332222214111000004444133333222221411100000444410000} \\ &{} \mathtt{02222214111000004444133333222221411100000_5} \\ 3\text {-}5\text {-}12: &{} \mathtt{444443313322222311110000044444331334444431111000004444433133222223111100000222223313} \\ &{} \mathtt{32222231111000004444433133222223111100000_5} \\ 3\text {-}5\text {-}13: &{} \mathtt{444443333321222211110000044444333332122221111000004444444444212222111100000333333333} \\ &{} \mathtt{32122221111000004444433333212222111100000_5} \\ 3\text {-}5\text {-}14: &{} \mathtt{444433334222232111111111144443333422223200000111114444333342222320000000000444433334} \\ &{} \mathtt{22223211111000004444333342222321111100000_5} \\ 3\text {-}5\text {-}15: &{} \mathtt{444443333222232111110000044444333322223211111111114444433332222320000000000444443333} \\ &{} \mathtt{22223211111000004444433332222321111100000_5} \\ 3\text {-}5\text {-}16: &{} \mathtt{444243333324222333330000044424333332422211111000004442411111242221111100000444243333} \\ &{} \mathtt{32422211111000004442433333242221111100000_5} \\ 3\text {-}5\text {-}17: &{} \mathtt{444433334322222111111111144443333432222200000000004444333343222221111100000444433334} \\ &{} \mathtt{32222211111000004444333343222221111100000_5} \\ 3\text {-}5\text {-}18: &{} \mathtt{444343343322222222220000044434334331111111111000004443433433222221111100000444343343} \\ &{} \mathtt{32222211111000004443433433222221111100000_5} \\ 3\text {-}5\text {-}19: &{} \mathtt{444443333322222111110000044444333332222211111000004444433333222221111100000444443333} \\ &{} \mathtt{32222211111000004444433333222221111100000_5} \\ 3\text {-}5\text {-}20: &{} \mathtt{444444444444444444444444433333333333333333333333332222222222222222222222222111111111} \\ &{} \mathtt{11111111111111110000000000000000000000000_5} \end{array}$