

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


5



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Associated with A036988 (Remark 4 of the reference).


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
H. Niederreiter and M. Vielhaber, Tree complexity and a doubly exponential gap between structured and random sequences, J. Complexity, 12 (1996), 187198.
Index entries for sequences related to binary expansion of n


FORMULA

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.
a(0) = 1, a(2n) = max(a(n)  1, 1), a(2n+1) = a(n) + 1.  Franklin T. AdamsWatters, Dec 26 2006
Equals inverse Moebius transform (A051731) of A010060, the ThueMorse sequence starting with "1": (1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1,...).  Gary W. Adamson, May 13 2007


EXAMPLE

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


MATHEMATICA

a[0] = 1; a[n_?EvenQ] := a[n] = Max[a[n/2]  1, 1]; a[n_] := a[n] = a[(n1)/2] + 1; Table[a[n], {n, 0, 104}] (* JeanFrançois Alcover, Nov 05 2013, after Franklin T. AdamsWatters *)


PROG

(Haskell)
import Data.List (transpose)
a036989 n = a036989_list !! n
a036989_list = 1 : concat (transpose
[map (+ 1) a036989_list, map ((max 1) . pred) $ tail a036989_list])
 Reinhard Zumkeller, Jul 31 2013


CROSSREFS

Cf. A036988, A036990, A126387.
Cf. A010060.
Sequence in context: A241165 A233183 A035942 * A035197 A227872 A323165
Adjacent sequences: A036986 A036987 A036988 * A036990 A036991 A036992


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Edited by Joshua Zucker, May 11 2006


STATUS

approved



