**Abstract**

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.*

**Introduction**

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.*)

**Part I**

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 PTheorem 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 P^{n}different possible number sequences.

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 (2

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 [0]->[1]->[2]...->[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 aIntuitively, this hypothesis makes a good deal of sense. A set of sequences of type 1 and length 1 has only one member sequence, [0], 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.Gray Code.

Lemma 3-2: A set of binary sequences of length L constitutes aBy 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 aGray Code. To constitute aGray Code, the set must be able to display entirely and to cycle through and display entirely again.

Block of Last 2 positions (reversed) [1,0]->[1,1]->[0,1]->[0,0].

First position [0]->[1].

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 aAccording to Lemma 3-2, if the set from Theorem 3 is of sequences of type 2, then it will constitute aGray Code.

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 aIn order to prove Theorem 4, we shall use a step-by-step approach. First, let us prove the following:Gray Code.

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 aIn 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.Gray Code.

[0,0]->[0,1]->[0,2]->[1,2]->[1,1]->[1,0]->[2,0]->[2,1]- >[2,2].

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 [1] for our standard reverse list to [2]->[0]- >[1]. By exchanging the last two sequences in the list, we can avoid "wasting" the [0] term in the last position at the interface point, and we can use the last term value of [0] 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 3^{2} or 9 sequences long, whereas
each display list for the last position is 3^{1} places long. In the display list for
the second position, for example, we used a [2]->[0]->[1] progression as opposed to
a [2]->[1]->[0] 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 aUnfortunately, 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.Gray Code.

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 | |
---|---|---|

0 | [] | 1 |

1 | [.] | 1 |

2 | [..],[-] | 2 |

3 | [...],[.-],[-.] | 3 |

4 | [....],[..-],[.-.],[-..],[--] | 5 |

5 | [.....],[...-],[..-.],[.-..],[.--],[-...],[--.],[-.-] | 8 |

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.

N | Sequences |
---|---|

1 | [.] |

2 | [..]->[-] |

3 | [-.]->[...]->[.-] |

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.

Now we can compare these sequences with those for N=3 and N=2.

N=3 [1,1,1]-> [1,2]-> [2,1].

N=2 [1,1]-> [2].

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 |
---|---|---|---|---|

11111 | 122 | 1211/ | 211/ | [.-..] |

1112 | 1211/ | 122/ | 122/ | [.--] |

1121 | 1121 | 11111 | 1112/ | [...-] |

1211 | 1112 | 1112/ | 11111/ | [.....] |

122/ | 11111/ | 1121/ | 1121/ | [..-.] |

2111 | 221/ | 221/ | 221/ | [--.] |

212 | 212 | 2111/ | 2111/ | [-...] |

221 | 2111 | 212 | 212 | [-.-] |

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

N=2 [..]->[-]->cycles infinitely.

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.

N=4 [.-.]->[....]->[..-]->[--]->[-..]->does not cycle infinitely.

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) |
---|---|

[...] | [..]->interrupted->[-] |

[..-] | [.]-> |

[--] | [.]-> |

[-.] | [..]->[-]-> |

[.-] | [-]->[..]->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 T_{k} as a representation of a
second block sequence of length N-3, while S_{k} 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.
[...] T_{1->}...T_{a->}

[..-] S_{1->}..S_{F(n-4)->};
[--] S_{F(n-4)->}..S_{1->};
[-.] T_{a->}...T_{a+1->}; (Note-because the set of the
T_{k} sequences forms a *Gray Code *, if we cycle backwards
T_{a+1} from T_{a} we can still run through every possible sequence
in the set).
[...] T_{a+1->};...T_{F(n-3)->};
[.-] T_{F(n-3)->};...T_{1->}; 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 aGray Codeaccording to the specifications of Part II of this paper if the quantity N-2 is a multiple of 3.

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*

**Acknowledgments**

I would like to thank Morris Dworkin and Mike Lawler for intellectual encouragement and their help in editing this paper.

Sameer's work

Mathematics Directed Research Class

Summer Odyssey '96 Student Projects