A371176 - OEIS

A371176

Numbers k such that A000120(k) <= A001511(k).

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 28, 32, 34, 36, 40, 44, 48, 52, 56, 64, 66, 68, 72, 76, 80, 84, 88, 96, 100, 104, 112, 120, 128, 130, 132, 136, 140, 144, 148, 152, 160, 164, 168, 176, 184, 192, 196, 200, 208, 216, 224, 232, 240, 256, 258, 260, 264, 268

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

It appears that this sequence is obtained when ordering Schreier sets as explained in the Bird link. See decM(n) PARI code. - Michel Marcus, May 31 2024

That is correct since the binary representation of these numbers can be put into 1-to-1 correspondence with Schreier sets, which satisfy |X| <= min X, using the indicator function of X as the bits (starting from the right, LSB). The reason is that A000120 then computes |X| and A001511 computes min X. For example, the Schreier set X = {2, 5} can be mapped to 10010_2 = 18. - Michael S. Branicky, May 31 2024

From David A. Corneth, May 31 2024: (Start)

If k is in the sequence then so is 2*k.

a(A000045(k)) = 2^(k-2) for k >= 2. (End)

Apart from a(1), all terms are even. - Paolo Xausa, May 31 2024

Zeckendorf representation of n with rewrite 0 -> 0, {0, 1} -> 1 and k-1 zeros appended to the right side (where k is the number of ones in the given representation) and then interpreted as binary expansion is the same as a(n) (see the first formula). - Mikhail Kurkov, Oct 21 2024

LINKS

Michel Marcus, Table of n, a(n) for n = 1..10945

Alistair Bird, Jozef Schreier, Schreier sets and the Fibonacci sequence, Out Of The Norm blog, May 13 2012.

FORMULA

a(n) = b(n)*A001316(b(n))/2 where b(n) = A048679(n).

a(n) = Sum_{i=0..n-1} 2^A213911(i).

a(n) = 2^(A072649(n) - 1) + [c(n) > 0]*2*a(c(n)) where c(n) = A066628(n).

a(n) = 2*a(A005206(n)) - A003849(n)*2^A007895(n-1) for n > 1 with a(1) = 1.

MAPLE

filter:= proc(n) convert(convert(n, base, 2), `+`) <= 1+padic:-ordp(n, 2) end proc:

select(filter, [1, seq(i, i=2..1000, 2)]); # Robert Israel, Oct 20 2024

MATHEMATICA

Join[{1}, Select[Range[2, 1000, 2], DigitCount[#, 2, 1] <= IntegerExponent[#, 2] + 1 &]] (* Paolo Xausa, May 31 2024 *)

PROG

(PARI) isok(n) = hammingweight(n) <= (valuation(n, 2) + 1)

(PARI) M(n) = my(list=List()); for (i=1, n, forsubset(i, s, my(bOk = if (#s && (vecmax(s) == n), #s <= vecmin(s), 0)); if (bOk, listput(list, vecsort(Vec(s), , 4))); ); ); Vec(list);

decM(nn) = my(v = vector(nn, k, M(k)), list=List()); for (i=1, #v, my(vi = v[i]); for (j=1, #vi, my(s = vecsort(vi[j]), slist=List(), m = vecmax(s)); forstep(k=m, 1, -1, listput(slist, sign(vecsearch(s, k)))); listput(list, fromdigits(Vec(slist), 2)); ); ); vecsort(Vec(list)); \\ Michel Marcus, May 31 2024

(Python)

def ok(n): return n.bit_count() <= (-n&n).bit_length()

print([k for k in range(1, 300) if ok(k)]) # Michael S. Branicky, May 31 2024

(Python) # Assuming the list starts with 0.

def a():

n = na = nb = 1

while True:

yield not(nb < (na - 1) << 1)

nb, na = na, n.bit_count()

n += 1

aList = a(); print([n for n in range(77) if next(aList)]) # Peter Luschny, Jun 07 2024

CROSSREFS