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

Author

Leonid Broukhis

Keywords

• base
• nonn

Examples

			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.
		

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

Crossrefs

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

Programs

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

Mathematica

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

PARI

a(n) = if(n--, bitneg(n,2+logint(n,2)), 1); \\ Kevin Ryde, Apr 14 2021

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