Representations found by the greedy algorithm

[Ralf Stephan]

Quoting an ealier mail from me to the list:

>  > Edwin Clark
>  > ...with entries 0,1,or -1 ...
>  > BTW I'm not sure that "signed binary" is a well-known concept. I did,
>  > however, find reference to "signed bit" representation of integers.
> 
1. > Knuth calls the number system with "trits" -1, 0, +1 "balanced ternary".

For completeness, you have, e.g.

2.
%C A001045 Number of positive integers requiring exactly n signed bits in the non-adjacent form representation.
%H A001045 W. Bosma, <a href="http://almira.math.u-bordeaux.fr/jtnb/2001-1/jtnb13-1.html#jourelec">Signed bits and fast exponentiation</a>

3.
%C A007302 Also the number of nonzero digits in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)_2 number system).
%D A007302 C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
http://www.wits.ac.za/helmut/abstract/abs_189.htm


You wrote 
> 
> There is also something similiar called the non-adjacent form
> (NAF) of an integer--which is a representation of an integer
> to base 2, with "bits" 1,-1 and 0. Such a representation
> is unique if no two adjacent "bits" are nonzero. Years ago Joe
> Liang and I wrote some papers on error-correcting codes
> for arithmetic in which this idea appears. The number
> of non-zero "bits" in a NAF is an analogue of the Hamming
> weight of a binary number.  There are also generalizations
> to bases r > 2, but not quite as simple. Some of our work
> was covered in van Lint's hardback Springer yellow book on
> coding theory. 
> 
> So long ago I can barely recall what it was about. 
> 
> A google search on "non-adjacent form" will
> no doubt lead to better references. 
> 
> We also got a similar form for some bases for the Gaussian
> integers and other Euclidean rings. But I doubt if any of
> that is related to the current discussion.
> 
> 
> 
> --Edwin
>