login
Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.
24

%I #47 Jul 01 2022 09:40:44

%S 1,2,1,4,3,2,1,8,7,6,5,4,3,2,1,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,

%T 32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,

%U 9,8,7,6,5,4,3,2,1,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47

%N Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.

%C T(n,k) < T(n,a(n)) = A070940(n) for 1 <= k < a(n) and T(n,k) <= T(n,a(n)) for a(n) <= k <= n, where T is defined as in A080080.

%C a(n) gives the distance from n to the nearest 2^t > n. - _Ctibor O. Zizka_, Apr 09 2020

%H Reinhard Zumkeller, <a href="/A080079/b080079.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F From _Benoit Cloitre_, Feb 22 2003: (Start)

%F a(n) = A004755(n) - 2*n.

%F a(n) = -n + 2*2^floor(log(n)/log(2)). (End)

%F From _Ralf Stephan_, Jun 02 2003: (Start)

%F a(n) = n iff n = 2^k, otherwise a(n) = A035327(n-1).

%F a(n) = A062383(n) - n. (End)

%F a(0) = 0, a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)-1 + 2*[n==0]. - _Ralf Stephan_, Jan 04 2004

%F a(n) = A240769(n,1); A240769(n, a(n)) = 1. - _Reinhard Zumkeller_, Apr 13 2014

%F a(n) = n + 1 - A006257(n). - _Reinhard Zumkeller_, Apr 14 2014

%p # _Alois P. Heinz_ observes in A327489:

%p A080079 := n -> 1 + Bits:-Nor(n, n):

%p # Likewise:

%p A080079 := n -> 1 + Bits:-Nand(n, n):

%p seq(A080079(n), n=1..81); # _Peter Luschny_, Sep 23 2019

%t Flatten@Table[Nest[Most[RotateRight[#]] &, Range[n], n - 1], {n, 30}] (* _Birkas Gyorgy_, Feb 07 2011 *)

%t Table[FromDigits[(IntegerDigits[n, 2] /. {0 -> 1, 1 -> 0}), 2] +

%t 1, {n, 30}] (* _Birkas Gyorgy_, Feb 07 2011 *)

%t Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1] + 1, {n, 30}] (* _Birkas Gyorgy_, Feb 07 2011 *)

%t Table[2 2^Floor[Log[2, n]] - n, {n, 30}] (* _Birkas Gyorgy_, Feb 07 2011 *)

%t Flatten@Table[Reverse@Range[2^n], {n, 0, 4}] (* _Birkas Gyorgy_, Feb 07 2011 *)

%o (Haskell)

%o a080079 n = (length $ takeWhile (< a070940 n) (a080080_row n)) + 1

%o -- _Reinhard Zumkeller_, Apr 22 2013

%o (Magma) [-n+2*2^Floor(Log(n)/Log(2)): n in [1..80]]; // _Vincenzo Librandi_, Dec 01 2016

%o (Python)

%o def A080079(n): return (1 << n.bit_length())-n # _Chai Wah Wu_, Jun 30 2022

%Y Cf. A327489, A004755, A062383, A080080, A240769, A006257.

%K nonn,base

%O 1,2

%A _Reinhard Zumkeller_, Jan 26 2003