%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