A010078 Shortest representation of -n in 2's-complement format.

1, 2, 5, 4, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 191, 190, 189

Offset

1,2

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Formula

a(n) = 2^(ceiling(log_2(n)+1)) - n.

a(n) = b(n-1), where b(n) = 1 if n = 0, otherwise 2*b(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 19 2003

G.f.: (x/(1-x)) * (1/x + Sum_{k>=0} 2^k*(x^2^k + 2x^2^(k+1))/(1+x^2^k)). - Ralf Stephan, Jun 15 2003

a(1) = 1; for n > 1, a(2n-1) = 2*a(n) + 1; for n >= 1, a(2n) = 2*a(n). - Philippe Deléham, Feb 29 2004

Example

In binary:
  a(   1_2) =    1_2,
  a(  10_2) =   10_2,
  a( 011_2) =  101_2,
  a( 100_2) =  100_2,
  a(0101_2) = 1011_2,
  a(0110_2) = 1010_2,
  a(0111_2) = 1001_2,
  a(1000_2) = 1000_2.

Mathematica

Array[2^(Ceiling[Log2[#] + 1]) - # &, 67] (* Michael De Vlieger, Oct 15 2018 *)

Prog

(Haskell)
a010078 = x . subtract 1 where
   x m = if m == 0 then 1 else 2 * x m' + 1 - b
            where (m', b) = divMod m 2
-- Reinhard Zumkeller, Feb 21 2014
(PARI) a(n) = if(n--, bitneg(n, 2+logint(n, 2)), 1); \\ Kevin Ryde, Apr 14 2021

Crossrefs

Cf. A004754 (terms sorted), A008687 (binary weight).

Sequence in context: A069913 A326002 A072403 * A074639 A319525 A357983

Adjacent sequences: A010075 A010076 A010077 * A010079 A010080 A010081

Keyword

base,nonn

Author

Leonid Broukhis

Status

approved