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.
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
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Edited by Joshua Zucker, May 11 2006
STATUS
approved