Analysis of Alternative Digit Sets for Nonadjacent Representations

.  It is known that every positive integer n can be represented as a finite sum of the form ∑iai2i, where ai ∈ {0, 1,−1} and no two consecutive ai’s are non-zero (“nonadjacent form”, NAF). Recently, Muir and Stinson [14, 15] investigated other digit sets of the form {0, 1, x}, such that each integer has a nonadjacent representation (such a number x is called admissible). The present paper continues this line of research. The topics covered include transducers that translate the standard binary representation into such a NAF and a careful topological study of the (exceptional) set (which is of fractal nature) of those numbers where no finite look-ahead is sufficient to construct the NAF from left-to-right, counting the number of digits 1 (resp. x) in a (random) representation, and the non-optimality of the representations if x is different from 3 or −1.