ITERATING AN ALPHA-ARY GRAY CODE

In this paper we prove a theorem on the number of distinct codes produ ced when the alpha-ary Gray code mapping of Sharma and Khanna [Inform. Sci., 15 (1978), pp. 31-43] is iteratively applied to an alpha-ary, d imension l code; that is, starting with an alpha-ary, dimension l code , and repeatedly applying the permutation given by Sharma and Khanna's mapping. From this theorem, it is easy to show there are Theta(l(q)) distinct codes generated from this mapping, where q is the number of d istinct primes in alpha (Let f : N --> R.O(f) is the set of functions g : N --> R such that for some c is an element of R+ and some n(0) i s an element of N, g(n) less than or equal to cf(n) for all n greater than or equal to n(0). Theta(f) is the set of functions g : N --> R s uch that 2 g is in O(f) and f is in O(g).). To prove this theorem we s how that any base alpha, dimension l code word will cycle in O(l q) it erations of this Gray code mapping, and that this upper bound is attai ned. This theorem is a generalization of a theorem proven by Culberson [Evolutionary Comput., 2 (1995), pp. 279-311] for the binary case.