Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time

A Lucas word of order $p$ and length $n$ is a binary string of length $n$ that is not equal to $1^n$, avoids $p$ consecutive ones, and has neither a $1^{\mathrm{\ell }}$ prefix nor a $1^m$ suffix such that $\mathrm{\ell }+m\ge p$. In other words, a Lucas word is a binary string of length $n$ that is not equal to $1^n$ and avoids $p$ consecutive ones when the string is considered cyclically. As an example, the 11 Lucas words of order $p=3$ and length $n=4$ are

0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1100.

The number of Lucas words, also known as Lucas numbers, is an interesting topic in combinatorics due to its close relationship with the famous Fibonacci sequence. The sequence was first discovered by Edouard Lucas, who found such a sequence when investigating Fibonacci number patterns. For example, when $p=2$, the initial six terms of the enumeration of Lucas words are 1, 3, 4, 7, 11, 18. The Lucas numbers $L_{n,p}$ of order $p=2$ can be defined recursively as follows:

This recursive definition is analogous to the Fibonacci sequence, with the exception of different initial terms. Interestingly, when $p>2$, the number of Lucas words corresponds to multi-step Lucas numbers, which are similar to multi-step Fibonacci numbers but with different initial terms. For example, when $p=3$, the first six terms of the enumeration of Lucas words are 1, 3, 7, 11, 21, 39, and 71. These terms can be computed similarly to the famous tribonacci numbers with the initial terms $L_{1,3}=1$, $L_{2,3}=3$, and $L_{3,3}=7$, and the recurrence formula $L_{n,3}=L_{n-1,3}+L_{n-2,3}+L_{n-3,3}$. Similarly when $p=4$, the number of Lucas words can be computed recursively in the same manner as the tetranacci number but with different initial terms, and this property holds for all integers $n$ and $p$. For more information about multi-step Lucas numbers and multi-step Fibonacci sequences, see [12, 13, 24, 27]. The enumeration sequences for Lucas words can be accessed on the Online Encyclopedia of Integer Sequences for various values of $p$ [28].

The study of Lucas words and their variations has attracted significant attention from mathematicians [2, 9, 10, 19]. One intriguing variant that has attracted considerable interest is $q$-decreasing words, which are binary strings in which every maximal factor of the form $0^a{1}^b$ satisfies the condition where $a=0$ or $qa>b$ [3, 20]. Another interesting variant is the concept of Fibonacci words, which are binary strings of length $n$ that avoid $p$ consecutive ones. Interestingly, there exists a bijection between the set of Fibonacci words and the set of $q$-decreasing sequences [3]. Moreover, our algorithm for generating Lucas words relies on our algorithm for generating Fibonacci words. In a more general context, Lucas words can be considered as a special case of binary strings of length $n$ that avoid a specific factor, which finds numerous applications in cryptography and coding theory. For more applications of Lucas words and other relatives, see [11, 14, 17, 22, 26, 29, 30, 33].

One of the most important aspects of combinatorial generation is to list the instances of a combinatorial object so that consecutive instances differ by a specified closeness condition involving a constant amount of change. Lists of this type are called Gray codes. This terminology is due to the eponymous binary reflected Gray code (BRGC) by Frank Gray, which orders the $2^n$ binary strings of length $n$ so that consecutive strings differ in one bit. For example, when $n=5$ the order is

$00000,00001,00011,00010,00110,00111,00101,00100,$

$01100,01101,01111,01110,01010,01011,01001,01000,$

$11000,11001,11011,11010,11110,11111,11101,11100,$

$10100,10101,10111,10110,10010,10011,10001,10000.$

The BRGC listing is a 1-Gray code in which consecutive strings differ by one bit change. We note that the order is also cyclic because the last and first strings also differ by the closeness condition.‘ For a survey on Gray codes, see [26, 30]. In this paper, we are focusing on 2-Gray code, where consecutive strings differ by at most two bit changes.

An interesting problem related to Lucas words is thus to discover a Gray code for such strings. The problem was first studied under the name Lucas cube, where a Hamiltonian path in the Lucas cube corresponds to a 1-Gray code for Lucas words. Several results related to Lucas cubes have been published [1, 8, 18, 21, 25, 27, 36]. The problem of finding a Gray code for Lucas words was solved by Baril and Vajnovzski [5, 6]. They proved that a 1-Gray code exists if and only if $(p+1)\nmid n$, and therefore there is no 1-Gray code for all integers $n$ and $p$. However, they were able to find a 2-Gray code for Lucas words for all integers $n$ and $p$. Baril and Vajnovszki proved that the dual reflected order induces a 2-Gray code for Lucas words. The dual reflected order can be obtained by complementing, reversing, and then listing the strings in BRGC order in reverse. For example, filtering the dual reflected Gray code produced by complementing and reversing the BRGC listing for $n=5$ leads to the following 2-Gray code for Lucas words of length $n=5$ and $p=2$:

$\cancel{11110},\cancel{01110},\cancel{00110},\cancel{10110},10010,00010,01010,\cancel{11010},$

$\cancel{11000},01000,00000,10000,10100,00100,\cancel{01100},\cancel{11100},$

$\cancel{11101},\cancel{01101},00101,\cancel{10101},\cancel{10001},00001,01001,\cancel{11001},$

$\cancel{11011},\cancel{01011},\cancel{00011},\cancel{10011},\cancel{10111},\cancel{00111},\cancel{01111},\cancel{11111}.$

Baril and Vajnovszki also developed an efficient algorithm to generate Lucas words in dual reflected order in constant amortized time per string. However, their Gray code is not cyclic. This paper thus provides the first cyclic 2-Gray code for Lucas words that can be constructed efficiently in constant amortized time per string. Since there is no 1-Gray code for Lucas words for all integers $n$ and $p$, our cyclic 2-Gray code is optimal. For more information about Gray codes induced by the binary reflected Gray code or the dual reflected Gray code, see [31, 32, 35].

The rest of the paper is outlined as follows. In Section 2, we describe a simple recursive algorithm for generating a cyclic 2-Gray code for Fibonacci words that start with a 0, along with additional operations to generate a cyclic 2-Gray code for Fibonacci words. Then in Section 3, we present an algorithm that utilizes our approach for generating Fibonacci words that start with a 0 to construct a cyclic 2-Gray code for Lucas words. Lastly in Section 4, we introduce a dynamic programming approach to generate Fibonacci words that start with a 0, Fibonacci words and Lucas words, and demonstrate that the strings can be generated in constant amortized time per string.

In this section, we first describe a simple recursive algorithm for generating a cyclic 2-Gray code for Fibonacci words that start with a 0. We then discuss simple modifications to the algorithm to generate a cyclic 2-Gray code for Fibonacci words. The approach is similar to the algorithms described in [37] for constructing cyclic 2-Gray codes for $q$-run constrained words and $q$-decreasing sequences. A Fibonacci word of order $p$ and length $n$ is a binary string of length $n$ that avoids $p$ consecutive ones. As an example, the 13 Fibonacci words of order $p=3$ and length $n=4$ are

0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101.

The seven Fibonacci words of order $p=3$ and length $n=4$ that start with a 0 are highlighted in bold and in blue color. The set of Fibonacci words is in bijection with the set of $q$-decreasing sequences, which are binary strings in which every maximal factor of the form $0^a{1}^b$ satisfies the condition where $a=0$ or $qa>b$ [3].

There are several Gray codes for Fibonacci words. Liu, Hsu, and Chung [23] first studied this problem under the name Fibonacci cube, showing that the Fibonacci cube is Hamiltonian, meaning there exists a 1-Gray code for Fibonacci words for any integer order $p$. Later, Vajnovszki [34] provided an efficient algorithm that constructs a 1-Gray code for Fibonacci words in constant amortized time per string. Chinburg, Savage, and Wilf [7] considered a more restricted Gray code for Fibonacci words, where any two 1s are at least $d\le 2$ positions apart. For $d=2$, they provided a Gray code which is precisely the Gray code by Vajnovszki [34]. For $d\ge 3$, they showed that a 1-Gray code does not exist, but they constructed a 2-Gray code that only uses single bit-flips or transpositions of a 0 and 1; see also [4]. The Gray codes provided by Vajnovszki and Chinburg et. al., however, are not cyclic. More recently, Hassler, Vajnovszki, and Wong [15, 16] proposed a greedy algorithm to generate a homogeneous 2-Gray code for Fibonacci words with a fixed weight (number of 1s) $k$, where the bits between the swapped 0 and 1 are all 0s. A 2-Gray code for Fibonacci words with no weight restriction can thus be constructed by interleaving listings of fixed-weight Fibonacci words with odd weights and reversals of the listings of fixed-weight Fibonacci words with even weights, in a manner similar to the approach described in [37] for the $q$-decreasing sequence. Hassler, Vajnovszki, and Wong also provided an efficient construction for generating the listing in constant amortized time per string. Interestingly, the number of Fibonacci words also follows the Fibonacci numbers and multi-step Fibonacci numbers [12, 24]. For example, when $p=2$, the initial six terms of the enumeration of Fibonacci words are 2, 3, 5, 8, 13, 21.

Below we provide a new cyclic 2-Gray code for Fibonacci words. Our construction is similar to the one we provided in [37] for generating Gray codes for $q$-decreasing sequences. All strings considered in this paper are binary. Our algorithms use a run-length representation for binary strings using a series of blocks which are maximal substrings of the form $0^{\ast }{1}^{\ast }$. Each block $B_i$ can be represented by two non-negative integers $(s_i,t_i)$ corresponding to the number of 0s and 1s respectively. The length of the block $B_i$ is thus given by $|B_i|=s_i+t_i$. For example, the string $\alpha =000110100011001$ is represented by $B_1{B}_2{B}_3{B}_4=(3,2)(1,1)(3,2)(2,1)$. We first prove the following lemmas.

In this section, we leverage our results on Fibonacci words to generate a cyclic 2-Gray code for Lucas words. Observe that the set of Lucas words of order $p$ and length $n$ can be constructed by taking the union of all strings in the format $1^{\mathrm{\ell }}\gamma {01}^m$, where $\gamma$ is a Fibonacci word of order $p$ that starts with a 0 and has length $n-\mathrm{\ell }-m-1$, and . Removing the prefix $1^{\mathrm{\ell }}$ and the suffix ${01}^m$ from each string in the set results in a set that contains all possible Fibonacci words of order $p$ that start with a 0 and have length $n-\mathrm{\ell }-m-1$.

The main idea of our algorithm is thus to utilize our recursive algorithm for ${𝒵}_p^n$ to first generate a cyclic 2-Gray code for Fibonacci words that starts with a 0, for all possible length $n-\mathrm{\ell }-m-1$. Subsequently, we prepend the prefix $1^{\mathrm{\ell }}$ and append the suffix ${01}^m$ to each Fibonacci word that starts with a 0. We first define ${ℳ}_{k,s,r}^n$ as a sequence with strings that start with $1^{s-r}$ and end with ${01}^r$, while in between consists of the strings in ${𝒵}_p^{n-s-1}$, that is:

For the special cases when $p=\{1,2,3\}$, our Gray code listings for Lucas words ${ℒ}_p^n$ are simply the listing $0^n$, the listing ${𝒵}_2^n,{ℳ}_{2,1,0}^n$, and the listing ${\overline{𝒵}}_3^n,{ℳ}_{3,2,1}^n,{\overline{ℳ}}_{3,2,0}^n,{ℳ}_{3,1,0}^n$ respectively. Otherwise if $p>3$, our Gray code listing ${ℒ}_p^n$ for Lucas words starts with ${\overline{𝒵}}_p^n$. It then connects to ${ℳ}_{p,2,1}^n$, followed by listings of the form ${ℳ}_{p,s,r}^n$ where each time both $s$ and $r$ are incremented by one until $s$ reaches its maximum possible value, $s=p-1$. Subsequently, $r$ is decremented by one, and the listing connects to the reverse of ${ℳ}_{p,p-1,p-3}^n$, that is ${\overline{ℳ}}_{p,p-1,p-3}^n$. This pattern continues with connections to listings of the form ${\overline{ℳ}}_{p,s,r}^n$ and gradually decrementing both $s$ and $r$ by one together until $r=1$. At $r=1$, $s$ is incremented by one, and the process of incrementing both $s$ and $r$ by one continues until reaching the maximum possible value for $s$ again. This zigzag pattern proceeds until reaching either the listing ${ℳ}_{p,p-1,1}^n$ or ${\overline{ℳ}}_{p,p-1,1}^n$. It then connects to ${ℳ}_{p,p-2,0}^n$ if the current listing is ${ℳ}_{p,p-1,1}^n$, or to ${\overline{ℳ}}_{p,p-2,0}^n$ if the current listing is ${\overline{ℳ}}_{p,p-1,1}^n$. Next, it connects to ${ℳ}_{p,p-1,0}^n$, followed by ${\overline{ℳ}}_{p,p-3,0}^n$ and continues decrementing $s$ until reaching ${\overline{ℳ}}_{p,1,0}^n$.

An example of ${ℒ}_p^n$ with $n=6$ and $p=5$ is given as follows:

• $\mathrm{■}$

• $\mathrm{■}$

  ${ℳ}_{5,2,1}^6$: $100101,101101,101001,100001$;

• $\mathrm{■}$

  ${ℳ}_{5,3,2}^6$: $101011,100011$;

• $\mathrm{■}$

  ${ℳ}_{5,4,3}^6$: $100111$;

• $\mathrm{■}$

  ${\overline{ℳ}}_{5,4,2}^6$: $110011$;

• $\mathrm{■}$

  ${\overline{ℳ}}_{5,3,1}^6$: $110001,110101$;

• $\mathrm{■}$

  ${ℳ}_{5,4,1}^6$: $111001$;

• $\mathrm{■}$

  ${ℳ}_{5,3,0}^6$: $111010,111000$;

• $\mathrm{■}$

  ${ℳ}_{5,4,0}^6$: $111100$;

• $\mathrm{■}$

  ${\overline{ℳ}}_{5,2,0}^6$: $110000,110100,110110,110010$;

• $\mathrm{■}$

  ${\overline{ℳ}}_{5,1,0}^6$: $100000,101010,101000,100100,101100,101110,100110,100010$.

As such, the Gray code listing for Lucas words for $p=5$ and $n=6$, that is ${ℒ}_5^6$, is as follows:

$000000,010000,010101,010100,010010,010110,010111,010011,010001,001001,$

$001011,001010,001000,011000,011010,011011,011001,011101,011100,001100,$

$001101,000101,000100,000010,000110,001110,011110,001111,000111,000011,$

$000001,100101,101101,101001,100001,101011,100011,100111,110011,110001,$

$110101,111001,111100,111010,111000,110010,110110,110100,110000,100010,$

$100110,101110,101100,100100,101000,101010,100000.$

Figure 1 illustrates connections of the listings that create ${ℒ}_5^6$. The algorithm for generating ${ℒ}_k^n$ is shown in Algorithm 1.

Our algorithm to generate Fibonacci words and Lucas words relies on our algorithm to generate Fibonacci words that start with a 0. We thus first discuss an efficient algorithm to generate our listing ${𝒵}_p^n$ for Fibonacci words that start with a 0.

Applying the formulae presented in the previous subsection, the pseudocodes in Algorithm 2 and Algorithm 3 generate Fibonacci words that start with a 0 in cyclic 2-Gray code order. The algorithm ConstructfRunTable precompute ${𝒵}_p^t$ using a standard dynamic programming approach, where , following the recursive definition of ${𝒵}_p^n$ and stores ${𝒵}_p^n$ in a table $R$. The precomputed table $R$ stores each block $B\cdot {({𝒵}_p^i)}^{-j}$ within ${𝒵}_p^t$ by a 4-tuple $(r_1,r_2,r_3,r_4)$ which represents $0^{r_1}{1}^{r_2}\cdot {({𝒵}_p^{r_4})}^{-((j+r_3)mod2)}$. For example, a precomputed table that stores ${𝒵}_p^n$ for $p=5$ and $1\le n\le 6$ is shown in Table 1. Also note that when , then the variable $j$ does not affect the listing as ${𝒵}_p^0$ is the empty list and ${𝒵}_p^1=0$. We thus initialize the variable $j=1$ when $t\le 2$. Otherwise when $t\ge 2$, observe that the variable $j$ is updated every time a tuple $(r_1,r_2,r_3,r_4)$ is stored in the table $R$. We thus complement the variable $j$ each time when a tuple is produced when $n>2$. The algorithm fRun then prints out the Fibonacci words in ${𝒵}_p^t$ by referring to the table $R$. To generate Fibonacci words that start with a 0, we make the initial call ConstructfRunTable$(n,p)$ to construct the table $R$, then we make the call fRun$(n,0)$. A complete Python implementation of the algorithm is given in Appendix A.

A $q$-decreasing word is a binary string in which every maximal factor of the form $0^a{1}^b$ satisfies the condition where $a=0$ or $qa>b$, with $q$ being a positive real number. As an example, the 21 $q$-decreasing words of length $n=6$ and $q=1$ are

000000, 000001, 000010, 000011, 000100, 000110, 001000,

001001, 100000, 100011, 100010, 100100, 100001, 110000,

110001, 110010, 111000, 111001, 111100, 111110, 111111.

In [37], we provided a recursive algorithm to generate cyclic 2-Gray codes for $q$-decreasing words, in a similar manner as the recursive algorithm discussed in this paper. The dynamic programming approach discussed in this paper for generating Fibonacci words that start with a 0 can thus be efficiently applied to generate 2-Gray codes for $q$-decreasing words, and subsequently, $q$-run constrained words.