login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 14

%I #233 Nov 27 2023 22:14:50

%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,

%T 71,75,77,79,83,85,87,91,93,95,103,107,109,111,115,117,119,123,125,

%U 127,143,151,155,157,159,167,171,173,175,179,181,183,187,189,191,199,203

%N 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.

%C List of binary words that correspond to a valid pairing of parentheses. - _Joerg Arndt_, Nov 27 2004

%C 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

%C Partial differences are powers of 2 (cf. A367626, A367627). - _Gennady Eremin_, Dec 23 2021

%C 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

%C 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

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

%H Alois P. Heinz, <a href="/A036991/b036991.txt">Table of n, a(n) for n = 1..13496</a> (all terms < 2^16; first 1000 terms from Reinhard Zumkeller)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.28, pp. 78-80.

%H Gennady Eremin, <a href="https://arxiv.org/abs/2211.01135">Dyck Numbers, II. Triplets and Rooted Trees in OEIS A036991</a>, arXiv:2211.01135 [math.NT], 2022.

%H Gennady Eremin, <a href="https://arxiv.org/abs/2302.02765">Dyck Numbers, III. Enumeration and bijection with symmetric Dyck paths</a>, arXiv:2302.02765 [math.CO], 2023.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F If a(n) = A000225(k) for some k, then a(n+1) = a(n) + A060546(k). - _Gennady Eremin_, Nov 07 2023

%e From _Joerg Arndt_, Dec 05 2021: (Start)

%e 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:

%e Binary Parentheses (if the value is in the sequence)

%e 00: ..... P [empty string]

%e 01: ....1 P ()

%e 02: ...1.

%e 03: ...11 P (())

%e 04: ..1..

%e 05: ..1.1 P ()()

%e 06: ..11.

%e 07: ..111 P ((()))

%e 08: .1...

%e 09: .1..1

%e 10: .1.1.

%e 11: .1.11 P (()())

%e 12: .11..

%e 13: .11.1 P ()(())

%e 14: .111.

%e 15: .1111 P (((())))

%e 16: 1....

%e 17: 1...1

%e 18: 1..1.

%e 19: 1..11 P (())()

%e (End)

%p q:= proc(n) local l, t, i; l:= Bits[Split](n); t:=0;

%p for i to nops(l) do t:= t-1+2*l[i];

%p if t<0 then return false fi

%p od: true

%p end:

%p select(q, [$0..300])[]; # _Alois P. Heinz_, Oct 09 2019

%t 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 *)

%t Join[{0},Select[Range[210],Min[Accumulate[Reverse[IntegerDigits[#,2]]/.{0->-1}]]>-1&]] (* _Harvey P. Dale_, Apr 18 2014 *)

%o (C++) /* returns true if the input is in the sequence: */

%o bool is_parenword(ulong x)

%o {

%o int s = 0;

%o for (ulong j=0; x!=0; ++j)

%o {

%o s += ( x&1 ? +1 : -1 );

%o if ( s<0 ) break; /* invalid word */

%o x >>= 1;

%o }

%o return (s>=0);

%o } /* _Joerg Arndt_, Nov 27 2004 */

%o (Haskell)

%o a036991 n = a036991_list !! (n-1)

%o a036991_list = filter ((p 1) . a030308_row) [0..] where

%o p _ [_] = True

%o p ones (0:bs) = ones > 1 && p (ones - 1) bs

%o p ones (1:bs) = p (ones + 1) bs

%o -- _Reinhard Zumkeller_, Jul 31 2013

%o (Python)

%o def ok(n):

%o if n == 0: return True # by definition

%o count = {"0": 0, "1": 0}

%o for bit in bin(n)[:1:-1]:

%o count[bit] += 1

%o if count["0"] > count["1"]: return False

%o return True

%o print([k for k in range(204) if ok(k)]) # _Michael S. Branicky_, Nov 25 2021

%o (Python)

%o from itertools import count, islice

%o def A036991_gen(): # generator of terms

%o yield 0

%o for n in count(1):

%o s = bin(n)[2:]

%o c, l = 0, len(s)

%o for i in range(l):

%o c += int(s[l-i-1])

%o if 2*c <= i:

%o break

%o else:

%o yield n

%o A036991_list = list(islice(A036991_gen(),20)) # _Chai Wah Wu_, Dec 30 2021

%o (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

%Y Cf. A350577 (primes subsequence).

%Y 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).

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

%K nonn,easy,base

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _Erich Friedman_

%E Edited by _N. J. A. Sloane_, Sep 14 2008 at the suggestion of _R. J. Mathar_

%E Offset corrected and example adjusted accordingly by _Reinhard Zumkeller_, Jul 31 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)