cp's OEIS Frontend

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.

%I A301977 #19 Jan 26 2022 11:53:07
%S A301977 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,
%T A301977 5,6,10,13,12,14,17,16,12,13,18,20,17,16,18,15,10,10,15,18,16,17,20,
%U A301977 18,13,12,16,17,14,12,13,10,6,7,12,16,15,18,22,21,16,18
%N 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.
%C A301977 This sequence has similarities with A078822; there we consider consecutive digits, here not.
%H A301977 Rémy Sigrist, <a href="/A301977/b301977.txt">Table of n, a(n) for n = 1..10000</a>
%H A301977 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A301977 a(2^n) = n + 1 for any n >= 0.
%F A301977 a(2^n - 1) = n for any n > 0.
%F A301977 a(2^n + k) = a(2^(n+1)-1 - k) for any n >= 0 and k=0..2^n-1.
%F A301977 a(n) >= A070939(n) for any n > 0.
%F A301977 a(n) = Sum_{k=1..n} (Stirling2(n+1,k) mod 2) (conjecture). - _Ilya Gutkovskiy_, Jul 04 2019
%e A301977 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:
%e A301977   n  a(n)  bin(n)    bin(k)
%e A301977   -- ----  ------    ------
%e A301977    1    1       1    1
%e A301977    2    2      10    1, 10
%e A301977    3    2      11    1, 11
%e A301977    4    3     100    1, 10, 100
%e A301977    5    4     101    1, 10, 11, 101
%e A301977    6    4     110    1, 10, 11, 110
%e A301977    7    3     111    1, 11, 111
%e A301977    8    4    1000    1, 10, 100, 1000
%e A301977    9    6    1001    1, 10, 11, 100, 101, 1001
%e A301977   10    7    1010    1, 10, 11, 100, 101, 110, 1010
%e A301977   11    6    1011    1, 10, 11, 101, 111, 1011
%e A301977   12    6    1100    1, 10, 11, 100, 110, 1100
%e A301977   13    7    1101    1, 10, 11, 101, 110, 111, 1101
%e A301977   14    6    1110    1, 10, 11, 110, 111, 1110
%e A301977   15    4    1111    1, 11, 111, 1111
%e A301977   16    5   10000    1, 10, 100, 1000, 10000
%e A301977   17    8   10001    1, 10, 11, 100, 101, 1000, 1001, 10001
%e A301977   18   10   10010    1, 10, 11, 100, 101, 110, 1000, 1001, 1010, 10010
%e A301977   19    9   10011    1, 10, 11, 100, 101, 111, 1001, 1011, 10011
%e A301977   20   10   10100    1, 10, 11, 100, 101, 110, 1000, 1010, 1100, 10100
%p A301977 b:= proc(n) option remember; `if`(n=0, {0},
%p A301977       map(x-> [x, 2*x+r][], b(iquo(n, 2, 'r'))))
%p A301977     end:
%p A301977 a:= n-> nops(b(n))-1:
%p A301977 seq(a(n), n=1..72);  # _Alois P. Heinz_, Jan 26 2022
%o A301977 (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)
%Y A301977 Cf. A070939, A078822.
%K A301977 nonn,base,look
%O A301977 1,2
%A A301977 _Rémy Sigrist_, Mar 30 2018