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
Examples
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)
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, IV. Nested patterns in OEIS A036991, arXiv:2306.10318, 2023. See pp. 1-2, 4, 7-11, 13-14.
- Gennady Eremin, Partitioning the set of natural numbers into Mersenne trees and into arithmetic progressions; Natural Matrix and Linnik's constant, arXiv:2405.16143 [math.CO], 2024. See pp 2-5, 14.
- Gennady Eremin, Infinite matrix of odd natural numbers. A bit about Sophie Germain prime numbers, arXiv:2501.17090 [math.GM], 2025. See pp. 3, 11.
- Index entries for sequences related to binary expansion of n
Crossrefs
Programs
-
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
-
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 *) -
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 -
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
Formula
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
Comments