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
Examples
59 in binary is 111011, excess from right to left is 1,2,1,2,3,4, maximum is 4, so a(59) = 4.
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
Programs
-
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
-
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 *)
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
Extensions
Edited by Joshua Zucker, May 11 2006
Comments