cp's OEIS Frontend

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

%I A010078 #45 Jul 18 2024 14:26:43
%S A010078 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 A010078 38,37,36,35,34,33,32,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,
%U A010078 79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,191,190,189
%N A010078 Shortest representation of -n in 2's-complement format.
%H A010078 Reinhard Zumkeller, <a href="/A010078/b010078.txt">Table of n, a(n) for n = 1..8192</a>
%H A010078 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A010078 R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F A010078 a(n) = 2^(ceiling(log_2(n)+1)) - n.
%F A010078 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 A010078 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 A010078 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 A010078 In binary:
%e A010078   a(   1_2) =    1_2,
%e A010078   a(  10_2) =   10_2,
%e A010078   a( 011_2) =  101_2,
%e A010078   a( 100_2) =  100_2,
%e A010078   a(0101_2) = 1011_2,
%e A010078   a(0110_2) = 1010_2,
%e A010078   a(0111_2) = 1001_2,
%e A010078   a(1000_2) = 1000_2.
%t A010078 Array[2^(Ceiling[Log2[#] + 1]) - # &, 67] (* _Michael De Vlieger_, Oct 15 2018 *)
%o A010078 (Haskell)
%o A010078 a010078 = x . subtract 1 where
%o A010078    x m = if m == 0 then 1 else 2 * x m' + 1 - b
%o A010078             where (m',b) = divMod m 2
%o A010078 -- _Reinhard Zumkeller_, Feb 21 2014
%o A010078 (PARI) a(n) = if(n--, bitneg(n,2+logint(n,2)), 1); \\ _Kevin Ryde_, Apr 14 2021
%Y A010078 Cf. A004754 (terms sorted), A008687 (binary weight).
%K A010078 base,nonn
%O A010078 1,2
%A A010078 _Leonid Broukhis_