[seqfan] nonadjacent form (sparse signed binary representation)

[Joerg Arndt]

If the following would be OK to submit,
can I somehow get two adjacent A-numbers?

Two sequences containing the negative and positive parts
of the nonadjacent signed binary representation of n
(see fxtbook p.61, or
 http://en.wikipedia.org/wiki/Non-adjacent_form ).

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 */
}

/* positve part: */
for(n=0,100,v=bin2naf(n);print1(v[1],", "););
0, 1, 2, 4, 4, 5, 8, 8, 8, 9, 10, 16, 16, 17, 16, 16, 16, 17, ...

/* negative part: */
for(n=0,100,v=bin2naf(n);print1(v[2],", "););
0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 5, 4, 4, 2, 1, 0, 0, 0, 1, 0, ...

/* playfully one could also submit: */
{ for(n=0,100, v = bin2naf(n); print1(v[1]+v[2],", "); ); }
0, 1, 2, 5, 4, 5, 10, 9, 8, 9, 10, 21, 20, 21, 18, 17, 16, 17, ...
/* and if this is fine as well I'd like 3 A-numbers */