Resumen de Analysis of Alternative Digit Sets for Nonadjacent Representations

Clemens Heuberger, Helmut Prodinger

• 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