A184615 Positive parts of the nonadjacent forms for n.

0, 1, 2, 4, 4, 5, 8, 8, 8, 9, 10, 16, 16, 17, 16, 16, 16, 17, 18, 20, 20, 21, 32, 32, 32, 33, 34, 32, 32, 33, 32, 32, 32, 33, 34, 36, 36, 37, 40, 40, 40, 41, 42, 64, 64, 65, 64, 64, 64, 65, 66, 68, 68, 69, 64, 64, 64, 65, 66, 64, 64, 65, 64, 64, 64, 65, 66, 68, 68, 69, 72, 72, 72, 73, 74, 80, 80, 81, 80, 80, 80, 81, 82, 84, 84, 85, 128

Offset: 0

Author

Joerg Arndt, Jan 18 2011

Keywords

• nonn

Comments

This sequence together with A184616 (negated negative parts) gives the (signed binary) nonadjacent form (NAF) of n, see fxtbook link.

No two adjacent bits in the binary representations of a(n) are 1.

No two adjacent bits in the binary representations of a(n)+A184616(n) are 1.

Examples

			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).
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Pages 61-62 of Matters Computational (The Fxtbook).

Crossrefs

A184616 (negated negative parts), A184617 (sums of both parts =A184615+A184616).

A007302 gives the number of nonzero bits ('M' and 'P' in example).

Programs

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

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

Formula

a(n) - A184616(n) = n

a(n) + A184616(n) = A184617(n)