A036988 Has simplest possible tree complexity of all transcendental sequences.

1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1

Offset

0,1

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

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(n) = A063524(A036989(n)). - Reinhard Zumkeller, Jul 31 2013

Mathematica

(* b = A036989 *) b[0] = 1; b[n_?EvenQ] := b[n] = Max[b[n/2] - 1, 1]; b[n_] := b[n] = b[(n-1)/2] + 1; a[n_] := Boole[b[n] == 1]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Nov 05 2013, after Reinhard Zumkeller *)

Prog

(Haskell)
a036988 = a063524 . a036989  -- Reinhard Zumkeller, Jul 31 2013

Crossrefs

Cf. A036989. Characteristic function of A036990.

Sequence in context: A357385 A316533 A085405 * A108357 A309848 A326822

Adjacent sequences: A036985 A036986 A036987 * A036989 A036990 A036991

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Sep 25 2000

Status

approved