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.

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

Author

Rémy Sigrist, Mar 30 2018

Keywords

• nonn
• base
• look

Comments

This sequence has similarities with A078822; there we consider consecutive digits, here not.

Examples

			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
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A070939, A078822.

Programs

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

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)

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