cp's OEIS Frontend

A036989 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).

%I A036989 #31 Feb 05 2022 15:57:19
%S A036989 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 A036989 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 A036989 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 A036989 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 A036989 Associated with A036988 (Remark 4 of the reference).
%H A036989 Reinhard Zumkeller, <a href="/A036989/b036989.txt">Table of n, a(n) for n = 0..10000</a>
%H A036989 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 A036989 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A036989 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 A036989 a(0) = 1, a(2n) = max(a(n) - 1, 1), a(2n+1) = a(n) + 1. - _Franklin T. Adams-Watters_, Dec 26 2006
%F A036989 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 A036989 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 A036989 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 A036989 (Haskell)
%o A036989 import Data.List (transpose)
%o A036989 a036989 n = a036989_list !! n
%o A036989 a036989_list = 1 : concat (transpose
%o A036989    [map (+ 1) a036989_list, map ((max 1) . pred) $ tail a036989_list])
%o A036989 -- _Reinhard Zumkeller_, Jul 31 2013
%Y A036989 Cf. A036988, A036990, A126387.
%Y A036989 Cf. A010060.
%K A036989 nonn,easy
%O A036989 0,2
%A A036989 _N. J. A. Sloane_
%E A036989 Edited by _Joshua Zucker_, May 11 2006