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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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.

Crossrefs

Cf. A036989. Characteristic function of A036990.

Programs

Haskell

a036988 = a063524 . a036989  -- 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 *)

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

Extensions

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