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

%I #45 Jul 18 2024 14:26:43

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

%T 38,37,36,35,34,33,32,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,

%U 79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,191,190,189

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

%H Reinhard Zumkeller, <a href="/A010078/b010078.txt">Table of n, a(n) for n = 1..8192</a>

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

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

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

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

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

%e In binary:

%e a( 1_2) = 1_2,

%e a( 10_2) = 10_2,

%e a( 011_2) = 101_2,

%e a( 100_2) = 100_2,

%e a(0101_2) = 1011_2,

%e a(0110_2) = 1010_2,

%e a(0111_2) = 1001_2,

%e a(1000_2) = 1000_2.

%t Array[2^(Ceiling[Log2[#] + 1]) - # &, 67] (* _Michael De Vlieger_, Oct 15 2018 *)

%o (Haskell)

%o a010078 = x . subtract 1 where

%o x m = if m == 0 then 1 else 2 * x m' + 1 - b

%o where (m',b) = divMod m 2

%o -- _Reinhard Zumkeller_, Feb 21 2014

%o (PARI) a(n) = if(n--, bitneg(n,2+logint(n,2)), 1); \\ _Kevin Ryde_, Apr 14 2021

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

%K base,nonn

%O 1,2

%A _Leonid Broukhis_