login
Read binary expansion of n from the right; keep track of the excess of 1's over 0's that have been seen so far; sequence gives 1 + maximum(excess of 1's over 0's).
5

%I #31 Feb 05 2022 15:57:19

%S 1,2,1,3,1,2,2,4,1,2,1,3,1,3,3,5,1,2,1,3,1,2,2,4,1,2,2,4,2,4,4,6,1,2,

%T 1,3,1,2,2,4,1,2,1,3,1,3,3,5,1,2,1,3,1,3,3,5,1,3,3,5,3,5,5,7,1,2,1,3,

%U 1,2,2,4,1,2,1,3,1,3,3,5,1,2,1,3,1,2,2,4,1,2,2,4,2,4,4,6,1,2,1,3,1,2,2,4,1

%N Read binary expansion of n from the right; keep track of the excess of 1's over 0's that have been seen so far; sequence gives 1 + maximum(excess of 1's over 0's).

%C Associated with A036988 (Remark 4 of the reference).

%H Reinhard Zumkeller, <a href="/A036989/b036989.txt">Table of n, a(n) for n = 0..10000</a>

%H H. Niederreiter and M. Vielhaber, <a href="http://dx.doi.org/10.1006/jcom.1996.0014">Tree complexity and a doubly exponential gap between structured and random sequences</a>, J. Complexity, 12 (1996), 187-198.

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

%F a(n) = 1 iff, in the binary expansion of n, reading from right to left, the number of 1's never exceeds the number of 0's: a(A036990(n)) = 1.

%F a(0) = 1, a(2n) = max(a(n) - 1, 1), a(2n+1) = a(n) + 1. - _Franklin T. Adams-Watters_, Dec 26 2006

%F Equals inverse Moebius transform (A051731) of A010060, the Thue-Morse sequence starting with "1": (1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, ...). - _Gary W. Adamson_, May 13 2007

%e 59 in binary is 111011, excess from right to left is 1,2,1,2,3,4, maximum is 4, so a(59) = 4.

%t a[0] = 1; a[n_?EvenQ] := a[n] = Max[a[n/2] - 1, 1]; a[n_] := a[n] = a[(n-1)/2] + 1; Table[a[n], {n, 0, 104}] (* _Jean-François Alcover_, Nov 05 2013, after _Franklin T. Adams-Watters_ *)

%o (Haskell)

%o import Data.List (transpose)

%o a036989 n = a036989_list !! n

%o a036989_list = 1 : concat (transpose

%o [map (+ 1) a036989_list, map ((max 1) . pred) $ tail a036989_list])

%o -- _Reinhard Zumkeller_, Jul 31 2013

%Y Cf. A036988, A036990, A126387.

%Y Cf. A010060.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_

%E Edited by _Joshua Zucker_, May 11 2006