A184615 - OEIS

%I #27 Feb 25 2023 04:28:15

%S 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,

%T 34,32,32,33,32,32,32,33,34,36,36,37,40,40,40,41,42,64,64,65,64,64,64,

%U 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

%N Positive parts of the nonadjacent forms for n.

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

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

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

%H Rémy Sigrist, <a href="/A184615/b184615.txt">Table of n, a(n) for n = 0..8192</a>

%H Pages 61-62 of <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>.

%F a(n) - A184616(n) = n

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

%e The first few nonadjacent forms (NAF) are

%e (dots are used for zeros for better readability):

%e      n     binary(n)  NAF(n)

%e    0:    .......    .......      0 =

%e    1:    ......1    ......P      1 =  +1

%e    2:    .....1.    .....P.      2 =  +2

%e    3:    .....11    ....P.M      3 =  +4 -1

%e    4:    ....1..    ....P..      4 =  +4

%e    5:    ....1.1    ....P.P      5 =  +4 +1

%e    6:    ....11.    ...P.M.      6 =  +8 -2

%e    7:    ....111    ...P..M      7 =  +8 -1

%e    8:    ...1...    ...P...      8 =  +8

%e    9:    ...1..1    ...P..P      9 =  +8 +1

%e   10:    ...1.1.    ...P.P.     10 =  +8 +2

%e   11:    ...1.11    ..P.M.M     11 =  +16 -4 -1

%e   12:    ...11..    ..P.M..     12 =  +16 -4

%e   13:    ...11.1    ..P.M.P     13 =  +16 -4 +1

%e   14:    ...111.    ..P..M.     14 =  +16 -2

%e   15:    ...1111    ..P...M     15 =  +16 -1

%e   16:    ..1....    ..P....     16 =  +16

%e   17:    ..1...1    ..P...P     17 =  +16 +1

%e   18:    ..1..1.    ..P..P.     18 =  +16 +2

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

%t bin2naf[x_] := Module[{xh, x3, c, np, nm},

%t   xh = BitShiftRight[x, 1];

%t   x3 = x + xh;

%t   c = BitXor[xh, x3];

%t   np = BitAnd[x3, c];

%t   nm = BitAnd[xh, c];

%t   Return[{np, nm}]];

%t a[n_] := bin2naf[n][[1]];

%t Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, May 30 2019, from PARI *)

%o (PARI)

%o bin2naf(x)=

%o { /* Compute (nonadjacent) signed binary representation of x: */

%o     local(xh,x3,c,np,nm);

%o     xh = x >> 1;

%o     x3 = x + xh;

%o     c = bitxor(xh, x3);

%o     np = bitand(x3, c);  /* bits == +1 */

%o     nm = bitand(xh, c);  /* bits == -1 */

%o     return([np,nm]);  /* np-nm==x */

%o }

%o { for(n=0,100, v = bin2naf(n); print1(v[1],", "); ); } /* show terms */

%o { for(n=0,100, v = bin2naf(n); print1(v[2],", "); ); } /* terms of A184616 */

%o { for(n=0,100, v = bin2naf(n); print1(v[1]+v[2],", "); ); } /* terms of A184617 */

%o { for(n=0,100, v = bin2naf(n); print1(v[1]-v[2],", "); ); }  /* == n */

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

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

%K nonn

%O 0,3

%A _Joerg Arndt_, Jan 18 2011