Analysis of alternative digit sets for nonadjacent representations

作     者：Heuberger, C Prodinger, H 

作者机构：Graz Tech Univ Inst Math A-8010 Graz Austria Univ Stellenbosch Dept Math ZA-7602 Stellenbosch South Africa 

出 版 物：《MONATSHEFTE FUR MATHEMATIK》 (数学月刊)

年 卷 期：2006年第147卷第3期

页      面：219-248页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：signed digit expansion nonadjacent form alternative digit sets optimality of digit expansions transducers analysis of algorithms Hausdorff dimension 

摘      要：It is known that every positive integer n can be represented as a finite sum of the form Sigma(i)a(i)2(i), where a(i) is an element of {0, 1, -1} and no two consecutive a(i) 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.