OFFSET
0,3
COMMENTS
LINKS
Rémy Sigrist, Table of n, a(n) for n = 0..8192
Pages 61-62 of Matters Computational (The Fxtbook).
EXAMPLE
The first few nonadjacent forms (NAF) are
(dots are used for zeros for better readability):
n binary(n) NAF(n)
0: ....... ....... 0 =
1: ......1 ......P 1 = +1
2: .....1. .....P. 2 = +2
3: .....11 ....P.M 3 = +4 -1
4: ....1.. ....P.. 4 = +4
5: ....1.1 ....P.P 5 = +4 +1
6: ....11. ...P.M. 6 = +8 -2
7: ....111 ...P..M 7 = +8 -1
8: ...1... ...P... 8 = +8
9: ...1..1 ...P..P 9 = +8 +1
10: ...1.1. ...P.P. 10 = +8 +2
11: ...1.11 ..P.M.M 11 = +16 -4 -1
12: ...11.. ..P.M.. 12 = +16 -4
13: ...11.1 ..P.M.P 13 = +16 -4 +1
14: ...111. ..P..M. 14 = +16 -2
15: ...1111 ..P...M 15 = +16 -1
16: ..1.... ..P.... 16 = +16
17: ..1...1 ..P...P 17 = +16 +1
18: ..1..1. ..P..P. 18 = +16 +2
This sequence gives the words obtained by keeping the 'P' (sum of positive terms in rightmost column), keeping the 'M' gives A184616 (negative sum of negative terms in rightmost column).
MATHEMATICA
bin2naf[x_] := Module[{xh, x3, c, np, nm},
xh = BitShiftRight[x, 1];
x3 = x + xh;
c = BitXor[xh, x3];
np = BitAnd[x3, c];
nm = BitAnd[xh, c];
Return[{np, nm}]];
a[n_] := bin2naf[n][[1]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 30 2019, from PARI *)
PROG
(PARI)
bin2naf(x)=
{ /* Compute (nonadjacent) signed binary representation of x: */
local(xh, x3, c, np, nm);
xh = x >> 1;
x3 = x + xh;
c = bitxor(xh, x3);
np = bitand(x3, c); /* bits == +1 */
nm = bitand(xh, c); /* bits == -1 */
return([np, nm]); /* np-nm==x */
}
{ for(n=0, 100, v = bin2naf(n); print1(v[1], ", "); ); } /* show terms */
{ for(n=0, 100, v = bin2naf(n); print1(v[2], ", "); ); } /* terms of A184616 */
{ for(n=0, 100, v = bin2naf(n); print1(v[1]+v[2], ", "); ); } /* terms of A184617 */
{ for(n=0, 100, v = bin2naf(n); print1(v[1]-v[2], ", "); ); } /* == n */
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Jan 18 2011
STATUS
approved