A036991 Numbers k with the property that in the binary expansion of k, reading from right to left, the number of 0's never exceeds the number of 1's.

0, 1, 3, 5, 7, 11, 13, 15, 19, 21, 23, 27, 29, 31, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 71, 75, 77, 79, 83, 85, 87, 91, 93, 95, 103, 107, 109, 111, 115, 117, 119, 123, 125, 127, 143, 151, 155, 157, 159, 167, 171, 173, 175, 179, 181, 183, 187, 189, 191, 199, 203

Offset

1,3

Comments

List of binary words that correspond to a valid pairing of parentheses. - Joerg Arndt, Nov 27 2004

This sequence includes as subsequences A000225, A002450, A007583, A036994, A052940, A112627, A113836, A113841, A290114; and also A015521 (without 0), A083713 (without 0), A086224 (without 6), A182512 (without 0). - Gennady Eremin, Nov 27 2021 and Aug 26 2023

Partial differences are powers of 2 (cf. A367626, A367627). - Gennady Eremin, Dec 23 2021

This is the sequence A030101(A014486(n)), n >= 0, sorted into ascending order. See A014486 for more references, illustrations, etc., concerning Dyck paths and other associated structures enumerated by the Catalan numbers. - Antti Karttunen, Sep 25 2023

The terms in this sequence with a given length in base 2 are counted by A001405. For example, the number of terms of bit length k=5 (these are 19, 21, 23, 27, 29, and 31) is equal to A001405(k-1) = A001405(4) = 6. - Gennady Eremin, Nov 07 2023

References

Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318, 2023.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..13496 (all terms < 2^16; first 1000 terms from Reinhard Zumkeller)

Joerg Arndt, Matters Computational (The Fxtbook), section 1.28, pp. 78-80.

Gennady Eremin, Dyck Numbers, II. Triplets and Rooted Trees in OEIS A036991, arXiv:2211.01135 [math.NT], 2022.

Gennady Eremin, Dyck Numbers, III. Enumeration and bijection with symmetric Dyck paths, arXiv:2302.02765 [math.CO], 2023.

Index entries for sequences related to binary expansion of n

Formula

If a(n) = A000225(k) for some k, then a(n+1) = a(n) + A060546(k). - Gennady Eremin, Nov 07 2023

Example

From Joerg Arndt, Dec 05 2021: (Start)
List of binary words with parentheses for those in the sequence (indicated by P). The binary words are scanned starting from the least significant bit, while the parentheses words are written left to right:
     Binary   Parentheses (if the value is in the sequence)
00:  ..... P  [empty string]
01:  ....1 P   ()
02:  ...1.
03:  ...11 P   (())
04:  ..1..
05:  ..1.1 P   ()()
06:  ..11.
07:  ..111 P   ((()))
08:  .1...
09:  .1..1
10:  .1.1.
11:  .1.11 P   (()())
12:  .11..
13:  .11.1 P   ()(())
14:  .111.
15:  .1111 P   (((())))
16:  1....
17:  1...1
18:  1..1.
19:  1..11 P   (())()
(End)

Maple

q:= proc(n) local l, t, i; l:= Bits[Split](n); t:=0;
      for i to nops(l) do t:= t-1+2*l[i];
        if t<0 then return false fi
      od: true
    end:
select(q, [$0..300])[];  # Alois P. Heinz, Oct 09 2019

Mathematica

moreOnesRLQ[n_Integer] := Module[{digits, len, flag = True, iter = 1, ones = 0, zeros = 0}, digits = Reverse[IntegerDigits[n, 2]]; len = Length[digits]; While[flag && iter < len, If[digits[[iter]] == 1, ones++, zeros++]; flag = ones >= zeros; iter++]; flag]; Select[Range[0, 203], moreOnesRLQ] (* Alonso del Arte, Sep 21 2011 *)
Join[{0}, Select[Range[210], Min[Accumulate[Reverse[IntegerDigits[#, 2]]/.{0->-1}]]>-1&]] (* Harvey P. Dale, Apr 18 2014 *)

Prog

(C++) /* returns true if the input is in the sequence: */
bool is_parenword(ulong x)
{
    int s = 0;
    for (ulong j=0; x!=0; ++j)
    {
        s += ( x&1 ? +1 : -1 );
        if ( s<0 ) break; /* invalid word */
        x >>= 1;
    }
    return (s>=0);
}  /* Joerg Arndt, Nov 27 2004 */
(Haskell)
a036991 n = a036991_list !! (n-1)
a036991_list = filter ((p 1) . a030308_row) [0..] where
   p _    [_]    = True
   p ones (0:bs) = ones > 1 && p (ones - 1) bs
   p ones (1:bs) = p (ones + 1) bs
-- Reinhard Zumkeller, Jul 31 2013
(Python)
def ok(n):
    if n == 0: return True # by definition
    count = {"0": 0, "1": 0}
    for bit in bin(n)[:1:-1]:
        count[bit] += 1
        if count["0"] > count["1"]: return False
    return True
print([k for k in range(204) if ok(k)]) # Michael S. Branicky, Nov 25 2021
(Python)
from itertools import count, islice
def A036991_gen(): # generator of terms
    yield 0
    for n in count(1):
        s = bin(n)[2:]
        c, l = 0, len(s)
        for i in range(l):
            c += int(s[l-i-1])
            if 2*c <= i:
                break
        else:
            yield n
A036991_list = list(islice(A036991_gen(), 20)) # Chai Wah Wu, Dec 30 2021
(PARI) select( {is_A036991(n, c=1)=!n||!until(!n>>=1, (c-=(-1)^bittest(n, 0))||return)}, [0..99]) \\ M. F. Hasler, Nov 26 2021

Crossrefs

Cf. A350577 (primes subsequence).

See also A014486, A030101, A036988, A036990, A036992. A036994 is a subset (requires the count of zeros to be strictly less than the count of 1's).

See also A030308, A000225, A002450, A007583, A350346, A367625, A367626 & A367627 (first differences).

Sequence in context: A005239 A141107 A047484 * A165887 A316625 A091892

Adjacent sequences: A036988 A036989 A036990 * A036992 A036993 A036994

Keyword

nonn,easy,base

Author

N. J. A. Sloane

Extensions

More terms from Erich Friedman

Edited by N. J. A. Sloane, Sep 14 2008 at the suggestion of R. J. Mathar

Offset corrected and example adjusted accordingly by Reinhard Zumkeller, Jul 31 2013

Status

approved