A080116 Characteristic function of A014486. a(n) = 1 if n's binary expansion is totally balanced, otherwise zero.

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

Offset

0,1

Comments

a(n) = 1 if the binary representation of n forms a valid Dyck path, or equally, a well-formed parenthesization when 1's are converted to left and 0's to right parentheses (that is, when A007088(n) is in A063171), and 0 otherwise. - Antti Karttunen, Aug 23 2019

Links

Antti Karttunen, Table of n, a(n) for n = 0..65537

Index entries for sequences related to binary expansion of n

Index entries for characteristic functions

Index entries for sequences related to parenthesizing

Example

0 stands for an empty parenthesization, thus a(0) = 1.
2 has binary expansion "10", which corresponds with "()", thus a(2) = 1.
3 has binary expansion "11", but "((" is not a well-formed parenthesization, thus a(3) = 0.
10 has binary expansion "1010", corresponding with a well-formed parenthesization "()()", thus a(10) = 1.
38 has binary expansion "100110", but "())(()" is not a well-formed parenthesization, thus a(38) = 0.

Maple

A080116 := proc(n) local c, lev; lev := 0; c := n; while(c > 0) do lev := lev + (-1)^c; c := floor(c/2); if(lev < 0) then RETURN(0); fi; od; if(lev > 0) then RETURN(0); else RETURN(1); fi; end;

Mathematica

A080116[n_] := (lev = 0; c = n; While[c > 0, lev = lev + (-1)^c; c = Floor[c/2]; If[lev < 0, Return[0]]]; If[lev > 0, Return[0], Return[1]]); Table[A080116[n], {n, 0, 104}] (* Jean-François Alcover, Jul 24 2013, translated from Maple *)

Prog

(Sage)
def A080116(n) :
    lev = 0
    while n > 0 :
        lev += (-1)^n
        if lev < 0: return 0
        n = n//2
    return 0 if lev > 0 else 1
[A080116(n) for n in (0..104)] # Peter Luschny, Aug 09 2012
(PARI) A080116(n) = { my(k=0); while(n, k += (-1)^n; n >>= 1; if(k<0, return(0))); (0==k); }; \\ Antti Karttunen, Aug 23 2019

Crossrefs

Cf. A014486, A063171, A080110, A080111, A080300, A080301.

Sequence in context: A016378 A323513 A089805 * A016359 A014029 A016396

Adjacent sequences: A080113 A080114 A080115 * A080117 A080118 A080119

Keyword

nonn,base

Author

Antti Karttunen, Feb 11 2003

Extensions

Examples added by Antti Karttunen, Aug 23 2019

Status

approved