In Part I of this paper, we examine sets of sequences in which each sequence has the same positive integer length N, and in which the numbers are of base P. We decide how many terms a set of sequences of length N and base P should have, and we prove that any of these sets can be arranged to form a Gray Code. In Part II, we examine sets of binary sequences in which the sum of the digits of each sequence equals a specific sum, N. We define a function to determine the number of sequences in a specific set, and we prove that any set of sequences in which (N-2) is a multiple of 3 will form a Gray Code.
The idea behind a Gray Code is seemingly simple: given a set of number sequences of length N, with P different possible characters in each position, cycle through all possible character combinations. However, for a defined set of number sequences to be a Gray Code, it must fulfill three conditions. First, to progress from one sequence in the set to the next, only one position in the sequence at a time may be changed (there may only be small changes between successive terms in the list of sequences). Second, after cycling through all possible number sequences, the set should be able to cycle back to the first sequence of the list. Finally, when cycling through the number sequences of a set, no sequence may be repeated. One example of a Gray Code is a set of all of the binary sequences of length 2 (all number sequences possessing only two digits and only containing either 0's or 1's); the set cycles [0,0]->[0,1]->[1,1]->[1,0]-> cycles back to [0,0].
In this paper we have invented several mathematical terms. The word "type" means the number of different digits that can be in a position; type 2, for example, means that a digit can only be a "0" or a "1." The "sequence" is a code word; it represents one possible combination of a specific length of numbers of a specific type. A "set of sequences" is a complete set of all of the sequences of a specific length and specific type. An example of a sequence of type 2 (which means it can only contain 0's and 1's) and length 2 is [0,1], whereas the set of all of these sequences contains [0,0],[1,0],[0,1],[1,1]. A "cycle" is a list of sequences such that the list will be able to loop infinitely and form a Gray Code . A "block" is a combination of several positions in a sequence that are treated as one combined position. A "display list" is an order of sequences in a set such that every sequence is displayed without repetition and there are only small changes between successive terms (a display list does not necessarily have to loop to form a Gray Code.)
The main problem for Part I of this paper is to determine which sets of number sequences constitute a Gray Code, and to formulate a set of rules to predetermine whether any given number set is a Gray Code. Also, we wish to determine whether, given a set of number sequences, we can systematically cycle through all of the possible combinations of numbers in a set by only changing one digit between sequences and never repeating a sequence.
Theorem 1: For any given set of number sequences of length N and type P, there exist Pn different possible number sequences.Theorem 1 can be proved easily. For every position in a number sequence there are P different possibilities for a digit. For the next position, there exist again P different possibilities for a character. Therefore, there are P*P*P...*P (N times), or PN, different number sequences of length N.
Theorem 2: Any given set of number sequences of any length N and type P (where N and P are positive integers) can be formed into a display list by changing only one digit between successive terms.To prove Theorem 2, we will first look at a simple case, the set of binary sequences of length 1. By Theorem 1, we know that there exist 2 (21) different combinations. The set of possible number sequences consists of the sequences  and . Obviously, this specific set of number sequences can cycle. We have proved that a set of binary sequences of length 1 can be arranged systematically so that all possible number sequences are displayed without repetition and by only changing the sequences one digit at a time. The cycle is ->. Similarly, for any type P, we can cycle through the set of number sequences in the following manner:
Lemma 2-1: Any set of number sequences of length 1 and the same positive integer type P can form a display list with no more than one position changed between successive sequences.In order to prove Theorem 2, we need to extend Lemma 2-1 to all sets of sequences of type P and any length N. This problem may be solved through recursion. For instance, a binary sequence of length 2 may be cycled in this manner:
After observing carefully, we notice that our display list for a binary set of sequences of length 1 shown earlier is repeated twice in the last (2nd position of the sequence), first forward and then in reverse, with a different first position corresponding to each sequence.
By Lemma 2-1, we know that we can make the last position display through all possible numbers for any type P. Also, we can now theorize that, indeed, for any type P, a set of sequences of length 2 will be able to display through all of its member sequences. Next, we simply ignore the last digit (as we already know how it cycles), and arrange the first digit separately, then combine the two sequences.
First Digit Cycles ->->...->[P-1].
Combination of the two, forms sequences of length 2:
[0,0]->[0,1]->[0,2]->...[0,P-1]->[1,P-1]->[1,P-2]->[1,P-3]- >...[1,1]->[1,0]->[2,0] ->[2,1]->...[P-1,P-1]
(Note: depending on P, the last term will either be [P-1,P-1] or [P-1,0]).
Lemma 2-2: For any set of number sequences of type P and length 2, we can form a display list so that there is only a change of one position between successive sequences in the display list.In order to prove Theorem 2, we must generalize Lemma 2-2 to be applicable for sets of number sequences of any length N. Once again, we will use recursion. For example, let us begin with a set of sequences of type P and length 3. By Lemma 2-2, we know that the last 2 digits will cycle correctly, and by Lemma 2-1, we know that the first digit will cycle correctly independently. If we view the last two digits as a single block, we notice that the first digit and the last two digits can combine (this is simply an extension of Lemma 2-2). However, we can also extend this general argument further; for instance, to a length of 4. As we know that a set of sequences of length 3 can be completely displayed, we simply view the last 3 digits as one block and the first digit as another. Once again, we can prove by Lemma 2-2 that the two blocks may be combined to create a set of sequences of length 4 that will display entirely according to the rules of our problem. Clearly, this argument may be extended to any length N, and we have proved Theorem 2.
We can now address the main question of Part I: Which sets of sequences constitute Gray Codes ?
Lemma 3-1: Any set of sequences of type 1, regardless of length, will constitute a Gray Code.Intuitively, this hypothesis makes a good deal of sense. A set of sequences of type 1 and length 1 has only one member sequence, , so obviously this set cycles. However, according to Theorem 1, no matter how long the sequence, the number of possible sequences in a set of sequences of type 1 is always 1. If there is only one set of sequences to deal with for any given length N, it must cycle.
Lemma 3-2: A set of binary sequences of length L constitutes a Gray Code. To constitute a Gray Code, the set must be able to display entirely and to cycle through and display entirely again.By Theorem 2, we know that we can get a binary sequence of length N to completely display all possible sequences without repetition and by only changing one digit between successive terms. Essentially, we must manipulate our display lists so that the last sequence of the list is comprised of zeroes with only one nonzero digit. For a binary sequence of length N, this sequence might be similar to [1,0,0,0...0]. Now, the progression for a binary sequence of length 2 is [0,0]->[0,1]->[1,1]->[1,0], which constitutes a Gray Code. With a length of 3, we once again use the idea of treating the last two positions as a block. This block will list forwards and then backwards, each display list corresponding to one of the two different possible first digits (as discussed in Lemma 2-2).
Block of Last 2 positions (reversed) [1,0]->[1,1]->[0,1]->[0,0].
First position ->.
Combined set of sequences: [0,0,0]->[0,0,1]->[0,1,1]->[0,1,0]->[1,1,0] ->[1,1,1]->[1,0,1]->[1,0,0]-> cycles back to [0,0,0].
Theorem 3: Any set of sequences of length N (where N is any nonnegative integer) and type P (where P is a positive, even integer) will constitute a Gray Code.According to Lemma 3-2, if the set from Theorem 3 is of sequences of type 2, then it will constitute a Gray Code. However, the idea of listing a "block" of positions forwards and backwards still pertains, no matter the type. For instance, here is a set of sequences of length 2 and type 4:
Since there are four possible digits for the first position of the sequence, the block of remaining digits lists forward, then reverse, then forward, then finally in reverse. We can observe that if the number of possible terms for the first position is even, then the last sequence will end while listing in reverse. If the remaining positions end while listing in reverse, then the last sequence will contain a "0" in every block except the first, enabling the set to cycle through again. Therefore, regardless of length, a set of sequences of type P, where P is an even integer, will constitute a Gray Code.
Theorem 4: A set of any length N (N being an integer >0) of type P (where P is a positive odd integer) will constitute a Gray Code.In order to prove Theorem 4, we shall use a step-by-step approach. First, let us prove the following:
Lemma 4-1: With the systematic approach used to create display list described in the proof of Theorem 2, it is impossible to make a set of sequences of type P, where P is odd and >1, to cycle completely to form a Gray Code.In the proof of Theorem 3, we showed that there must exist a list displaying all possible sequences of numbers in the positions following the first corresponding to each different digit in the first position. Furthermore, we also established that these display lists in the blocks of digits after the first position will list forwards and then backwards. However, if there is an odd number of possibilities for the first position, and we are forced to start in a forward list in the block of positions, then the last sequence of the list will be part of a forward list, and will not be able to cycle back to the starting sequence of the list.
This example does not cycle into a loop to form a Gray Code. If the list of sequences ends in the forward list, then the last sequence will not consist of only zeroes in the positions after the first; therefore, it is impossible to cycle a set of sequences of an odd type to form a Gray Code using the technique of Theorem 2.
However, is there another technique that can be used to arrange the sequences of a set? In fact, there is no way to arrange the sequences where the positions will not cycle in some sequential manner. Regardless of order, each position must list all possibilities for value. In order for a set of sequences of an odd number type to cycle, we must abandon our previous technique with forward/reverse listing patterns in favor of a new approach. The problem is simple; the right position lists forward and then in reverse for the first two digits in the first position. In order to list to the last digit in the first position, we must use a [2,0] sequence. Since we are not allowed repetition, we know that we will not be able to cycle the set. Therefore, we know that we will not be able to cycle the set. The last sequence in the pattern may only have one non-zero term (we want it in the first position) in it in order to form a Gray Code cycle. We know that we must find a way to make the last term [2,0]. Here is one method that works: [0,0]->[0,1]->[0,2]->[1,2]->[1,0]->[1,1]->[2,1]->[2,2]->[2,0]- > cycles infinitely. Notice the technique we use to make the set cycles. We change the interface between the first term value of 1 and the first term value of 2 from [1,0] -> [2,0] to [1,1]->[2,1].
To change the interface, we were forced to change the order of the last terms corresponding to the first term value of  for our standard reverse list to ->- >. By exchanging the last two sequences in the list, we can avoid "wasting" the  term in the last position at the interface point, and we can use the last term value of  in the final sequence of our set. We can apply this technique to more general situations, such as a set of sequences of type 3 and length 3.
Notice once again that for both positions after the first we inverted the order of the terms in the display list directly preceeding the last in order to avoid using a "0" term at the interface. For the second position, each display list is 32 or 9 sequences long, whereas each display list for the last position is 31 places long. In the display list for the second position, for example, we used a ->-> progression as opposed to a ->-> progression. By this pattern of inversion of order in the penultimate cycle of each position after the first, we can see that any set of sequences of type 3, regardless of length, will constitute a Gray Code.
Lemma 4-2: A set of sequences of type 3 (ternary) and any positive integer length N will constitute a Gray Code.Unfortunately, Lemma 4-2 only applies to sets of ternary (type 3) sequences. Upon reflection, however, we can observe that we may be able to extend our argument further. We only need to exchange two sequences in the penultimate display lists in each position. Let us test our idea on a set of sequences of type 5 and length 2.
Regardless of length or type, our technique does not change.
Summary: Part I
In Part I we looked at the "standard" form of Gray Code. With Theorem 1 we showed how to determine the exact number of sequences in a set of length N and type P. Theorem 2 proves that we can always form a display list for any given set of sequences by only changing one position between successive sequences. Finally, by using Theorem 2, we proved that any complete set of sequences of length N and type P (where N and P are nonnegative integers) will constitute a Gray Code. (Theorems 3 and 4).
Now that we have seemingly solved the problem of a standard Gray Code, we can look at a more complex version. We shall construct a new Gray Code, defined by a set containing all of the different ordered combinations of 1's and 2's such that the sum of the digits equals some positive integer, N. These sets can be thought to represent a list of words in Morse code, with a "." for a 1 and a "-" for a 2, where every possible sequence takes the same length of time to transmit. We shall use the notation "." for a 1 and "-" for a 2 throughout Part II. Note that each sequence in a set may not have the same number of digits. Like a standard Gray Code, we wish to cycle these modified Gray Code so that we can display every possible sequence without repetition. Once again, we can only make small changes to progress between each sequence. In Part II, the only changes allowed are to change two 1's ("..") to a 2 ("-"), or vice versa.
First, we wish to determine the number of sequences that exist for any given integer value (N) for the sum of the sequences. For instance, there is only one ordered sequence of 1's and 2's whose sum is 1, [.]. Here are a few other examples:
|N (sum of terms)||Sequences|
If we list the total number of sequences in order of N, we get 1->1 ->2->3->5- >8... This series, one of the most famous in the history of mathematics, is know as the Fibonacci sequence. After looking carefully at the series, we notice that each successive term of the series is defined by the sum of the two terms before it.
F(n)= number of possible sequences for any integer N.However, we wish to prove that F(N)- F(N-1) + F(N-2). Why does it exist? Let us look at a simple case; for instance, N=4. When we increase the total from 3 to 4, it is the same as creating an extra place at the left in our graphical representation of the problem. If we decide to place a "." (a 1) into this extra position, we still have four positions left. In those positions there are F(4) different possible sequences. There exists, of course, a second possibility for that extra position; we can insert a "-" (a 2) into the position. Since a "-" takes up two positions, we only have 3 positions left to deal with. In those 3 remaining positions we can have F(2) different sequences. Altogether, we have a total of F(2)+F(3) different sequences, or 5. Different sequences for N=4:
Theorem 5: For any positive integer, N , F(N) is simply F(N- 1)+F(N-2).Now that we have a working technique for determining the total number of sequences with a sum of N, we can address the second part of the question. Is it possible to create a display list for given sets of sequences? Following are examples for values of N from 1 to 4.
As we can see, the sequences for N=1 to 3 do indeed form a display list. From our proof of Theorem 5 we know that we can treat the sequences for any N (for example, 3 ) as being composed of the sequences for n-1 and n-2. In turn, the n-1 sequences are composed of n-2 and n-3 sequences, while the n-2 block can be divided into n-3 and n-4 blocks. By understanding the recursive nature of this form of Gray Code,we can develop a technique for developing complete lists of sets. For instance, let us create a sequential list of terms for N=4.
Comparing the three display lists we can easily notice the recursive structure of this form of Gray Code. In our sequential list, we decided to lists terms of 1 before terms of 2. However, what if we wanted to redesign our sequential list so that we could use our list to display each sequence and yet only have one place change between successive sequences in the list? Perhaps we could once again use our idea of forward/reverse display listing. If we take our sequential list, and then completely reverse the display list for each position, then we would bring the end sequences of adjacent display lists of the same position next to each other. Because of the recursive nature of our Gray Code, if we continued this process for successively smaller display lists, we would be able to create a list of codes with only small changes between consecutive sequences. Since the components of the sequences have different values (either a 1 or 2), the display lists are not of the same length. If a cycle is reduced to length 1, we can not subdivide it further, and we are finished applying our technique to that division. Following is an example with n=5:
|nth level||n-1 levels||n-2 levels||n-3 levels||Final Code List|
Notice that our technique appears to work. After each inversion, the sequences come closer to being able to form a display list correctly. We can also prove now that this technique can be applied to any nonnegative integer N (simply by changing the number of positions needed); therefore, we have proved the following theorem:
Theorem 6: Every set of sequences comprised solely of the digits 1 and 2 in which every sequence adds up to the same integer N will be able to form a display list.Finally, we wish to look at the most important question from Part II. Which sets of sequences actually constitute Gray Codes ? Recall that a Gray Code can be formed into a display list that will cycle infinitely. Immediately, we can prove that at least two values of N will yield Gray Codes , N=1 and N=2. We can show this easily below.
However, what about other values of N? If we look carefully at N=3 or N=4 we notice that neither constitutes a Gray Codes. For example, below are two possibilities of display lists for these values.
The reader can verify that no other display lists for these values will cycle. When we try N=5, though, we find that it is a Gray Code.
We now have the beginning of a pattern. If we consider N=1 as outside of a pattern, then we have N=2 and N=5 as Gray Codes We can conjecture that perhaps every third sequence will form a Gray Code ; therefore, we will next test the set of sequences with N=8. By Theorem 5, we know that the set of N=8 contains 34 different sequences. After a good deal of testing, we find a working arrangement of sequences:
Now we wish to look carefully at the patterns of the display lists for N=2 and N=5 to attempt to notice similarities between the two. Since there is a difference of 3 between N=2 and N=5, we will try to look at the pattern of the display lists for N=5 with a "block" of 3 removed from the first 3 positions. Since a "-" character occupies 2 positions, some sequences will not begin with a block of 3, instead some will begin with a block of 4. Following is the same arrangement of sequences from above, slightly rearranged to show the "blocks":
|First block (length 3 or 4)||Second Block (length 5 or 4)|
|[...]||[.....]->[..-.]->interrupted->[--.]->[-...]->[-.-]- >[...-] ->[.--]->[.-..]->|
|[.-]||[.-..]->[.--]->[...-]->[-.-]->[-...]->[--.]->[..-.]- >[.....]-> cycles infinitely to form a Gray Code.|
We now notice that the set of sequences with N=5 shows the same pattern.
|First Block (Length 3 or 4)||Second Block (Length 2 or 1)|
|[.-]||[-]->[..]->cycles infinitely to form a Gray Code.|
After comparing the two sequences, we notice that both exhibit the same pattern in terms of the order in the listing of the various first "blocks." There is a definite order to the arrangement of the first "blocks" of length 3 and length 4. Now, if we compare the order of the sequences for the second "blocks," we once again notice a pattern. We interrupt the sequences corresponding to the [...] first block with sequences corresponding to the [..-] block. We interrupt the sequences of the [...] block after a sequence in which the first position is empty and the following positions are the same as the opening sequence for the display cycle of the second block sequences corresponding to the first block [..-]. In other words, at the interface between the two first blocks, the second blocks will match up entirely. Next, the second block for the [..-] first block goes through a display cycle. At the interface point between the [..-] and [--] first blocks, a new display cycle for the second block corresponding to the [--] first block begins. We notice, though, that this display cycle is the reverse of the one for the [..-] first block. If we remember Part I of this paper, we realize that this forward/reverse cycling pattern is necessary in order for the two display cycles to be able to interface. Because of this forward/reverse cycling pattern, the end of the second block for the [--] first block is the same as the beginning of the second block for the [..-] first block. This pattern is not easily noticed in the example with N=5 because the number of sequences for the second block corresponding to either [..-] or [--] first blocks is only one. Once all of the sequences with [..-] and [--] first blocks have cycled, the next set of sequences has a first block of [-.]. We once again begin to cycle the second block of sequences, starting with a value in the second block which is the same as the last second block value corresponding to the [...] first block. Since we want the [-.] first block values to be able to interface with the next of the [...] values, we have the second block sequence which is the reverse of the second block display list for [...]. We can notice that this technique is only possible because the second block is actually a Gray Code independently. Because the value of N for both these sequences is 3 greater than the value of N for the previous Gray Code , the second block is the same as the previous Gray Code . By looping backwards we are able to reach a second block sequence identical to the next second block sequence for the [...] first block. After cycling the second block sequences in reverse, we are again at an interface point between the [-.] and [...] first block. We can now continue the display list for the second block corresponding to the first block of [...], which was interrupted by the [..-],[--], and [-.] first block sequences. Finally, after finishing the display list for the second block sequences corresponding to the first block of [...], we reach an interface point with the first block value of [.-]. The display list for the second block sequences corresponding to the first block of [.-] is the reverse of the display list for the second block sequences corresponding to the first block of [...]. Since the display list in once again in reverse, the very last second block sequence will be the same as the very first second block sequence in the display list, meaning that the display list forms a Gray Code (because the display list can cycle infinitely). This pattern shows up in every set of sequences which has a value of N such that (N-2) is a multiple of 3. Our explanation of this pattern is actually a proof of a set rule for constructing Gray Code s according to the rules of Part II.
Since this proof is rather complex, we shall now also attempt to prove the existence
of the pattern algebraically. We shall define Tk as a representation of a
second block sequence of length N-3, while Sk is a representation of a
second block sequence of length N-4. Following is a general form for the cycling pattern
for a Gray Code according to the rules for Part II. In this diagram, the second
block sequences are written to the right of their respective first block sequence.
[..-] S1->..SF(n-4)-> [--] SF(n-4)->..S1-> [-.] Ta->...Ta+1-> (Note-because the set of the Tk sequences forms a Gray Code , if we cycle backwards Ta+1 from Ta we can still run through every possible sequence in the set). [...] Ta+1->...TF(n-3)-> [.-] TF(n-3)->...T1-> cycles infinitely to form a Gray Code .
We have now proved the following theorem:
Theorem 7: Any set of sequences in which the sum of the digits in each sequence equals N and the digits in the sequence are comprise solely of 1's and 2's will form a Gray Code according to the specifications of Part II of this paper if the quantity N-2 is a multiple of 3.Summary: Part II
In Part II, we have proved several theorems that predict the nature of sets of number sequences comprised solely of 1's and 2's in which the digits in each sequence add up to the same sum, N. Every set of these sequences can be arranged to form a display list. Also, we know that the number of sequences in each set , F(N), is defined by the Fibonacci sequence such that F(N)=F(N-1) + F(N-2). Finally, we have concluded that certain sets in which the difference between the sum of each sequence, N, and the number 2 is a multiple of 3 can be arranged into Gray Code s
I would like to thank Morris Dworkin and Mike Lawler for intellectual encouragement and their help in editing this paper.
Mathematics Directed Research Class
Summer Odyssey '96 Student Projects