login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
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

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: A326846 A243220 A293596 * A085430 A246794 A285333

Adjacent sequences:  A301974 A301975 A301976 * A301978 A301979 A301980

KEYWORD

nonn,base,look

AUTHOR

Rémy Sigrist, Mar 30 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 29 10:34 EST 2020. Contains 331337 sequences. (Running on oeis4.)