login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A301977
a(n) is the number of distinct positive numbers whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.
4
1, 2, 2, 3, 4, 4, 3, 4, 6, 7, 6, 6, 7, 6, 4, 5, 8, 10, 9, 10, 12, 11, 8, 8, 11, 12, 10, 9, 10, 8, 5, 6, 10, 13, 12, 14, 17, 16, 12, 13, 18, 20, 17, 16, 18, 15, 10, 10, 15, 18, 16, 17, 20, 18, 13, 12, 16, 17, 14, 12, 13, 10, 6, 7, 12, 16, 15, 18, 22, 21, 16, 18
OFFSET
1,2
COMMENTS
This sequence has similarities with A078822; there we consider consecutive digits, here not.
FORMULA
a(2^n) = n + 1 for any n >= 0.
a(2^n - 1) = n for any n > 0.
a(2^n + k) = a(2^(n+1)-1 - k) for any n >= 0 and k=0..2^n-1.
a(n) >= A070939(n) for any n > 0.
a(n) = Sum_{k=1..n} (Stirling2(n+1,k) mod 2) (conjecture). - Ilya Gutkovskiy, Jul 04 2019
EXAMPLE
The first terms, alongside the binary representations of n and of the numbers k whose binary digits appear in order in the binary representation of k, are:
n a(n) bin(n) bin(k)
-- ---- ------ ------
1 1 1 1
2 2 10 1, 10
3 2 11 1, 11
4 3 100 1, 10, 100
5 4 101 1, 10, 11, 101
6 4 110 1, 10, 11, 110
7 3 111 1, 11, 111
8 4 1000 1, 10, 100, 1000
9 6 1001 1, 10, 11, 100, 101, 1001
10 7 1010 1, 10, 11, 100, 101, 110, 1010
11 6 1011 1, 10, 11, 101, 111, 1011
12 6 1100 1, 10, 11, 100, 110, 1100
13 7 1101 1, 10, 11, 101, 110, 111, 1101
14 6 1110 1, 10, 11, 110, 111, 1110
15 4 1111 1, 11, 111, 1111
16 5 10000 1, 10, 100, 1000, 10000
17 8 10001 1, 10, 11, 100, 101, 1000, 1001, 10001
18 10 10010 1, 10, 11, 100, 101, 110, 1000, 1001, 1010, 10010
19 9 10011 1, 10, 11, 100, 101, 111, 1001, 1011, 10011
20 10 10100 1, 10, 11, 100, 101, 110, 1000, 1010, 1100, 10100
MAPLE
b:= proc(n) option remember; `if`(n=0, {0},
map(x-> [x, 2*x+r][], b(iquo(n, 2, 'r'))))
end:
a:= n-> nops(b(n))-1:
seq(a(n), n=1..72); # Alois P. Heinz, Jan 26 2022
PROG
(PARI) a(n) = my (b=binary(n), s=Set(1)); for (i=2, #b, s = setunion(s, Set(apply(v -> 2*v+b[i], s)))); return (#s)
CROSSREFS
Sequence in context: A243220 A334593 A293596 * A085430 A246794 A334030
KEYWORD
nonn,base,look
AUTHOR
Rémy Sigrist, Mar 30 2018
STATUS
approved