# Generating \(m\)-[PERSON] Gray Codes and Related Algorithms  
[PERSON]  
1 Faculty of Mathematics and Informatics, St. Cyril and St. Methodius University of Veliko Tarnovo, 5000 Veliko Tarnovo, Bulgaria; [EMAIL_ADDRESS]  
[PERSON]  
2 Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 5000 Veliko Tarnovo, Bulgaria; [EMAIL_ADDRESS] (I.B. ); [EMAIL_ADDRESS] (M.P.-G.)  
[PERSON]  
1 Faculty of Mathematics and Informatics, St. Cyril and St. Methodius University of Veliko Tarnovo, 5000 Veliko Tarnovo, Bulgaria; [EMAIL_ADDRESS]  
[PERSON]  
2 Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 5000 Veliko Tarnovo, Bulgaria; [EMAIL_ADDRESS] (I.B. ); [EMAIL_ADDRESS] (M.P.-G.)  
Footnote 1: email: {[EMAIL_ADDRESS]}  
Footnote 2: email: {[EMAIL_ADDRESS]}  
Footnote 3: email: {[EMAIL_ADDRESS]}  
Footnote 4: email: {[EMAIL_ADDRESS]}  
Footnote 5: email: {[EMAIL_ADDRESS]}  
Footnote 6: email: {[EMAIL_ADDRESS]}  
Footnote 7: email: {[EMAIL_ADDRESS]}  
==WARNING: Truncated because of repetitions==
numeral system, where \(a_{g}=a_{1}m^{n-1}+a_{2}m^{n-2}+\cdots+a_{n}\). It is easy to see that \(a_{1}=g_{1}\). We give the relation between \(g\) and \(a_{g}\) in the following theorem. **Theorem 2**. : _Let \(g=(g_{1},\ldots,g_{n})\in G_{m}(n)\) be a codeword in the reflected Gray code and \(a_{g}\) be its sequence number. If \(a_{g}=a_{1}m^{n-1}+a_{2}m^{n-2}+\cdots+a_{n}\), \(0\leq a_{i}\leq m-1\), \(i=1,\ldots,n\), then_  
\[a_{i}= \begin{cases}g_{i},\text{ if }S_{i}\text{ is even},\\ m-1-g_{i},\text{ if }S_{i}\text{ is odd},\end{cases} \] (2)  
_where \(S_{1}=0\) and \(S_{i}=\sum_{j=1}^{i-1}g_{j}\) for \(2\leq i\leq n\)._  
**Proof. ** Again, we use induction on \(n\). If \(n=1\), \(G_{m}(1)=(0,1,\ldots,m-1)^{T}\), and the corresponding numbers are \(0,1,\ldots,m-1\), so \(a_{g}=g_{1}\). Assume that the statement is true for \(G_{m}(n-1)\), and take \(g=(g_{1},\ldots,g_{n})\in G_{m}(n)\). If \(g_{1}=0\), then \(a_{g}\) coincides with the number of the codeword \((g_{2},\ldots,g_{n})\in G_{m}(n-1)\). Since in this case \(S_{i}=\sum_{j=1}^{i-1}g_{j}=\sum_{j=2}^{i-1}g_{j}\), the Formula (2) holds for the codeword \(g\). In the general case, \(a_{g}=g_{1}m^{n-1}+a_{g}^{\prime}\), where \(a_{g}^{\prime}\) is the rank of \(g^{\prime}=(g_{2},\ldots,g_{n})\in G_{m}(n-1)\) if \(g_{1}\) is even, and \(g^{\prime}=(g_{2},\ldots,g_{n})\in G_{m}^{*}(n-1)\) if \(g_{1}\) is odd. If \(S_{i}^{\prime}=S_{i}-g_{1}=\sum_{j=2}^{i-1}g_{j}\), then \(S_{i}\equiv S_{i}^{\prime}\pmod{2}\) if \(g_{1}\) is even, and \(S_{i}\equiv S_{i}^{\prime}+1\pmod{2}\) if \(g_{1}\) is odd. Hence, if \(g_{1}\) is even, then
+++  
\[a_{i}= \begin{cases}g_{i},\text{ if }S_{i}\text{ is even},\\ m-1-g_{i},\text{ if }S_{i}\text{ is odd},\end{cases} .\]  
If \(g_{1}\) is odd, then \(g^{\prime}=(g_{2},\dots,g_{n})\in G_{m}^{*}(n-1)\) and in this case the codewords of the corresponding Gray code are taken in reverse order. Hence, the number of \(g^{\prime}\) if this code is \(m^{n-1}-1-a_{g^{\prime}}\), where \(a_{g^{\prime}}\) is the number of \(g^{\prime}\in G_{m}(n-1)\). Since the ciphers of this number for radix \(m\) are \(m-1-a_{2},m-1-a_{3},\dots,m-1-a_{n}\), we have the same formula for \(a_{i}\), \(i=1,\dots,n\). **Corollary 1**. : _Let \(a=a_{1}m^{n-1}+a_{2}m^{n-2}+\dots+a_{n}\), \(0\leq a_{i}\leq m-1\), \(i=1,\dots,n\), be a nonnegative integer, \(0\leq a\leq m^{n}-1\), and \(g=(g_{1},g_{2},\dots,g_{n})\) be the codeword in \(G_{m}(n)\) in the \(a\)-th row according to Definition 1. Then_  
\[g_{i}= \begin{cases}a_{i},\text{ if }S_{i}\text{ is even},\\ m-1-a_{i},\text{ if }S_{i}\text{ is odd}.\end{cases}  \tag{3}\]  
_where \(S_{1}=0\) and \(S_{i}=\sum_{j=1}^{i-1}g_{j}\) for \(2\leq i\leq n\)._  
Tables 1 and 2 show the ranking of the codewords in \(G_{3}(3)\) and \(G_{4}(2)\), respectively. The implementation of the Formulas (2) and (3) is given in Algorithm 7. Additionally, we have incorporated the decimal representation of the rank (sequence number) into these algorithms.