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

Offset: 1

Author

Mikhail Kurkov, Mar 14 2024

Keywords

• nonn
• base

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.
• Vaclav Kotesovec, Plot of log(a(n))/log(n) for n = 2..2129243
• Vaclav Kotesovec, Plot of a(n) / 2^(log(sqrt(5)*n)/log((1 + sqrt(5))/2) - 2) for n = 2..2129243

Crossrefs

Cf. A000045, A000120, A001316, A001511, A003849, A005206, A007895, A048679, A066628, A072649, A213911.

Cf. A355489, A373345, A373347 (complement), A373557.

Cf. A104287.

Programs

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], DigitSum[#, 2] <= IntegerExponent[#, 2] + 1 &]] (* Paolo Xausa, Aug 12 2025 *)

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

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.

Conjecture: lim sup_{n -> oo} log(a(n))/log(n) = log(2) / log((1 + sqrt(5))/2) = 1.440420090412556479... = A104287. - Vaclav Kotesovec, Aug 12 2025