[seqfan] nonadjacent form (sparse signed binary representation)

Joerg Arndt arndt at jjj.de
Mon Jan 17 11:21:08 CET 2011

```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

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

```