VOOZH about

URL: https://oeis.org/A301977

⇱ A301977 - OEIS

login
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 A379719 A246794
KEYWORD
nonn,base,look
AUTHOR
Rémy Sigrist, Mar 30 2018
STATUS
approved