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,2

Comments

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

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Index entries for sequences related to binary expansion of n

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

Cf. A070939, A078822.

Sequence in context: A243220 A334593 A293596 * A085430 A246794 A334030

Adjacent sequences: A301974 A301975 A301976 * A301978 A301979 A301980

Keyword

nonn,base,look

Author

Rémy Sigrist, Mar 30 2018

Status

approved