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

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

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), 187-198.

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. Adams-Watters, Dec 26 2006

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

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[(n-1)/2] + 1; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Nov 05 2013, after Franklin T. Adams-Watters *)

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: A233183 A035942 A329622 * A360330 A035197 A227872

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