login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A184615 Positive parts of the nonadjacent forms for n 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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.

LINKS

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Pages 61-62 of Matters Computational (The Fxtbook).

FORMULA

a(n) - A184616(n) = n

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

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

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

Sequence in context: A327625 A084824 A344710 * A151969 A261393 A327629

Adjacent sequences:  A184612 A184613 A184614 * A184616 A184617 A184618

KEYWORD

nonn

AUTHOR

Joerg Arndt, Jan 18 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 28 07:25 EDT 2022. Contains 354903 sequences. (Running on oeis4.)